[Algorithm] Baekjoon 1021번 : 회전하는 큐

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

1021번: 회전하는 큐

 
int n, m;
int arr[51] = { 0 };
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> n >> m;
 
    for (int i = 1; i <= n; ++i)
    {
        arr[i] = i;
    }
 
    int frontIndex = 1;
    int queueSize = n;
    int answer = 0;
 
    for (int i = 0; i < m; ++i)
    {
        int target = 0;
        cin >> target;
 
        int index = frontIndex;
        int count = 0;
 
        while (1) // 오른쪽으로 쭉 순회.
        {
            if (arr[index] == target) // 찾았으면
            {
                arr[index] = -1;
                frontIndex = index + 1;
 
                if (index + 1 > n)
                {
                    frontIndex = 1;
                }
                
                break;
            }
            else if (arr[index] == -1)
            {
                ++index;
            }
            else // 타겟아닌 숫자면
            {
                ++index;
                ++count;
            }
 
            if (index > n)
            {
                index = 1;
            }
        }
 
        // 여기 count값은 우측순회했을 때 count.
        if (count <= queueSize / 2) // 우측카운팅값 그대로 이용. 크기 짝수면 똑같고, 홀수면 작아야됨
        {
            answer += count;
        }
        else
        {
            answer += queueSize - count;
        }
 
        --queueSize;
    }
 
    cout << answer;
}

 

보통 덱을 이용해서 풀이들을 하는것 같은데, 덱을 안써도 풀 수 있을 것 같아서 배열하나로 풀어봤다.

타겟을 찾고, pop을 했다는 표현을 해당칸에 -1을 넣어줌으로써 표현했다.

그리고 pop한다음에 그 다음 인덱스가 큐의 맨 앞쪽이라는 표시를 해준다.

배열에서 -1이 표시된곳은 pop을 했던 빈 곳이기 때문에, 순회할 때 -1이라면 카운팅을 하지 않고 그냥 넘어간다.

 

위 코드에서 index는 arr의 절대적인 index이고 count는 시작위치에서 타겟을 찾을때까지 실제 카운팅index라고 생각하면 된다. 그래서 -1(빈 곳)을 만날 경우 index는 ++해주고 count는 ++해주지 않는다.

index가 n값(크기)를 넘어설경우 다시 1로 되돌아가게 해주는 보정도 당연 해준다. (원형큐니까)

 

이후 front위치에서 타겟까지의 거리를 의미하는 count값이 큐크기의 절반이하일 경우 해당값을 그대로 answer에 합산을 해준다. 큐크기의 절반값을 초과한다면 왼쪽회전하는것보다 오른쪽회전하는게 더 싸게먹히기 때문에 오른쪽회전값을 합산해주면 된다.