[Algorithm] 백준 1021

ZEDY·2024년 3월 19일

[코딩테스트] 알고리즘 문제풀이

목록 보기

14/46

문제

지민이는 N개의 원소를 포함하고 있는 양방향 순환 큐를 가지고 있다. 지민이는 이 큐에서 몇 개의 원소를 뽑아내려고 한다.

지민이는 이 큐에서 다음과 같은 3가지 연산을 수행할 수 있다.

첫 번째 원소를 뽑아낸다. 이 연산을 수행하면, 원래 큐의 원소가 a1, ..., ak이었던 것이 a2, ..., ak와 같이 된다.
왼쪽으로 한 칸 이동시킨다. 이 연산을 수행하면, a1, ..., ak가 a2, ..., ak, a1이 된다.
오른쪽으로 한 칸 이동시킨다. 이 연산을 수행하면, a1, ..., ak가 ak, a1, ..., ak-1이 된다.
큐에 처음에 포함되어 있던 수 N이 주어진다. 그리고 지민이가 뽑아내려고 하는 원소의 위치가 주어진다. (이 위치는 가장 처음 큐에서의 위치이다.) 이때, 그 원소를 주어진 순서대로 뽑아내는데 드는 2번, 3번 연산의 최솟값을 출력하는 프로그램을 작성하시오.

풀이

내가 생각한 알고리즘

큐 -> N크기
1. N크기만큼의 큐 생성
2. num 만큼 입력받아, 연산
3. 조회를 하고 맞다면 뽑고, 아니면 왼쪽으로 움직였을 때와 오른쪽으로 움직였을 때의 최솟값을 구해서 더해간다.

이 코드는 원형 큐에서 특정 숫자를 찾는 과정을 구현합니다. 입력으로 받은 숫자 리스트를 원형 큐에서 순차적으로 찾으면서, 왼쪽 또는 오른쪽으로 이동하는 횟수를 세는 방식입니다.

주요 절차:
1. 초기화: 입력된 N 값에 따라 원형 큐 Q를 생성하고, 각 요소에는 1부터 N까지의 값이 들어갑니다.
2. find_right 함수: 주어진 숫자를 찾을 때까지 오른쪽으로 이동하면서 이동한 횟수를 카운트합니다.
3. find_left 함수: 주어진 숫자를 찾을 때까지 왼쪽으로 이동하면서 이동한 횟수를 카운트합니다.
4. 주어진 숫자 리스트를 순회하면서 현재 위치와 주어진 숫자를 비교하여 같지 않은 경우에는 오른쪽과 왼쪽으로 이동하면서 최소 이동 횟수를 찾습니다.
5. 찾은 숫자는 큐에서 제거하고, 다음 숫자를 찾을 때 이동 횟수를 최소화하기 위해 현재 위치를 업데이트합니다.
6. 최종적으로 이동한 횟수를 출력합니다.

맞은 코드

N, n = map(int, input().split(' '))

Q = [[0] for _ in range(N)]

for i in range(0, N):
    Q[i] = i+1

def find_right(num, current):
    cnt = 0
    temp = current

    while Q[temp] != num:
        temp += 1
        if temp >= len(Q):
            temp = temp - len(Q)
        cnt += 1
        
    return (cnt, temp)

def find_left(num, current):
    cnt = 0
    temp = current

    while Q[temp] != num:
        temp -= 1
        if - temp >= len(Q):
            temp = temp + len(Q)
        cnt += 1

    return (cnt, temp)

current = 0
cnt = 0

num_list = list(map(int, input().split(' ')))

for j in range(0, len(num_list)):
    num = num_list[j]
    if num != Q[current]:
        cnt_right, temp_right = find_right(num, current)
        cnt_left, temp_left = find_left(num, current)

        cnt += min(cnt_right, cnt_left)
        current = Q.index(num)
        Q.remove(num)
        if current >= len(Q):
            current = current - len(Q)
    else:
        Q.remove(num)
        if current >= len(Q):
            current = current - len(Q)
