[백준] 1474 - 밑 줄

문제

백준 1474번 밑 줄

문제 링크 : https://www.acmicpc.net/problem/1474

 

문제 풀이

이 문제는 각 단어 사이에 '_'를 넣어 새로운 문자열을 만드는 것이 목적이다. 단어의 순서는 정해져 있고, 각 단어 사이에 반드시 '_'를 포함해야 하므로, 각 단어 사이에 어떤 길이의 '_' 문자열을 넣어야 하는지 판단해야 한다. 

대문자 < _ < 소문자 순이므로, 앞 글자가 소문자라면 '_'가 우선이고, 대문자라면 '_'가 후순위이다.  최소 '_'문자열의 길이 small과, 최대 '_' 연결 문자열의 길이 big, small의 수 ss, big의 수 bs를 구한다. 이후 입력된 단어들을 순회하면서 앞 글자가 소문자인 경우 우선적으로 앞에 big을 붙이고, 앞 글자가 대문자인 경우 우선적으로 small을 붙인다. 사전 순으로 가장 앞서는 단어를 만들어야 하므로, 앞선 단어들에 적합한 big과 small을 먼저 배치하는 것이 사전 순으로 반드시 앞선다. 따라서 그리디 알고리즘으로 풀이했다고 볼 수 있다.

 

코드

import sys

input = sys.stdin.readline

n,m = map(int,input().split(' '))
lst=['' for _ in range(n)]
alpha=0

for i in range(n):
  lst[i]=input().rstrip()
  alpha+=len(lst[i])

# 최소 '_' 연결 문자열의 길이
small = (m-alpha)//(n-1) 
# 최대 '_' 연결 문자열의 길이
big=small+1 
# big의 수
bs = (m-alpha -n*small + small)//(big-small)
# small의 수
ss=(n-1)-bs

answer=lst[0]
for i in range(1,n):
  # 소문자인 경우
  if lst[i][0]>='a':
    # 우선적으로 big을 고려
    if bs>0:
      bs-=1
      answer+='_'*big
    else:
      ss-=1
      answer+='_'*small
  # 대문자인 경우
  else:
    # 우선적으로 small을 고려
    if ss>0:
      ss-=1
      answer+='_'*small
    else:
      bs-=1
      answer+='_'*big
  answer+=lst[i]   

print(answer)