BOJ 30191 문자열 만들기 1

https://www.acmicpc.net/problem/30191

30191번: 문자열 만들기 1

문제

이번 학기 물리학실험의 조교장을 맡은 서현이는 학생들의 성적을 입력하는 일을 하고 있다.

서현이가 맡은 분반의 학생 수는 N명이고, 이 중 정확히 절반에 해당하는 학생들은 S, 나머지 절반의 학생들은 U를 받게 된다. N은 항상 짝수이다.

1번 학생, 2번 학생, ⋯, N번 학생이 받을 성적이 길이 N인 문자열 T로 주어진다. 서현이가 할 일은 이 문자열을 전산 시스템에 입력하는 것이다.

서현이는 다음 시행만을 반복하여 학생들의 성적을 입력하려고 한다.

1. 현재 커서의 위치에 SU 를 추가한다.
2. 커서가 맨 왼쪽에 있지 않은 경우, 커서를 왼쪽으로 한 글자 움직인다.
3. 현재 커서의 위치에 US 를 추가한다.

처음 상태는 빈 문자열이며, 커서는 매 순간 문자열의 맨 앞이나 맨 끝, 또는 글자와 글자 사이에 위치한다. 1번 시행과 3번 시행이 끝난 뒤, 커서는 추가된 문자열의 바로 뒤로 이동한다.

서현이를 위해, 시행을 최대 2N번 사용하여 학생들의 성적을 모두 입력하는 방법을 하나 찾아주자!

입력

첫째 줄에 문자열의 길이 N이 주어진다. (2 ≤ N ≤1,000,000 , N은 짝수)

둘째 줄에 학생들의 성적을 나타내는 S와 U로만 이루어진 문자열 T가 주어진다. T에서 S와 U의 개수는 같다.

출력

첫째 줄에 시행의 횟수 K를 출력한다. (0 ≤ K ≤ 2N)

둘째 줄에 서현이의 시행을 나타내는 길이 K의 문자열을 출력한다. 1번 시행은 S, 2번 시행은 N, 3번 시행은 U로 나타낸다. 커서가 맨 왼쪽에 있을 때에는 2번 시행을 출력해서는 안 된다.

모든 시행이 끝난 뒤에 커서의 위치는 어디에 있든 상관없다.

답이 여러 가지 존재하는 경우 아무거나 하나만 출력한다.

입력 조건 하에서 답이 항상 존재함을 증명할 수 있다.

풀이

애드 혹 태그가 달린 문제답게 풀이도 코드도 간단했지만 풀이를 얻기까지 한두시간 고민했다.

실제 풀이에서 맨 처음 생각한 아이디어는 우선 문자의 쌍을 찾아야 한다는 것이다. 예를 들어 U를 입력하면 그에 대응되는 S가 어딘가에 존재한다. 이런 경우 누적 합을 통해 구간을 관리할 수 있다. BOJ1023(괄호 문자열)과 비슷한 맥락에서 두 부분문자열을 연결한 문자열도 동일하게 해결할 수 있으므로 반대로 원래 문자열을 문제의 조건을 만족하는 두 부분문자열로 컷 한 뒤 해결하는 방법을 생각해봤다.

 

우선 예제 입출력을 분석해보자. 예제 입출력에서 발견한 특징은 "정답 문자열 제일 끝에 불필요한 N이 붙어있다. 그것도 두개씩이나."였다. 

예제 출력을 따라가면 입력의 문자열을 "뒤에서부터" 구성한다는 것을 알 수 있었다. 예컨대 예제 입력 1은 SS로도 작성할 수 있지만, 뒤에서부터 작성하면  SNNS로 작성하게 된다.

 

실제로 뒤에서 부터 작성하려는 아이디어를 떠올렸을 때 문뜩 든 생각은 앞서 생각한 문자 쌍을 찾기 아주 쉽다는 것이다. 최소해를 찾는 경우가 아니기때문에 문자 쌍이 대응되는 것이 유일할 필요가 없고, 아무거나 적당히 문자 쌍을 대응시킬 수 있다면(풀이 과정 중의 해의 성질을 여전히 만족하는 이상), 대응시키면 된다. 실제로 이 시점에서 문제의 풀이가 완성되었고, 바로 코드를 작성해서 AC를 받았다. 물론 코드를 작성하는 과정에서 어림으로 계산했던 디테일을 잡아갔다.

 

