[Python/파이썬] 백준 6137번 문자열 생성

6137번: 문자열 생성

 

문제

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의 배수일 때마다 줄 바꿈을 하도록 해준다.