[백준 알고리즘: python 3] #1021 - 회전하는 큐

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

 

* 1020번은... 생각보다 어렵네요 ㅠㅠ 공부를 좀 더 해보고 기회가 되면 다시 풀어보려 합니다.

 

1021번은 회전하는 큐라는 이름의 문제로 소개되어 있습니다. N개의 원소를 포함하고 있는 양방향 순환 큐에서 원하는 원소를 정해진 연산 법칙에 맞게 뽑아내는 데요, 그 연산 법칙은 다음과 같습니다.

 

1. 첫 번째 원소를 뽑아낸다. 이 연산을 수행하면, 원래 큐의 원소가 a1, ..., ak이었던 것이 a2, ..., ak와 같이 된다.
2. 왼쪽으로 한 칸 이동시킨다. 이 연산을 수행하면, a1, ..., ak가 a2, ..., ak, a1이 된다.
3. 오른쪽으로 한 칸 이동시킨다. 이 연산을 수행하면, a1, ..., ak가 ak, a1, ..., ak-1이 된다.

원하는 원소의 큐에서의 처음 위치가 주어졌을 때, 2번 3번 연산을 총 몇번 했는지 출력하는 문제입니다. 별로 어렵지 않은 문제였습니다!

 

Hint!

이 문제에서 까다롭다면 까다로운 부분이, 주어진 원소를 순서대로 꺼내려고 할 때 현재 타겟이 되는 원소가 2번 연산과 3번 연산 중에 무엇이 더 빠른지 먼저 캐치해야 한다는 점입니다. 이 부분만 해결한다면 문제에서 주어진 메커니즘 대로 큐를 바꿔가며 답을 내면돼요.

 

python 같은 경우에는 특정 원소가 몇번째 index에 위치했는지 알려주는 함수(list.index(찾는 원소))가 존재합니다. 이 함수를 많이 활용합니다. 아래는 제가 성공한 코드의 풀이 순서입니다.

 

1. 먼저, N의 크기를 가진 1부터 시작하는 자연수들의 queue를 만듭니다. 예를 들어, N=10이라면 queue = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]입니다. 그리고 최종 결과값을 0으로 초기화 합니다.
2. 입력으로 받은 빼내고자 하는 원소들의 리스트를 for문으로 순회 합니다.
   1. 현재 for문으로 들어온 원소의 queue에서의 위치를 찾습니다. (queue.index(원소))
   2. 그 위치의 원소가 queue의 첫번째 원소로 오기위한 2번 연산의 수와 3번 연산의 수를 비교하고 둘 중 작은 값을 찾습니다. 이 때, python의 리스트의 index 방식을 활용하면 좋은데요, 바로 위 1번에서 구한 index는 2번 연산의 수와 같고 3번 연산의 수는 현재 queue의 길이에 1번에서 구한 index의 값을 뺀 것과 같습니다. 예를 들어, N이 10이고 현재 원소의 index가 3이라면 빼내기 위한 2번 연산의 수는 3번, 3번 연산은 7번이 됩니다. (이건 공책이 있으면 펴서 확인해보세요!)
   3. 2에서 구한 연산의 최솟값 만큼 해당 연산을 그대로 진행합니다. 2번 연산이면 최솟값 만큼 queue의 맨 앞 값을 맨 뒤로 보내는 것을 반복하고 3번 연산이면 맨 뒷값을 앞으로 보내는 것을 반복합니다.
   4. 2에서 구한 연산의 최솟값을 결과값에 더하고 큐의 맨 처음 값을 빼냅니다(삭제합니다).
3. 결과값을 출력합니다.

 

이 과정을 아래의 코드로 구현해 성공하였습니다.

 

import sys

N, M = map(int, sys.stdin.readline().split())
targets = list(map(int, sys.stdin.readline().split(' ')))
queue = [i for i in range(1, N+1)]

ans = 0
for target in targets:
    plus_index = queue.index(target) # 앞에꺼를 뒤로 넘기는 연산 수
    minus_index = len(queue) - plus_index # 뒤에꺼를 앞으로 넘기는 연산 수
    steps = min(plus_index, minus_index) # 둘 중 최솟값

    # plus는 2번 연산
    # minus는 3번 연산
    if steps == plus_index: sign = 'plus' 
    else: sign = 'minus'

    if sign == 'plus':
        for _ in range(steps):
            temp = queue.pop(0)
            queue.append(temp)
    else:
        for _ in range(steps):
            temp = queue.pop(-1)
            queue.insert(0, temp)
    
    ans += steps
    queue.pop(0)

print(ans)