-
1021. [Python]회전하는 큐Python_알고리즘/Silver III 2023. 8. 2. 15:18
1. 문제
https://www.acmicpc.net/problem/1021
2. 접근 방법
- 시간 제한: 2초
- 메모리 제한: 128MB
- Deque(덱)
3. 파이썬 코드
# deque 선언 from collections import deque N, M = map(int,input().split()) # 찾고자 하는 숫자 리스트 answer_list = list(map(int,input().split())) # 초기 인덱스값 index = 0 # deque 선언 deque_list = deque() # deque에 1 ~ N 까지 값추가 for i in range(1,N+1): deque_list.append(i) cnt = 0 # 인덱스 값이 찾고자 하는 숫자의 개수 전 까지 반복 while index != M: # check_num 에 찾고자 하는 숫자의 값들을 한개씩 대입 check_num = answer_list[index] # 0번째 인덱스 값이 찾는 값이 아닌 경우 if check_num != deque_list[0]: # 찾고자 하는 숫자가 deque_list에 가운데 인덱스를 기준으로 왼쪽인지 오른쪽인지 판단. if N//2 >= deque_list.index(check_num): # 중앙에서 왼쪽인 경우 리스트를 -1 방향으로 계속 돌리며 cnt 값 증가 while deque_list[0] != check_num: deque_list.rotate(-1) cnt += 1 elif N//2 < deque_list.index(check_num): # 찾고자 하는 숫자가 deque_list에 가운데 인덱스를 기준으로 오른쪽인 경우 리스트를 +1 방향으로 계속 돌리며 cnt 값 증가 while deque_list[0] != check_num: deque_list.rotate(1) cnt += 1 # deque_list 에서 젤 왼쪽값 제거 후 N 값 -1 deque_list.popleft() N -= 1 index += 1 print(cnt)
4. 문제를 풀고난 후 생각
- 리스트 왼쪽값을 기준으로 목표값이 어디있는지 찾는 문제이다.
- 특이하게 Deque를 사용하여 리스트를 돌리면서 값을 찾는 문제였다.
- 0번 인덱스 값이 목표값이 아닌 경우 리스트 중앙을 기준으로 찾고자 하는 값의 위치를 가져온 후 그 가져온 위치가 어디에 가까운지 따라서 오른쪽으로 돌릴지 왼쪽으로 돌릴지 결정했다.
- 돌릴때마다 cnt 값을 증가시키는 형태로 구현했다.
- 돌리기가 끝나면 그 값을 뽑아주고 N 값은 계속해서 -1 해준 후 index를 증가시켜 while 문을 탈출 시켰다.
5. 문제를 푸는데 도움이 되는 지식
- Deque(덱)
'Python_알고리즘 > Silver III' 카테고리의 다른 글
1347. [Python]미로 만들기 (0) 2023.08.02 2607. [Python]비슷한 단어 (0) 2023.08.02 3474. [Python]교수가 된 현우 (0) 2023.07.31 3077. [Python]임진왜란 (0) 2023.07.26 3273. [Python]두 수의 합 (0) 2023.07.25