[백준] 문자열 생성

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

6137번: 문자열 생성

그리디 문제입니다. 반례의 반례가 계속 나와서 한참동안 고민했습니다. 문자열의 양쪽 끝을 비교해서 더 작은 문자를 붙혀주면 되는데 문제는 양쪽 끝의 문자가 같은 경우입니다. 그런 경우에는 양쪽 끝에서부터 투 포인터를 움직이면서 더 작은 문자를 만나는 쪽을 빼줘야합니다. 그렇지 않으면 사전 순으로 더 빠른 문자열을 얻을 수 없습니다.

 

예를 들어, CBBABC의 경우 앞뒤로 CB, BC가 같습니다. 만약 여기서 투포인터로 처리해주지 않고 같을 경우 앞에 문자를 빼서 넣어주게 되면 CBBABC를 얻게 됩니다. 하지만 정답은 CBABBC가 나와야합니다.

 

import sys
from collections import deque

# sys.stdin = open("input.txt", "r")

input = sys.stdin.readline

n = int(input())

dq = deque()

for _ in range(n):
    char = input().rstrip()
    dq.append(char)

answer = ""

cnt = 0
while dq:
    if len(dq) == 1:
        answer += dq[0]
        break

    if dq[0] < dq[-1]:
        answer += dq.popleft()

    elif dq[0] == dq[-1]:
        # deque의 길이가 3보다 작으면 어떤 걸 뽑아도 상관없다.
        if len(dq) <= 3:
            answer += dq.popleft()

        else:
            # 양끝 문자의 바로 다음 문자들을 비교해서
            # 같거나 왼쪽에 있는 문자가 더 작으면 왼쪽 문자를 pop한다.
            left = 0
            right = len(dq) - 1

            while left < right:
                if dq[left] < dq[right]:
                    answer += dq.popleft()
                    break
                elif dq[left] > dq[right]:
                    answer += dq.pop()
                    break

                left += 1
                right -= 1

            # 만약 달라지는 구간을 찾지 못한 경우에는 어떤 것을 뽑아도 상관없다.
            if left >= right:
                answer += dq.popleft()

    else:
        answer += dq.pop()


    if len(answer) == 80:
        print(answer)
        answer = ""
        cnt += 1

if answer:
    print(answer, end="")