[백준/Python] 해시 - 임진왜란(3077)

임진왜란

---

 

문제 설명

---

현우는 방금 선생님으로부터 역사 시험 결과를 받았다. 현우가 가장 열심히 공부한 문제는 임진왜란의 해전을 일어난 순서대로 적는 문제이다.

올바른 순서는 다음과 같다.

1. 옥포 해전 2. 사천 해전 3. 한산도 대첩 4. 명량 해전 5. 노량 해전

현우는 정말 열심히 공부했고, 옥포 해전을 제외한 모든 해전의 날짜를 외웠다. 따라서, 현우는 옥포 해전이 가장 먼저 일어난 해전인지 마지막에 일어난 해전인지 생각해내지 못했고, 다음과 같이 결국 제일 마지막에 적고말았다.

1. 사천 해전 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로 출력한다. (약분 하면 안 된다)

 

 

입력 예시

---

5 okpo sacheon hansan myeongnyang noryang sacheon hansan myeongnyang noryang okpo

3 alpha beta gamma alpha gamma beta

5 naboo geonosis yavin hoth endor geonosis yavin hoth endor naboo

 

출력 예시

---

6/10

2/3

6/10

 

 

---

나의 풀이

import sys
import itertools  # 조합

# n: 해전의 개수
n = int(sys.stdin.readline())

# 해전 순서의 정답
wars_correct = dict(zip(sys.stdin.readline().split(), [i for i in range(n)]))

# 학생의 답안
wars_answer = sys.stdin.readline().split()

# 학생의 답안 중 N(N-1)/2개의 쌍 고름
pick = list(itertools.combinations(wars_answer, 2))
''' >>> 출력: [('sacheon', 'hansan'), ('sacheon', 'myeongnyang'), ('sacheon', 'noryang'), ('sacheon', 'okpo'), ('hansan', 'myeongnyang'),
 ('hansan', 'noryang'), ('hansan', 'okpo'), ('myeongnyang', 'noryang'), ('myeongnyang', 'okpo'), ('noryang', 'okpo')]
'''
point = 0  # 학생의 점수
# N(N-1)/2개의 쌍 중에서 해전이 일어난 연도의 순서를 맞게 적었다면 +1점
for p in pick:
    if wars_correct.get(p[0]) < wars_correct.get(p[1]):
        point += 1

# 학생 점수/총 점수
print("%d/%d" % (point, n*(n-1)/2))

- 💡 아이디어
해전이 일어난 순서대로 정답이 받아지므로, 해전 이름을 key, 순서를 value로 하여 딕셔너리로 받았다.
학생의 답안 중 N(N-1)/2개의 쌍을 전부 검사하여 순서가 맞았는지 틀렸는지 검사하므로 이를 itertools.combination을 이용하여 조합을 만들었다.
만든 조합을 for문을 사용하여 검사하며, 맞았을 시 point를 +1하였다.

 

- 📚 후기

시간제한이 1초길래 정말 모든 경우의 수를 찾는 게 맞나? 라는 생각을 했는데 그게 맞았다.
해시를 이용해 최대한 시간을 줄이는 것이 관건이었던 것 같다.

 

- ✏️ 배운점

• dict(zip(list1, list2)): list 두 개를 이용하여 딕셔너리로 만듦. list1은 key, list2는 value가 됨.
• itertools: 경우의 수를 찾을 때 사용되는 라이브러리 (import itertools)
  • itertools.permutations: 순서는 중요하고 중복은 허용되지 않음.
    ex) itertools.permutations([1, 2, 3], 2) => [(1,2), (1,3), (2,1), (2,3), (3,1), (3,2)]
  • itertools.product: 순서는 중요하고 중복은 허용됨.
    ex) itertools.product([1, 2, 3], 2) => [(1,1), (1,2), (1,3), (2,1), (2,2), (2,3), (3,1), (3,2), (3,3)]
  • itertools.combinations: 순서는 중요하지 않고 중복은 허용되지 않음.
    ex) itertools.combinations([1, 2, 3], 2) => [(1,2), (1,3), (2,3)]
  • itertools.combinations_with_replacement: 순서는 중요하지 않고 중복은 허용됨.
    ex) itertools.combinations_with_replacement([1, 2, 3], 2) => [(1,1), (1,2), (1,3), (2,2), (2,3), (3,3)]