persistent linked list이용한 문자열 변화 추적하기

1. persistent linked list

 

“퍼시스턴트(Persistent) 연결 리스트”는 한 번 만든 리스트를 “불변(immutable)”으로 유지하면서도, 수정할 때마다 과거 버전까지 그대로 보존할 수 있게 해 주는 연결 리스트입니다.

 

1) 왜 ‘퍼시스턴트’인가?

• 일반 연결 리스트는 노드 값을 바꾸거나 추가·삭제하면 기존 상태가 없던 일처럼 사라집니다.
• 반면 퍼시스턴트 리스트는 “이전 상태”를 그대로 남겨 두고, 수정 후 새 리스트 버전을 만들어 줍니다.
• 즉, 여러 시점(version)의 리스트를 동시에 관리할 수 있죠.

 

2) 어떻게 불변성을 지키나?

1. 노드는 절대 수정하지 않는다.
2. 새로운 내용만 새 노드로 생성하고,
3. 변경되지 않은 구간은 **기존 노드를 그대로 재사용(공유)**한다.
4. 각 버전은 “헤드 포인터(head)”만 달리 갖고 있게 된다.

 

 

2. 연습문제

 

https://atcoder.jp/contests/abc411/tasks/abc411_d

D - Conflict 2

 

 

서버 1대와 n개의 PC가 있다.

 

서버와 PC는 각각 문자열을 가지고 있으며 초기에는 빈 문자열이다.

 

Q개의 쿼리가 주어진다.

 

1 p는 p번째 PC의 문자열을 서버의 문자열로 대체한다.

 

2 p s는 p번째 PC의 문자열 끝에 문자열 s를 추가한다.

 

3 p는 서버의 문자열을 p번째 PC의 문자열로 대체한다.

 

모든 쿼리를 처리하고 나서 서버의 문자열을 구하라.

 

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

 

node[i]는 (p,s)로 노드번호 p가 문자열 s를 일부로 가지고 있다는 뜻

 

PC[i]는 i번째 PC가 현재 가리키고 있는 노드번호

 

server는 서버가 가리키고 있는 노드번호

 

쿼리를 순회하여 1 p는 p번째 PC의 문자열을 server의 문자열로 대체하므로,

 

p번째 PC가 가리키고 있는 노드랑 서버가 가리키고 있는 노드를 동일하게 하면..

 

PC[p] = server

 

2 p s는 node에 새로운 노드를 추가한다.

 

(p번째 PC가 가리키고 있는 노드번호 PC[p],s)를 추가하고

 

그리고 p번째 PC는 추가된 노드인 PC[p] = node[-1]을 가리키도록 한다.

 

3 p는 서버가 가리키고 있는 노드번호를 p번째 PC가 가리키고 있는 노드번호로 바꾼다. server = PC[p]

 

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

node = [(0,"")]
PC = [0]*(n+1)
server = 0

for _ in range(q):
    
    Q = input().split()

    a = Q[0]
    p = int(Q[1])

    if a == '1':
        
        PC[p] = server
    
    elif a == '2':
        
        s = Q[2]

        node.append((PC[p],s))
        PC[p] = len(node)-1
    
    else:
        
        server = PC[p]

answer = []

now = server

while now != 0:
    
    prev,s = node[now]
    answer.append(s)
    now = prev

print(''.join(answer[::-1]))

 

 

예를 들어서, 

 

2 6
2 1 at
3 1
2 2 on
1 2
2 2 coder
3 2

 

 

초기에는 모든 PC가 0번 노드를 가리키고 있고, 0번 노드는 빈 문자열을 가지고 있다.

 

 

 

 

2 1 at은 1번 PC의 끝에 at을 붙인다는 의미이다.

 

node에 (PC[1],at)을 새롭게 추가하자. 그리고 최근에 추가된 1번 노드를 가리키도록 한다.

 

그러면 다음 그림과 같이, 1번 PC는 1번 노드를 가리키고 있고, 1번 노드는 0번 노드와 연결되어 있다.

 

 

 

 

3 1은 서버를 1번 PC가 가리키고 있는 노드로 연결시킨다.

 

 

 

 

2 2 on은 2번 PC에 on을 붙인다는 뜻으로, node에 (PC[2],on)을 붙인다.

 

PC[2] = 0이므로, 2번 노드는 0번 노드와 연결된다.

 

 

 

 

1 2는 2번 PC를 서버가 가리키고 있는 노드로 연결시킨다.

 

 

 

 

2 2 coder은 2번 PC의 끝에 coder을 붙인다.

 

새로운 노드에 (PC[2],coder)을 추가한다. PC[2] = 1이므로, (1,coder)가 추가된다.

 

