파이썬을 이용한 연결리스트 기본 구현 테크닉 배우기

31423번: 신촌 통폐합 계획 (acmicpc.net)

31423번: 신촌 통폐합 계획

 

문제는 단순한데 s[i] 뒤에 s[j]를 그대로 붙이고, s[j] = 0으로 만든다.

 

이를 n-1번 순서대로 반복해서 얻은 결과를 출력하면 된다

 

from sys import stdin

n = int(stdin.readline())

s = [0]

for _ in range(n):
    
    c = stdin.readline().rstrip()
    s.append([c])

for _ in range(n-1):
    
    i,j = map(int,stdin.readline().split())

    s[i].append(s[j][0])
    s[i] = [''.join(s[i])]
    s[j] = 0

print(''.join(s[i]))

 

 

이렇게 하면 O(N)정도라 시간초과 안나는거 아닌가? 생각했는데 시간초과 나더라고

 

찾아보니 ''.join()이 O(1)이 아니고 문자열 길이 N만큼 O(N)이라고 하더라

 

그래서 전체 시간복잡도가 $O(N^{2})$

 

N이 50만이니 이렇게 단순하게 접근하면 시간초과날것 같고

 

생각할 수 있는 방법은 문자열을 붙이는 순서를 O(N)으로 미리 찾고

 

마지막에 찾은 순서를 차례대로 순회해서 붙여주면 될것 같다

 

2,3

 

1,2

 

4,5

 

1,4를 쿼리로 받는다면..?

 

2 > 3으로 연결시키고 1,2를 받는다면 1 > 2로 연결시키는데...

 

여기서 2 > 3이 있으니까 1 > 2 > 3으로 연결시키고, 4,5를 받는다면 4 > 5가 된다.

 

여기에 1,4를 받으면 1 > 4가 될것인데...

 

이미 1 > 2 > 3 상태라서, 1 > 2 > 3 > 4로 받아줘야한다. 

 

그리고 여기에 1 > 2 > 3 > 4 > 5로 연결시켜줘야할 것이다. 이 과정을 구현하면 되는데

 

파이썬 dict로 구현해보면 2 > 3은 d[2] = 3이고 1 > 2는 d[1] = 2로 연결시키고.. 

 

그런데 여기서 1 > 2 > 3이 될텐데 문제는 1,4를 받을때 1 > 2 > 3 > 4가 되도록 해야하는데..

 

3 뒤에 4를 연결시켜야하는데 1의 마지막이 어디인지를 1 > 2 > 3 차례대로 순회하면 매우 느릴것 같다

 

그래서 1에 붙은 마지막 3을 바로 찾을 수 있도록 dict를 하나 더 써야할 것 같다..

 

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

 

여기서 초기 셋팅이 매우 중요하다.

 

1,2,3,4,...,n이 있다고 할때, 각각을 자기 자신과 연결시킨다

 

이게 핵심 테크닉

 

이걸 안하면 구현이 뭔가 꼬이더라

 

 

 

그리고 2,3이 들어온다고 하자. 2 > 3으로 연결시키는데

 

2의 마지막 부분에 3을 연결시켜야한다.

 

2의 마지막부분은 현재 2 자기 자신이다.

 

그래서 2 바로 뒤에 3을 연결시키게 될 것이고 

 

연결시키고 나서 2번의 마지막 부분을 2번 자기자신이 아니라 3번으로 연결시켜준다.

 

 

 

다시 1,2가 들어온다면... 1 > 2를 연결시켜준다.

 

1 뒤에 2를 연결시켜줘야하는데 1의 마지막에 2를 연결시켜줘야한다.

 

1의 마지막은 지금 1 자기 자신이다. 그래서 1 바로 뒤에 2를 연결시켜주고나서...

 

1의 마지막을 바꿔줘야는데..

 

1의 마지막이 3이라는건 어떻게 찾을 수 있을까?

 

1과 바로 연결된 2의 마지막이 3이다.

 

따라서 1과 바로 연결된 2의 마지막을 1의 마지막에 연결시켜주면 된다.

 

 

 

비슷하게 4 > 5가 들어온다면.. 1,2,3과는 아무런 상관이 없으니까 

 

 

 

그리고 1 > 4가 들어온다면..?

 

1 뒤에 4를 연결시키는데.. 1 뒤에 연결시킨다는건 1의 마지막인 3 뒤에 연결시킨다는 것이다.

 

1의 마지막은 3이라는걸 바로 알 수 있고, 4와 연결시켰으니.. 1의 마지막을 4의 마지막에 연결시킨다.

 

 

그래서 최초 모든 i = 1,2,3,..,n에 대하여 i의 꼬리부분을 자기 자신 i로 연결

 

쿼리 i,j가 들어올때 i > j로 연결시켜야한다.

 

i의 뒤에 j를 연결시키는데 i의 꼬리부분 link2[i] 바로 뒤에 j를 연결

 

연결하고 나면 i의 꼬리부분 link2[i]은 j의 꼬리부분 link2[j]가 될 것이다.

 

from sys import stdin

n = int(stdin.readline())

s = [0]

for _ in range(n):
    
    c = stdin.readline().rstrip()
    s.append(c)

link1 = {} #i의 바로 뒤(next)
link2 = {} #i의 마지막 부분(tail)

#i > i
#i번 자기 자신이 i번의 마지막부분
for i in range(1,n+1):
    
    link2[i] = i

for _ in range(n-1):
    
    i,j = map(int,stdin.readline().split())
    
    #i > a1 > a2 > ... > ak > link2[i]
    #j > b1 > b2 > ... > bk > link2[j]

    #i > ... > link2[i] > j > .... > link2[j]

    #i > ... > (link2[i] = link2[j])
    
    #i,j가 들어온다면 i > j로 연결시켜줘야함
    #i의 마지막부분(link2[i]) 바로 뒤에 j를 연결시켜줘야함
    link1[link2[i]] = j
    
    #연결하고 나서, i의 마지막 부분을 변경시켜줘야한다.
    #j와 연결되었으니 j의 마지막부분(link2[j])이 i의 마지막부분(link2[i])이 된다
    link2[i] = link2[j]

 

 

이제 모든 문자열 붙이는 순서를 찾았다.

 

for문이 끝나고 i번이 문자열의 시작 순서가 될 것이다.

 

i번부터 시작해서 link1을 타고 들어가 문자열을 차례대로 붙인다

 

물론 매번 붙이면 $O(N^{2})$이 될것이니까 리스트에 부분 문자열만 차례대로 담아두고

 

끝나고 나서 한번에 join하자

 

answer = []

while 1:

    answer.append(s[i])
    
    if link1.get(i,0) == 0:
        
        break
        
    i = link1[i]

print(''.join(answer))

 

 

이렇게 매번 join하면 매번 O(N)이라 전체는 $O(N^{2})$이라 시간초과

 

answer = []

while 1:

    answer.append(s[i])
    answer = [''.join(answer)]
    
    if link1.get(i,0) == 0:
        
        break
        
    i = link1[i]

print(''.join(answer))