코딩테스트 복기 -오프라인 쿼리를 이용한 놀라운 배열 재배치-

1. 문제

 

1부터 n까지 적힌 카드가 아래에서부터 위로 순서대로 쌓여있다.

 

이제 다음과 같은 질문이 주어진다.

 

x : 카드 뭉치에서 x번이 적힌 카드를 찾아 맨 아래로 내린다.

 

-x : 카드 뭉치에서 x번이 적힌 카드를 찾아 맨 위로 올린다.

 

예를 들어 n = 5라고 하자.

 

카드가 [1,2,3,4,5]로 쌓여있다고 표현할 수 있고 [3,-2,1,-4,-5] 순서대로 질문이 주어진다.

 

3이 주어지면, [1,2,3,4,5]에서 3을 찾아 맨 아래로 내리면 [3,1,2,4,5]

 

-2가 주어지면 [3,1,4,5,2]

 

1이 주어지면 [1,3,4,5,2]

 

-4가 주어지면 [1,3,5,2,4]

 

-5가 주어지면 [1,3,2,4,5]

 

최종 상태는 [1,3,2,4,5]가 된다.

 

n개의 카드가 순서대로 쌓여있는 상태에서 q개의 질문이 주어질때, 모든 질문이 끝나고 난 뒤의 최종 상태를 출력하는 프로그램을 작성하라

 

2. 제한

 

$1 \leq n \leq 500000$, $1 \leq q \leq 500000$, $1 \leq x \leq n$

 

이전에 3이라는 query가 주어지면, -3이라는 query가 주어질 수 있으며, 중복해서 주어질 수도 있다.

 

 

3. 풀이

 

사실 가장 쉬운 방법?은 매 순간 배열에서 x를 찾아서 x를 제거하고 x > 0 이면 맨 앞에 삽입하고

 

x < 0 이면 맨 뒤에 삽입하는건데

 

당연히 x를 찾는 과정이 O(N)이며 제거하는 것도 O(N)일거고 삽입하는것도 맨 뒤에 삽입하면 O(1)이겠지만 맨 앞에 삽입하면 O(N)이다..

 

N,Q가 500000이면 최악의 경우 평생해도 안끝나겠는데

 

나는 스택을 이용해서 풀긴했지만.. 로직이야 깔끔해도 $O(N^{2})$인건 마찬가지라...

 

 

4. 온라인 쿼리와 오프라인 쿼리

 

온라인 쿼리는, 쿼리를 받을때마다 그 때 그 때 쿼리에 답을 하는 방법이고

 

오프라인 쿼리는, 그 때 그 때 쿼리에 답을 하지 않고,

 

어떤 식으로든지 내가 유리한 방향대로 쿼리를 재배치해서 답을 하는 테크닉이다.

 

핵심은 쿼리가 주어짐과 동시에 답을 해야한다는 생각부터 버려야 할때가 있다는 것

 

쿼리를 미리 다 받아놓고, 거꾸로 쿼리를 답하든지, 어떤 식으로든 다른 방법으로도 답을 할 수 있다는 테크닉을 익히는게 중요

 

 

5. 오프라인 쿼리를 이용한 풀이

 

쿼리가 주어질때마다 배열을 재배치하지 말고, 일단 모든 쿼리를 다 받아보자.

 

n = 10이고 q = 7인데 [3,-2,4,-1,-9,2,7]이라고 해보자.

 

[1,2,3,4,5,6,7,8,9,10]에서 3을 찾아서 [3,1,2,4,5,6,7,8,9,10]이라고 생각하지 말고..

 

그냥 배열이 비어있는 상태에서 [3,-2,4,-1,-9,2,7]을 각각 처리하면 어떻게 되는지 생각해보자

 

3을 받으면, [3,0,0,0,0,0,0,0,0,0]

 

-2를 받으면, [3,0,0,0,0,0,0,0,0,2]

 

4를 받으면, [4,3,0,0,0,0,0,0,0,2]

 

-1을 받으면, [4,3,0,0,0,0,0,0,2,1]

 

-9를 받으면, [4,3,0,0,0,0,0,2,1,9]

 

2를 받으면, [2,4,3,0,0,0,0,0,1,9]

 

7을 받으면, [7,2,4,3,0,0,0,0,1,9]

 

그리고 나머지 비어있는 0,0,0,0에는 그동안 안넣은 5,6,8,10을 차례대로 넣으면 될 것 같다

 

[7,2,4,3,5,6,8,10,1,9]

 

실제로 [1,2,3,4,5,6,7,8,9,10]에서 [3,-2,4,-1,-9,2,7]을 수행한다고 생각해보자. 정말로 저렇게 되나?

 

3을 받으면 [3,1,2,4,5,6,7,8,9,10]

 

-2를 받으면 [3,1,4,5,6,7,8,9,10,2]

 

4를 받으면 [4,3,1,5,6,7,8,9,10,2]

 

-1을 받으면 [4,3,5,6,7,8,9,10,2,1]

 

-9를 받으면 [4,3,5,6,7,8,10,2,1,9]

 

2를 받으면 [2,4,3,5,6,7,8,10,1,9]

 

7을 받으면 [7,2,4,3,5,6,8,10,1,9]

 

-----------------------------------------------------------------------------------------------------

 

조금 더 생각해서 1~n까지 만들어놓은 배열에서 각 질의에 해당하는 답을 찾아서 앞,뒤로 재배치하지 말고,

 

query를 전부 받은 다음에 query 리스트를 순회해가지고 양수라면 앞에 채워넣고,

 

음수라면 뒤에 순서대로 채워넣고, 나머지 빈 부분에는 지금까지 넣지 않았던 숫자를 채워넣는다.

 

