문제

N개의 문자로 이루어진 문자열 S가 입력된다.

이 문자열의 각 문자들로 새로운 문자열 T를 만들려고한다.

문자열 S로 문자열 T를 만드는 규칙은 다음과 같다.

문자열 S의 가장 앞의 문자 하나를 문자열 T의 마지막에 추가한다.
문자열 S의 가장 뒤의 문자 하나를 문자열 T의 마지막에 추가한다.

위 규칙으로 만들어진 문자열 T들 중 사전순으로 가장 빠른 문자열을 출력하는 프로그램을 작성하시오.

입력

첫 번째 줄에 문자열 S의 길이 N이 주어진다. (N <= 2,000)

이후 N개의 줄에 S를 이루는 문자들이 주어진다.

출력

만들어진 사전순으로 가장 빠른 문자열을 출력한다. 80글자마다 새줄 문자를 출력해야 한다.

코드

from collections import deque
import sys
input = sys.stdin.readline

n = int(input())
q = deque()
for i in range(n):
    q.append(input().rstrip())

s, e = 0, n-1
while s <= e:
    if s == e:
        print(q[s], end="")
        break
    # 앞 문자 pop
    if q[s] < q[e]:
        print(q[s], end="")
        s += 1
    # 뒷 문자 pop
    elif q[s] > q[e]:
        print(q[e], end="")
        e -= 1
    # 앞뒤 같은 문자인 경우
    else:
        flag = False
        ss, ee = s+1, e-1
        # 서로 다른 문자 나올 때까지 양쪽에서 1씩 줄여감
        while ss <= ee:
            if q[ss] < q[ee]:
                print(q[s], end="")
                s += 1
                flag = True
                break
            elif q[ss] > q[ee]:
                print(q[e], end="")
                e -= 1
                flag = True
                break
            else:
                ss += 1
                ee -= 1
        # 서로 다른 문자 찾지 못했으면 그냥 앞에서 pop
        if not flag:
            print(q[s], end="")
            s += 1
    if (s+(n-1)-e) % 80 == 0:
        print()

입력으로 주어진 문자열의 맨앞이나 맨뒤에서 문자를 하나씩 뽑아서 만든 문자열 중 사전순으로 가장 빠른 문자열을 찾는 문제였다.

이 문제를 해결하기 위해서는 뽑을 수 있는 두 문자 중 무조건 사전순으로 더 빠른 문자를 뽑으면 된다. 예를 들어 BCDA라는 문자열이 있다면 현재 뽑을 수 있는 문자는 B, A이다. 이 둘 중 사전순으로 더 빠른 문자는 A이므로 A를 먼저 뽑으면 된다.

그런데 두 문자열이 같은 경우에는 더 안 쪽의 문자를 비교해보아야 한다. 예를 들어 BADB라는 문자열이 있다면 양쪽에서 하나씩 안으로 들어오며 검사했을때 서로 다른 문자가 나오는 순간은 A, D이다. 사전순으로 더 빠른 문자열을 만들기 위해서는 앞쪽에 최대한 작은 문자가 와야 한다. 그러므로 A가 더 빨리 출력될 수 있도록 A가 있는 쪽인 앞쪽의 B, 즉 첫번째 B를 출력해준다. 만약 이렇게 아직 출력하지 않은 문자열을 다 검사해도 대칭되는 문자 중 서로 다른 문자를 발견하지 못한다면 그냥 맨앞의 문자를 출력해준다.

그리고 문제의 조건 중에 80글자마다 줄 바꿈을 해주어야 한다고 했으므로 출력된 글자의 수인 (s+(n-1)-e)가 80의 배수일 때마다 줄 바꿈을 하도록 해준다.

저작자표시 (새창열림)