[코딩테스트] List of Unique Numbers

출처: https://www.acmicpc.net/problem/13144

풀이전에 할 말

이 문제는 백준 기준 골드3 에 해당하는 문제입니다. 만만치않다는 뜻이겠죠?

일단 문제 분석부터 해보겠습니다. 일단 메모리 제한이 32MB로 넉넉치않게 주어진 모습을 확인할 수 있습니다. 이 뜻은, 이 문제를 풀이하면서 최대한 변수 할당을 줄여야한다는 뜻입니다. 그러면 DP적인 풀이가 요구되겠죠?

그리고 시간 제한이 1초이고, 수열의 길이 N은 100000까지 제한이 되어있는 모습입니다. 당연히 O(N^2)의 복잡도는 사용하지 못하고, 선형으로 탐색하거나, 혹은 O(NlogN)의 복잡도로 해결해야한다는 뜻입니다.

그런데 이 문제는 투포인터 기법으로 풀이하기에는 많이 빡세보입니다. 투 포인터로 풀려고 했다가 1시간 날린거는 안 비밀
투포인터로 풀기 위해서는 중복되는 숫자를 이분탐색을 통해서 찾아내야하는데, 문제는 탐색해야하는 케이스가 생각보다 풀다보면 많이 불어난다는 것입니다.

게다가 투포인터로 어떻게든 풀어도 복잡도가 자연스럽게 커지기 때문에 실패의 확률이 매우 높습니다.

import sys

input = sys.stdin.readline

N = int(input())
number_list = list(map(int, input().split()))
checked = [False] * 100001 # 0부터 100000까지 숫자가 check 되었는지 검사하기 위한 리스트
count = 0

for i, number in enumerate(number_list):
    start, end = i + 1, N - 1
    mid = 0
    signal = False
    checked[number] = True
    
    while start <= end:
        mid = (start + end) // 2
        target_idx = 0
        
        for j in range(start, mid + 1):
            if checked[number_list[j]] == True:
                signal = True
                target_idx = j
                break
            else:
                checked[number_list[j]] = True
                
        # 탐색을 종료시킨다
        if signal == True:
            count += (j - i)
            checked = [False] * 100001
            break
        
        else:
            start = mid + 1 # 기존에 탐색하지 않았던 범위를 탐색하기 때문에 checked를 초기화하지 않는다
            
    # 겹치는 숫자들 찾지 못하는 경우
    if start > end:
        count += (N - i)
        checked = [False] * 100001
        
print(count)

위의 풀이는 제가 이분탐색을 이용한 풀이입니다. 위의 풀이는 O(NlogN)의 복잡도가 아니라, $O(N^2logN)$의 복잡도를 가지고 있습니다. $O(N^2)$의 복잡도도 허용이 되지 않는데 $O(N^2logN)$ 의 복잡도를 사용했으니 당연히 틀리겠죠?

그래서 저는 생각을 바꿨습니다. 굳이 투 포인터에 얽매이지 말자 라는 생각을 가졌습니다. 아래에 제 생각을 기술하겠습니다.

그래서 어떻게 풀어냈는데?

저는 위의 문제를 선형 탐색을 이용해서 풀자 라고 생각을 했습니다. 풀이 과정은 다음과 같습니다.

1-1. 앞에서부터 숫자를 읽어들인다. 읽어들인 숫자가 이미 탐색이 된 숫자가 아닌 경우에는, 가능한 경우이기 때문에 sequence에 추가시킨다.
1-2. 탐색이 되지 않았던 숫자를 넣었다면, 수열(sequence)에 담겨있는 숫자이기 때문에 방문했다는 표식을 남긴다.
2-1. 만약에 이미 탐색된 숫자를 읽어들였다면, 지금까지의 수열 길이를 count에 반영시킨다.
2-2. 그리고 다음 수열의 맨 앞 숫자를 pop시킨다. 그리고 pop된 숫자는 수열에 없기 때문에 checked에서 풀어버린다.

위의 풀이는 합리적입니다. 그 이유를 예시를 통해 알려드리겠습니다.

🌈 예제 입력

6
1 2 3 5 2 1

위처럼 입력이 들어왔다고 해봅시다. 그러면 다음의 과정을 거칠것입니다.

1. [1, 2, 3, 5]까지 sequence에 저장이 되고, 다음 차례에 2를 탐색할 것입니다.
2. 2를 탐색하려고 봤더니, 2는 이미 sequence에 있습니다. 따라서 count에 4를 더하고, 1을 pop 시킵니다.
3. 그 다음에 2를 탐색했더니, 2도 이미 sequence에 잔존해있습니다. 따라서 count에 3을 더하고, 2를 pop 시킵니다.
4. 이제 2를 넣을 수 있습니다. 따라서 2를 sequence에 추가시킵니다. 여기까지 sequence는 [3, 5, 2] 입니다.
5. 1은 sequence에 없기 때문에 1을 추가시킵니다. 탐색을 끝냅니다.
6. 이제 짬처리를 합니다.

위의 과정은 총 $O(N)$ 의 복잡도를 가집니다.

그런데 이런 의문이 들 수 있습니다. 짬처리 하는 과정에서 복잡도가 상승할 수 있지 않아요? 그런데 짬처리 과정은 $O(1)$의 복잡도를 가집니다. 왜냐하면, 짬처리 과정에서는 다음의 수식이 사용되기 때문입니다.

$(1/2)n(n+1)$

왜냐하면, 짬처리 결과의 수열에는 중복된 숫자가 없기 때문에 1부터 수열의 길이까지 합을 계산해서 count에 더하면 됩니다.

이제 저의 코드를 감상해보시죠.

코드를 감상하시죠. 허무할 수도 있습니다!

import sys

input = sys.stdin.readline

N = int(input())
number_list = list(map(int, input().split()))
checked = [False] * 100001 # 0부터 100000까지 숫자가 check 되었는지 검사하기 위한 리스트
count = 0

start, end = 0, N - 1
sequence = [] # 수열을 담을 리스트

while start <= end:
    # 기존에 check된 숫자인지 검사
    if checked[number_list[start]] == False:
        checked[number_list[start]] = True
        sequence.append(number_list[start])
        start += 1
    else:
        count += len(sequence) # 길이만큼 카운트 수 증가
        removed_number = sequence.pop(0) # 제일 앞의 숫자를 pop
        checked[removed_number] = False # checked 해제
        
# 마지막에 남은 sequence 짬처리
remained = len(sequence)
count += remained * (remained + 1) // 2

print(count)

수열에 숫자가 담겨있는 경우에는 checked에 정보를 새깁니다. 그리고 while문을 돌면서 checked를 바라보게 하여 탐색하고자 하는 인덱스(start)에 해당하는 숫자가 이미 수열에 존재하는지 검사를 해봅니다.

그 외의 메커니즘은 위에서 설명한 그대로입니다.

위의 코드를 통해서 저는 $O(N)$의 복잡도로 문제를 해결했습니다.