문제
현우는 방금 선생님으로부터 역사 시험 결과를 받았다. 현우가 가장 열심히 공부한 문제는 임진왜란의 해전을 일어난 순서대로 적는 문제이다.
올바른 순서는 다음과 같다.
- 옥포 해전 2. 사천 해전 3. 한산도 대첩 4. 명량 해전 5. 노량 해전
현우는 정말 열심히 공부했고, 옥포 해전을 제외한 모든 해전의 날짜를 외웠다. 따라서, 현우는 옥포 해전이 가장 먼저 일어난 해전인지 마지막에 일어난 해전인지 생각해내지 못했고, 다음과 같이 결국 제일 마지막에 적고말았다.
- 사천 해전 2. 한산도 대첩 3. 명량 해전 4. 노량 해전 5. 옥포 해전
현우가 적은 정답은 모든 위치에서 정답과 일치하지 않는다. 따라서 5개 해전 중에 4개 해전의 순서를 올바르게 적었지만, 점수는 5점 만점에 0점이 된다.
현우는 이러한 채점 방식이 큰 문제가 있다고 생각했다.
현우는 선생님께 해전이 일어난 정확한 연도도 중요하지만, 상대적인 관계가 훨씬 더 중요하다고 말했고, 선생님은 현우의 의견을 받아들여 이 문제를 다시 채점하기로 했다.
선생님이 다시 사용한 채점 방법은 두 해전을 골라 순서가 일치하면 점수를 주는 방법이다. 즉, 선생님은 학생의 답 중에 N(N-1)/2개의 쌍을 모두 고른뒤, 올바른 순서로 적혀져 있으면 1점을 주려고 한다. 최종 점수는 획득점수/(N(N-1)/2)가 된다.
문제의 정답과 현우가 작성한 답안이 주어졌을 때, 현우의 점수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 해전의 개수 N이 주어진다. (2 ≤ N ≤ 2500) 다음 줄에는 올바른 정답이 공백으로 구분되어 주어진다. 그 다음 줄에는 현우가 작성한 답안이 공백으로 구분되어 주어진다. 해전의 이름은 3글자~15글자 알파벳 소문자로 이루어져 있다.
출력
현우가 획득한 점수를 a/b로 출력한다. (약분 하면 안 된다)
풀이 - 오답 (Deque를 이용한 풀이)
import sys
from collections import deque
input = sys.stdin.readline
n = int(input())
writing = input().split()
answer = input().split()
writing_pair = deque()
answer_pair = deque()
count = int(0)
for i in range(len(writing) - 1):
for j in range(i + 1, len(answer)):
writing_pair.append(writing[i] + " " + writing[j])
answer_pair.append(answer[i] + " " + answer[j])
while writing_pair:
target = writing_pair.popleft()
if target in answer_pair:
count += 1
print(str(count) + "/" + str(len(answer_pair)))Deque 가 append연산이 O(1) 복잡도를 가진다고 알고 있어서 Deque 로 모든 쌍의 조합을 만든 후에,
답안지와 비교하는 로직을 작성해봤는데 채점 9% 쯤 메모리 초과가 뜨게 됐다.
풀이 - 정답 (Dict를 이용한 풀이)
import sys
input = sys.stdin.readline
n = int(input())
answer = dict(zip(input().split(), [i for i in range(n)]))
writing = input().split()
count = int(0)
for i in range(n - 1):
for j in range(i + 1, n):
if answer[writing[i]] < answer[writing[j]]:
count += 1
print(count, "/", n * (n - 1) // 2, sep="")도저히 이유를 모르겠어서 다른 사람들의 의견을 참고하니 Dict를 활용해서 풀어야 한다고 했다.
여기서 포인트는 순서가 일치한지 확인하기 위해 일일히 순서쌍을 만들고 검사하는게 아니라
답안지 내용에서 현재 순회하고 있는 답안지의 어떤 원소가 그 다음 답안에 있는 원소보다 작으면 그 순서가 맞는것으로 처리하면 된다.