[파이썬/python] 백준 3077 - 임진왜란

문제

https://www.acmicpc.net/problem/3077

---

문제 설명

1. 해전 순서를 맞춰야 하는 역사 시험이 주어진다.
2. 해전의 순서를 전부 맞춰야 하는 것이 아니라 두 개의 해전의 순서가 맞을 때 마다 1점씩 부여하도록 한다.
3. 정답과 제출한 답안을 비교했을 때 점수를 구해라.

 

---

풀이

1.   총 해전에서 두 개의 해전을 선택한다.
   1. 두 해전의 순서가 정답의 해전과 같으면 1점을 부여한다.
2. 모든 경우의 수를 판단하여 점수를 부여한다.

---

코드

import sys
input = sys.stdin.readline

n = int(input())
ans = input().split()
dic = {ans[i]: i for i in range(n)}
stack = [dic[i] for i in input().split()]

total = n*(n-1)//2

cnt = 0
res = 0
tmp = [stack.pop()]
while stack:
  crnt = stack.pop()
  for prev in tmp:
    if crnt < prev:
      res+=1
  tmp.append(crnt)
print(f"{res}/{total}")

---

시간복잡도

• 최악의 경우 $N = 2500$
• stack이 비워질 때 까지 반복하므로  O(N)이다.
  따라서 O(10*3)정도 소요된다.