[백준] 1474번 밑 줄

💡문제접근

• 각 단어의 사이에 _을 넣어서 새로운 단어를 만드는데 이 때 만들어진 새로운 단어가 사전 순으로 가장 앞서는 단어를 구하는 문제다. [출력] 항목에 보면 사전 순 정렬에 대한 조건이 주어져있는데 조건은 다음과 같다.

알파벳 대문자, 소문자, 밑 줄의 순서는 'A' < 'B' < 'C' < ... < 'Z' < '_' < 'a' < 'b' < 'c' < ... < 'z' 이다.

• 위의 조건을 이해하면 우선 대문자가 사전 순으로 가장 앞서고 그 다음으로 소문자가 나오게 되는데 이 때 대문자와 소문자의 경계에 존재하는 _는 소문자보다 사전 순으로 앞선다는 것을 알 수 있다.

💡테스트케이스

입력
4 29
Hello
world
John
said

출력
Hello____world___John____said

💡코드(메모리 : 31256KB, 시간 : 56ms)

import sys
input = sys.stdin.readline

N, M = map(int, input().strip().split())
words = []
temp = 0
for i in range(N):
    words.append(input().strip())
    temp += len(words[i])

# 사전 순으로 가장 앞서는 단어를 출력하려면?
# 알파벳 대문자, 소문자, 밑 줄의 순서는 'A' < 'B' < 'C' < ... < 'Z' < '_' < 'a' < 'b' < 'c' < ... < 'z' 이다.

diff = M - temp
gap = N - 1
quotient, remain = divmod(diff, gap)
result = words[0]
for i in range(1, N):
    if words[i][0].islower() and remain != 0:
        remain -= 1
        result += "_" * (quotient + 1) + words[i]
    # 같은 대문자의 경우
    elif words[i][0].isupper() and i + remain > gap:
        remain -= 1
        result += "_" * (quotient + 1) + words[i]
    else:
        result += "_" * quotient + words[i]
print(result)

💡소요시간 : 37m