[BOJ] 6137 - 문자열 생성 (Python)

 

 

아이디어

 

투 포인터로 사전순으로 가장 빠른 문자열을 만들어 나간다.

 

 

풀이

 

비교하는 두 문자가 같은 경우 이후에 사전순으로 앞서는 문자가 먼저 등장하는 포인터쪽의 문자를 더한다.

 

import sys

input = sys.stdin.readline

def solution():
    N = int(input())
    S = [input().rstrip() for _ in range(N)]
    s = 0
    e = N-1
    res = ''
    for k in range(1, N+1):
        if S[s] < S[e]:
            res += S[s]
            s += 1
        elif S[e] < S[s]:
            res += S[e]
            e -= 1
        else:
            i, j = s, e
            while i <= j:
                if S[i] < S[j]:
                    res += S[s]
                    s += 1
                    break
                elif S[j] < S[i]:
                    res += S[e]
                    e -= 1
                    break
                i += 1
                j -= 1
            else:
                res += S[s]
                s += 1
        if k%80 == 0:
            res += '\n'
    print(res.rstrip())

solution()