밑 줄 ( 1474 번 )

1474번: 밑 줄

 

---

🧠 알고리즘

• 그리디(Greedy) + 문자열 처리

 

✔️ 동작 방식

• 단어들을 입력받아 리스트 answer에 저장
• 소문자로 시작하는 단어의 인덱스를 low_idx 집합에 기록 (첫 단어 제외)
• 필요한 언더바 구한 후 각 조건에 맞게 언더바 추가

---

 

 

🧾 코드

import sys

def _main(n, m):
    answer = []
    low_idx, str_len = set(), 0

    for idx in range(n):
        now_str = sys.stdin.readline().rstrip()
        if (idx > 0) and now_str[0].islower(): # 소문자 일경우 index 기록
            low_idx.add(idx)
        
        str_len += len(now_str)
        answer.append(now_str)

    under_count = m - str_len
    mod, na = under_count // (n - 1), under_count % (n - 1)
    
    for idx in range(1, n):
        if (idx in low_idx) and (na > 0): # 소문자 경우 언더바 추가
            answer[idx] = '_' + answer[idx]
            na -= 1

        answer[idx] = ('_' * mod) + answer[idx]

    for idx in range(n - 1, 0, -1): # 추가 언더바 남으면 대문자에도 추가
        if (idx not in low_idx) and (na > 0):
            answer[idx] = '_' + answer[idx]
            na -= 1
        
    return ''.join(answer)


n, m = map(int, sys.stdin.readline().rstrip().split())
print(_main(n, m))

---

 

 

⏱️ 시간 복잡도

for idx in range(1, n) : 순회하며 언더바 추가 ( 선형 시간 복잡도 )
for idx in range(n - 1, 0, -1): # 역순으로 추가하며 언더바 추가 ( 선형 시간 복잡도 )

해당 알고리즘 시간 복잡도 : 선형 시간 복잡도 ( O(n) )