print(cnt)

나는 튜플을 사용했는데, 중복 값들을 리턴하고 싶어서 그렇게 구현을 하였다.
생각해보니까 temp_right와 temp_left는 사용하지 않았다..

개선

개선할 부분:
1. find_right와 find_left 함수에서 현재 위치를 이동할 때 사용하는 방식을 개선할 수 있습니다. 현재 구현은 임의의 값에 대해 원형 큐의 범위를 넘어가는 경우에 대한 처리를 하고 있지만, 이를 간단하게 처리할 수 있습니다.
-> 원래는 int(temp%len(Q))로 처리했지만 음수를 어떻게 다뤄야할지 몰라서 저렇게 체크해서 연산을 하였다.
-> 양수 값을 처리하는 오른쪽 탐색에는 충분히 사용할 수 있지만, 왼쪽 탐색은 어떻게 하면 좋을까?

음수 값에 대한 처리를 위해서는, 이동할 때 현재 위치에 N을 더하고 나눈 나머지를 취하는 방법 대신에, 음수 값에 대한 별도의 처리를 추가해야 합니다.

음수 값에 대한 처리를 추가하는 방법은 다음과 같습니다:
1. 현재 위치에 이동할 값이 음수인 경우, 이동할 값을 양수로 변환하여 처리합니다.
2. 이동한 결과가 음수가 되는 경우에는 다음과 같이 처리합니다:

현재 위치에 이동할 값을 더한 후, 만약 결과가 음수가 되면, 이를 처리하기 위해 원형 큐의 길이 N을 더하고 다시 N으로 나눈 나머지를 취합니다.

이렇게 함으로써 음수 값을 처리할 수 있고, 원형 큐의 범위를 벗어나는 경우에 대해서도 적절하게 처리할 수 있게 됩니다.
-> 복잡하네..

코드 중복을 줄이고 가독성을 높일 수 있습니다. 특히, find_right와 find_left 함수는 유사한 기능을 하므로 중복을 최소화할 필요가 있습니다. 함수를 하나로 통합할 수 있습니다.

Chat GPT라면??

이 문제를 해결하기 위해서는 다음과 같은 방식을 사용할 수 있습니다:

초기 큐 생성: 크기가 N인 원형 큐를 생성합니다. 큐에는 1부터 N까지의 숫자가 들어갑니다.
주어진 위치에 따라 이동 횟수 계산:
- 주어진 위치부터 원하는 요소까지의 거리를 계산합니다.
- 이 거리를 기반으로 왼쪽으로 이동하는 횟수와 오른쪽으로 이동하는 횟수를 구합니다.
이동 횟수 중 최솟값 출력:
- 왼쪽으로 이동하는 횟수와 오른쪽으로 이동하는 횟수 중 작은 값을 출력합니다.

이 방법을 사용하여 주어진 위치에 해당하는 요소를 추출하는 데 필요한 최소 이동 횟수를 계산할 수 있습니다.

여기 코드의 개략적인 구현이 있습니다:

def calculate_min_moves(N, positions):
    # 초기 큐 생성
    queue = list(range(1, N + 1))
    
    # 각 위치별 이동 횟수 계산
    min_moves = []
    for pos in positions:
        # 현재 위치에서의 왼쪽 이동 횟수
        left_moves = pos - 1
        # 현재 위치에서의 오른쪽 이동 횟수
        right_moves = N - pos + 1
        
        # 왼쪽 또는 오른쪽 이동 중 작은 이동 횟수를 선택하여 결과에 추가
        min_moves.append(min(left_moves, right_moves))
    
    return min_moves

# 입력 받기
N, M = map(int, input().split())
positions = list(map(int, input().split()))

# 최소 이동 횟수 계산
result = calculate_min_moves(N, positions)

# 결과 출력
for moves in result:
    print(moves)