3077. [Python]임진왜란

1. 문제

 

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

3077번: 임진왜란

 

2. 접근 방법

 

• 시간 제한: 1초
• 메모리 제한: 128MB
• 딕셔너리
• 브루트 포스

 

3. 파이썬 코드

 

N = int(input())
# 정답 리스트 생성
answer_list = list(map(str,input().split()))
# 제출 리스트 생성
check_list = list(map(str,input().split()))
# 정답 갯수 체크
cnt = 0
# 시간 절약을 위해 딕셔너리 선언
answer_dict = {}
# enumerate를 통해 index 와 value를 가져옴
for i,j in enumerate(answer_list):
    # 딕셔너리에 값 추가
    answer_dict[j] = i
# N까지 반복
for i in range(N):
    # 처음 뽑을 값
    first_answer = check_list[i]
    # 이후 뽑을 값들 i+1부터 N 까지
    for j in range(i+1,N):
        second_answer = check_list[j]
        # 딕셔너리에 처음 값의 인덱스와 이후 값의 인덱스의 대소를 비교하여 cnt 증가
        if answer_dict[first_answer] < answer_dict[second_answer]:
            cnt += 1

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

print(f"{cnt}/{total}")

 

4. 문제를 풀고난 후 생각

 

• 문제를 읽고 딕셔너리를 생각하지 못해서 리스트로 처음에는 구현을 진행했다.
• 당연히 3중 for문을 통해서 리스트를 탐색했기 때문에 2500 * 2500 * 2500 정도로 시간초과가 발생했다.
• 인덱스를 찾는 방법을 고민하던 중 딕셔너리를 이용하여 key : value 쌍으로 단어와 인덱스 값을 넣는 방법을 생각했고, 딕셔너리를 이용하여 내가 찾은 두 값의 인덱스를 비교해서 작은 경우 cnt가 증가하는 코드를 구현했다.
• 문제 자체의 난이도는 어렵지 않지만 딕셔너리와 리스트를 병행해서 사용하는 것을 생각하지 못하면 조금 고민이 필요했던 문제같다.

 

5. 문제를 푸는데 도움이 되는 지식

 

• 딕셔너리
• 브루트 포스