-
3077. [Python]임진왜란Python_알고리즘/Silver III 2023. 7. 26. 20:22
1. 문제
https://www.acmicpc.net/problem/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. 문제를 푸는데 도움이 되는 지식
- 딕셔너리
- 브루트 포스
'Python_알고리즘 > Silver III' 카테고리의 다른 글
1021. [Python]회전하는 큐 (0) 2023.08.02 3474. [Python]교수가 된 현우 (0) 2023.07.31 3273. [Python]두 수의 합 (0) 2023.07.25 2512. [Python]예산 (0) 2023.07.18 2503. [Python]숫자 야구 (0) 2023.07.13