[백준] 1474 밑줄 Python 풀이 (Greedy)

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

1474번: 밑 줄

 

그리디 문제이다 
규칙을 찾는데 좀 오래 걸렸는데, 문제에서 핵심이 되는 것은 바로 사전순 정렬이다. 

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

라고 문제에서 주어졌다. 

즉, 대문자로 시작하는 단어의 경우 대문자의 우선순위가 '_' 의 우선순위 보다 높으니까, _가 뒤에 등장해야하고, 
소문자로 시작하는 단어의 경우 소문자의 우선순위보다 '_' 의 우선순위가 더 높으므로, _가 앞에 등장해야 이득이다. 

이를 코드화해보자 !

우선, 지금 체크하는 문자열의 길이를 확인하여, 단어의 사이마다 _의 개수를 몇개로 할것인지를 구해준다. 

k = (m-length)//(n-1)

 

그리고 (n-1)로 떨어지지 않는 우리가 greedy 규칙을 이용해서 붙여주어야 하는 남는 '_' 의 개수를 구한다. 

left = (m - length) % (n - 1) # 더해주어야 하는 _ 남은 개수

result는 만들 문자열의 결과값을 담는 리스트이다. 

우선 소문자로 시작하는 단어들의 케이스를 확인한다.
단어를 담아둔 array 라는 배열에서 처음부터 끝까지 순회하며, 소문자로 시작하는 단어가 등장하면 앞에 _를 하나 더 붙여주고, left개수를 1개 빼준다 

for i in range(n):
    if i == 0:
        result.append(array[i])
        continue
    if 97 <= ord(array[i][0]) <= 122:
        if left > 0:
            result.append(interval+"_")
            left -= 1
            result.append(array[i])
        else:
            result.append(interval)
            result.append(array[i])
    else: # 대문자
        result.append(interval)
        result.append(array[i])

소문자로 시작하는 단어들을 다 체크한 이후에도 남은 '_' 개수가 있다면 (left >0 인 경우), 
대문자로 시작하는 단어들을 체크한다.
대문자로 시작하는 단어들은 맨 마지막 인덱스부터 확인하여 '_'를 붙여준다. 

if left > 0: # 아직 더해주어야 하는 _ 의 개수가 남았다면 대문자로 시작하는 단어를 확인한다.
    for i in range(len(result)-1, -1, -1):
        if 65 <= ord(result[i][0]) <= 90: # 대문자인 경우
            if left > 0:
                result[i] = '_'+result[i]
                left -= 1

 

확인이 다 끝나면 result 를 join()함수를 이용해 문자열로 출력한다. 

print("".join(result))

 

[ 전체 코드 ]

n, m = map(int, input().split())

array = []
length = 0
result = []

for i in range(n):
    data = input()
    array.append(data)
    length += len(data)

k = (m-length)//(n-1)
left = (m - length) % (n - 1) # 더해주어야 하는 _ 남은 개수
interval = "_"*k
#소문자 먼저 확인하고, 소문자 등장하면 _ 넣기

for i in range(n):
    if i == 0:
        result.append(array[i])
        continue
    if 97 <= ord(array[i][0]) <= 122:
        if left > 0:
            result.append(interval+"_")
            left -= 1
            result.append(array[i])
        else:
            result.append(interval)
            result.append(array[i])
    else: # 대문자
        result.append(interval)
        result.append(array[i])

if left > 0: # 아직 더해주어야 하는 _ 의 개수가 남았다면 대문자로 시작하는 단어를 확인한다.
    for i in range(len(result)-1, -1, -1):
        if 65 <= ord(result[i][0]) <= 90: # 대문자인 경우
            if left > 0:
                result[i] = '_'+result[i]
                left -= 1
print("".join(result))

# 대문자
# print(ord('A')) 65
# print(ord('Z')) 90
# print(ord('a')) 97
# print(ord('z')) 122
# print(ord('_')) 95