그리고 PC[2]를 새로 추가된 노드로 연결시킨다.

 

따라서, 2번 PC는 node[3]의 coder에 붙고, node[3]이 node[1]과 연결되어 있어서 at도 붙는다.

 

 

 

 

2 1 at은 1번 PC에 at을 붙인것

 

1번 PC = at

 

3 1은 서버에 1번 PC 문자열을 복사하므로, 현재 서버는 at

 

2 2 on은 2번 PC에 on을 붙이므로 2번 PC = on

 

1 2는 서버의 문자열을 2번 PC에 복사하므로, 2번 PC = at

 

2 2 coder은 2번 PC 끝에 coder을 추가하므로, 2번 PC = atcoder

 

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

 

현재 1번 PC = at

 

서버  = at

 

2번 pc = atcoder

 

현재 자료구조상으로도, 2번 PC는 3번 노드 coder로 가고, 3번 노드는 1번 노드 at으로 가고 있고,

 

1번 노드는 0번 노드 빈 문자열로 가므로, 

 

빈 문자열을 만날때까지 노드를 거슬러 올라간 다음, 문자열을 거꾸로 붙이면 된다는 것을 알 수 있다.

 

coder > at > "" 

 

>>> atcoder

 

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

 

이제 3 2는 서버가 가리키고 있는 노드를 2번 PC가 가리키고 있는 노드로 연결

 

 

 

마지막으로 서버부터 시작해서 거슬러 올라가면 된다.

 

서버는 2번 PC를 가리키고, 2번 PC는 3번 노드를 가리키고 있고, 3번 노드는 coder, 3번 노드는 1번 노드로 가서 at,

 

1번 노드는 0번 노드 빈 문자열을 가지고 있어서, 이를 역으로 붙이면 atcoder가 된다.

 

 

3. 다른 풀이

 

f(t,i)를 쿼리 t까지 처리하고 나서 i번 PC가 가지고 있는 문자열이라고 하자.

 

여기서 0번 PC는 서버이다.

 

쿼리 t가 1 p라면, p번째 PC는 이전 쿼리 t-1에서 처리된 서버의 문자열을 가지므로 f(t,p) = f(t-1,0)

 

그리고 p가 아닌 PC는 이전 쿼리의 문자열을 그대로 가져오므로 f(t,i) = f(t-1,i)

 

쿼리 t가 2 p s라면, f(t,p) = f(t-1,p) + s

 

마찬가지로 p가 아닌 PC는 이전 쿼리를 그대로 가져와서 f(t,i) = f(t-1,i)

 

쿼리 t가 3 p라면 서버의 문자열을 p번째 PC 문자열로 가져오므로, f(t,0) = f(t-1,p)

 

마찬가지로 p가 아닌 PC는 f(t,i) = f(t-1,i)

 

구하고자 하는 것은 f(Q,0)이다.

 

쿼리를 역순으로 Q,Q-1,Q-2,...,1로 살펴보면서 f(0,i) = ""을 이용해서 해결할 수 있다.

 

f(q,0) = f(q-1,i1) = f(q-2,i2) = ..... = f(t,i) = .... = f(0,i) + ...형태가 되므로

 

구체적으로 t = Q, i = 0, answer = 빈 문자열로 초기화

 

t가 1 p이고 i = p라면, i = 0

 

2 p s이고 i = p라면, answer = s + answer

 

3 p이고 i = 0이라면, i = p

 

그리고 t = t-1

 

t = 0이면 알고리즘 종료

 

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

query = []

for _ in range(q):
    
    Q = input().split()

    t = Q[0]
    p = int(Q[1])

    if t == '1' or t == '3':
        
        query.append((int(t),p,''))
    
    else:
        
        s = Q[2]

        query.append((int(t),p,s))

answer = []
i = 0 #f(q,0)

#f(q,0) = .... = f(t,i)
#f(t,i) = f(t-1,0), a = 1, i = p
#f(t,i) = f(t-1,i) + s, a = 2, i = p
#f(t,i) = f(t-1,p), a = 3, i = 0
for t in range(q-1,-1,-1):
    
    a,p,s = query[t]

    if a == 1:
        
        if i == p:
            
            i = 0
    
    elif a == 2:
        
        if i == p:
            
            answer.append(s)
    
    else:
        
        if i == 0:
            
            i = p

answer = answer[::-1]
print(''.join(answer))

 

 

일종의 다이나믹 프로그래밍이라고 봐야겠지?

 

원래 2번 쿼리는 앞에다 붙여야하는데(거꾸로하니까)... 

 

일단 뒤에다 붙인 다음 마지막에 거꾸로 해서... 하면 시간복잡도를 줄일 수 있는