[🥇5 / 백준 31423 / 파이썬] 신촌 통폐합 계획

 

 

 

31423번: 신촌 통폐합 계획

 

문제

극단적인 출산율 감소로 인해 신촌 지역 N개 대학교가 하나의 학교로 통합되었다.

기나긴 회의 끝에, 통합된 학교의 이름은 N개 대학교의 이름을 이어 붙여서 정해졌다. 회의에서 통합된 학교의 이름을 정한 방법은 다음과 같다.

 N개 대학교의 이름 s₁,s₂,⋯,s_N을 일렬로 나열한다. 이후 다음의 과정을 N−1번 반복한다.

1.  s_i,s_j가 빈 문자열이 아닌 서로 다른 두 정수 i,j를 고른다.
2.  s_i의 뒤쪽에 s_j를 이어 붙인다.
3.  s_j를 빈 문자열로 바꾼다.

모든 과정이 끝난 뒤에는 빈 문자열이 아닌 s_k가 하나 남게 되며, 이때 s_k가 통합된 학교의 이름이 된다.

 N개 대학교의 이름 s₁,s₂,⋯,s_N과 회의에서 고른 i,j가 순서대로 주어질 때, 회의를 통해 정해진 통합된 학교의 이름을 구하는 프로그램을 작성해 보자.

 

입력

첫 번째 줄에 대학교의 개수 N이 주어진다. (2≤N≤500000)

다음 N개의 줄의 i번째 줄에 대학교 이름을 의미하는 알파벳 소문자로 이루어진 문자열 si가 주어진다. 주어지는 대학교 이름의 길이 합은 500000을 넘지 않는다.

다음 N−1개의 줄에 회의에서 고른 i,j가 공백을 사이에 두고 차례로 주어진다. (1≤i,j≤N; i≠j) 

주어지는 순서대로 회의를 진행할 때 s_i,s_j가 빈 문자열이 아닌 i,j만 입력으로 주어진다.

 

출력

첫 번째 줄에 회의를 통해 정해진 통합된 학교의 이름을 출력한다.

 

예제 입력 5 sogang sookmyung yonsei ewha hongik 2 3 1 2 4 5 1 4

예제 출력 sogangsookmyungyonseiewhahongik

 

 

풀이

 

실제로 문자열을 이어나가는 방식으로 문제를 해결하려 하면 문자열을 이어붙이는 과정에서 O(N^2)의 시간이 소요될 것이다.

따라서 실제로 문자열을 이어붙이지는 않고, 연결리스트 형태로 이어 붙여나가는 순서만 기록한 뒤, 마지막에 한 번만 순서대로 문자열을 합쳐 출력해야 한다.

 

단, 문자열 덩어리를 합칠 때 next로 추적하여 문자열 덩이의 tail을 추적하려 하면 마찬가지로 O(N^2)의 시간복잡도를 가지게 되므로 tail을 따로 기록하는 방식으로 풀어나가야 한다.

 

import sys
input = sys.stdin.readline

n = int(input())
colleges = [""] + [input().rstrip() for _ in range(n)]
next = [-1] * (n+1)
tail = [i for i in range(n+1)]

for _ in range(n-1):
    x, y = map(int, input().split())
    next[tail[x]] = y
    tail[x] = tail[y]

result = []
for _ in range(n):
    result += colleges[x]
    x = next[x]
print("".join(result))