그런데 이미 넣었던 숫자가 또 나온다면, 이전에 넣은 위치를 제거하고 해당 질의에 맞는 위치에 넣어줘야한다.

 

이 부분이 아쉽다.

 

이미 나온 질의에 해당하는 질의가 또 나온다면, 이미 넣은 숫자의 위치를 또 찾아서, 다시 넣어야하니까

 

-----------------------------------------------------------------------------------------------------

 

중복된 질의는 마지막으로 어디에 위치할까?

 

매 질의마다 답을 하지 않고, 모든 질의를 다 안 상태에서 정답을 구성하는 이 상황에, 질의에 순서대로 답할 필요가 있을까?

 

동일한 질의가 여러번 나온다면, 결국 마지막에 나온 질의의 답이 해당 숫자의 최종 위치가 된다

 

마지막에 나온 질의일수록, 숫자는 맨 앞, 맨 뒤에 위치하게 된다.

 

[3,1,2,-3,2,-1,3]으로 질의가 구성된다면?

 

3을 맨 앞에 두다가, -3이 나오면 3을 다시 뒤에 두다가, 3이 또 나오면 뒤에 둔 3을 맨 앞에 두니

 

[3,0,0,0,0,0,0,0,0,0]

 

다시 1을 맨 앞에 두다가 -1이 나오면 1을 맨 뒤에 두니

 

[3,0,0,0,0,0,0,0,0,1]

 

2가 나오면 맨 앞에 두다가, 다시 2가 또 나오면 2를 맨 앞에 두니

 

[2,3,0,0,0,0,0,0,0,1] 

 

1,2,3이 중복해서 나오고 있지만 결국 맨 뒤에 있는 쿼리 2,-1,3에만 답하면 그것이 최종 정답이 된다는 사실을 알 수 있다

 

[3,1,2,-3,2,-1,3]을 거꾸로 순회해서,

 

3이 나오면 [3,0,0,0,0,0,0,0,0,0]

 

-1이 나오면 [3,0,0,0,0,0,0,0,0,1]

 

2가 나오면 [2,3,0,0,0,0,0,0,0,1]

 

그리고 -3이 나오면 3은 이미 넣었으니 스킵, 2가 나오면 2는 이미 넣었으니 스킵, 1이 나오면 1은 이미 넣었으니 스킵,

 

3이 나오면 3은 이미 넣었으니 스킵

 

따라서 query를 거꾸로 순회해서 빈 배열을 구성하는 방식으로 접근하면 적어도 O(q)에 모든 쿼리에 답을 할 수는 있다.

 

그 다음 마지막 빈 부분에는 지금까지 넣지 않은 숫자를 순서대로 채워넣어야 하면서, 어차피 이미 넣은 숫자는 스킵시켜야하니

 

visited배열을 사용해서 이미 넣은 숫자는 기록해놓는다면, 모든 query에 답하고 나서,

 

O(N)으로 1부터 n까지 순회해서 query에 등장하지 않은 숫자를 순서대로 채워넣는다면, O(N+q)에 문제를 해결할 수 있다.

 

#offline query
#query마다 배열을 재배치

n,q = map(int,input().split())

#query에 답하지 않고 모든 query를 일단 구성한다
query_list = []

for _ in range(q):
    
    x = int(input())
    query_list.append(x)

visited = [0]*(n+1)

answer = [0]*n

left = 0
right = -1

#query를 거꾸로 순회해서, 빈 배열 answer에 채워 넣는다.
for i in range(q-1,-1,-1):
    
    x = query_list[i]
    
    #x가 양수라면, 왼쪽부터 차례대로 채워넣는다.
    if x > 0:
        
        #이미 기록한 숫자라면 스킵
        if visited[x] == 1:
            
            continue
        
        else:
            
            #마지막에 나온 양수 query일수록 맨 왼쪽에 배치된다.
            #거꾸로 순회하기 때문에 다음 query에 채워넣을때는 left + 1에 채워넣기만 하면 된다
            answer[left] = x
            left += 1
            visited[x] = 1 #이미 나온 숫자인지 확인하기 위해
    
    #음수라면 오른쪽부터 채워넣는다
    elif x < 0:
        
        #이미 나온 숫자라면 스킵
        if visited[-x] == 1:
            
            continue
        
        else:
            
            #마지막에 나온 음수 query일수록 맨 오른쪽에 배치된다.
            #거꾸로 순회하기 때문에 다음 query에 채워넣을때는 right - 1에 채워넣기만 하면 된다
            answer[right] = -x
            right -= 1
            visited[-x] = 1

#query에 등장하지 않아 아직 채워넣지 않은 숫자를 왼쪽부터 채워넣는다
for i in range(1,n+1):
    
    if visited[i] == 0:
        
        answer[left] = i
        left += 1

print(*answer)

 

query를 뒤에서부터 순회하는 또 다른 장점은 위 코드 구현에서 확인할 수 있다

 

마지막 query에 답할수록 맨 앞, 맨 뒤에 배치된다는 특징을 이용한다면

 

거꾸로 순회할때, 먼저 나온 양수 쿼리는 맨 왼쪽에 배치하고,

 

다음에 나올 양수 쿼리는 인덱스를 1 증가시켜 left + 1에 배치하면 된다

 

음수 쿼리도 마찬가지다. 먼저 나온 음수 쿼리는 맨 오른쪽에 배치하고

 

다음에 나올 음수 쿼리는 인덱스를 1 감소시켜 right - 1에 배치하면 된다..

 

query_list 50만개를 랜덤으로 구성해서 최악의 경우 돌려보면 0.3초만에 해결 가능

 

O(100만)이라 1초안에는 돌것 같다..

 

 

진짜 경이롭다...

 

쿼리를 다 구성해놓고 답을 할 수 있다는 생각은 전혀 못해봄