일단 최초 상태를 빈 문자열 가장 뒤에 커서가 위치한 것으로 볼 수 있다. 가장 뒤의 문자가 S라고 가정하자. 이 문자는 자명하게 U를 입력해 나온 S여야 한다. 따라서 이 S와 대응되는 U가 앞선 문자열의 일부에 존재한다. 만약 이 이전 문자가 U라고 가정하면, 즉 가장 마지막 두 글자가 US라면 이 두 글자를 제외한 나머지 앞선 부분문자열은 본 알고리즘으로 풀 수 있다. 따라서 UNN을 시행하면 마지막 US를 오른쪽에 입력하고 나머지 문자열을 입력하기 위해 US를 제외한 나머지 빈 문자열 가장 뒤에 위치시킨 것과 같다. 다르게 말하면, US를 가장 오른쪽에 입력하고 나머지 부분문제를 풀기 위한 최초상태로 진입하는 것이다.

 

앞서 생각했던 괄호 문자열과 비슷하게 입력을 분석해보자. US, SU는 입력할 수 있는 문자열이다. 입력할 수 있는 두 문자열 S, T에 대해 ST도 입력할 수 있는 문자열이고, UTS, STU도 입력할 수 있는 문자열이다. 어떤 부분문자열 T를 입력하고 난 뒤 커서를 가장 왼쪽에 위치할 때 까지 N을 실행하고, 다시 부분문자열 S를 입력하면 ST를 출력할 수 있고, UN을 실행하고 T를 입력하면 UTS, SN을 실행하고 T를 입력하면 STU도 입력할 수 있다.

 

이 로직에서 커서를 우선 어떤 문자 왼쪽으로 이동시키고 나면 커서 오른쪽 문자열은 어떤 일이 있어도 수정될 수 없다. 따라서 커서 오른쪽 문자열을 입력마다 추적해보자. 커서의 위치를 C로 쓰자. UNUNNN의 경우 "USC" -> "UCS" -> "UUSCS"-> "UUCSS"-> "UCUSS" -> "CUUSS"와 같이 작성된다. 이때 N이 하나 추가될 때마다 커서가 한 칸 왼쪽으로 이동한다. 반대로, N이 하나 추가될 때마다 커서 오른쪽에 문자가 하나 추가된다. 우리가 원하는 로직이 문자를 입력한 뒤 커서를 이미 입력한 문자 왼쪽으로 보내는 것이기 때문에 N을 문자열 길이만큼 입력해야 한다.

 

실제로 이를 재귀로 실행할 필요는 없다. 두 부분문자열이 연속해서 등장하는 경우는 N을 출력해 커서의 위치를 이동한 뒤 출력하면 되고, STU, UTS의 경우는 UN(또는 SN)을 실행한 뒤 커서 왼쪽의 부분문자열을 보면 S(또는 U)가 하나 U(또는 S)보다 하나 많은 부분문자열이 된다. 이때 입력할 수 있는 문자열을 오른쪽부터 입력하고 난 뒤 S(또는 U)를 만난다면 가장 앞선 문자와 쌍을 이루는 문자라고 생각할 수 있으므로 N을 실행하면 UTS, STU의 문자열을 입력하고 커서를 왼쪽 끝으로 이동시킬 수 있다. 좀 더 자세히 얘기하자면, 오른쪽에서 왼쪽으로 훑으면서 커서 오른쪽의 문자열이 입력가능한 문자열일 때 처음 만난 문자와 대응되는 S<->U는 이 두 문자를 제외하고 입력가능한 문자열이 지난 후에 처음으로 나오는 대응되는 문자인 경우는 해가 된다.

 

설명이 길었는데, 실제 로직은 아래와 같이 해결된다.

1. 가장 오른쪽 문자부터 순서대로 확인한다. S에 1, U에 -1을 대응시키자. 오른쪽에서 왼쪽으로 이동하면서 문자열의 누적합을 구하자. 누적합이 0이라면 이전까지 탐색한 문자열이 입력가능한 문자열이라는 뜻이다. (문제 조건에서 해가 존재함을 증명가능하다고 서술했다.)

2. 현재 만난 문자가 S이고 누적합이 0 이상이라면 UN을 출력한다.

3. 현재 만난 문자가 U이고 누적합이 0 이하라면 SN을 출력한다.

4. 현재 만난 문자가 S이고 누적합이 음수이거나, 현재 만난 문자가 U이고 누적합이 양수라면 N을 출력한다.

이렇게 완성된 문자열은 N이 문자열 길이만큼 존재하고 문자열 길이의 절반만큼 U나 S를 입력해야 하므로 정확히 3/2N개의 길이가 된다.

 

뭐라 설명하기는 어렵지만 순서대로 따라가면 해가 되겠거니하는 생각은 쉽게 할 수 있을거라고 생각한다. 애드혹 문제들이 설명하거나 유도하는 과정을 말로 설명하기는 어렵지만 로직을 짰을 때 타당하다고 확인하기 쉬운 문제들인 것 같다.