문제 소개
문자열 s에 여러 개의 단어가 있고, 단어들 사이에는 하나 이상의 공백이 포함되어 있다고 가정해 봅시다. 우리가 해야 할 일은 이 공백들을 재배치하여 인접한 모든 단어 쌍 사이에 동일한 개수의 공백이 오도록 만드는 것입니다. 또한 단어 사이의 공백 개수를 최대한 많이 확보해야 합니다.
만약 전체 공백을 단어들 사이에 균등하게 나눌 수 없다면, 남은 공백은 문자열의 맨 뒤에 추가하면 됩니다.
예를 들어 입력이 다음과 같다고 해보겠습니다.
s = " I love programming "
이 경우 출력 결과는 아래와 같습니다. 단어 사이마다 공백이 고르게 분배된 것을 확인할 수 있습니다.
"I love programming "
해결 접근 방법
이 문제는 다음 단계를 통해 해결할 수 있습니다.
- 결과를 담을 빈 문자열
res를 초기화합니다. total_sp에 문자열 s 안의 전체 공백 개수를 저장합니다.suff_sp_cnt(뒤에 붙일 남은 공백 개수)를total_sp값으로 초기화합니다.text_array에 s를 공백 기준으로 분리한 단어 목록을 저장합니다.num_words에 단어의 개수를 저장합니다.- 단어가 하나뿐이라면, 해당 단어 뒤에 전체 공백을 모두 붙여 바로 반환합니다.
sep_size는total_sp // (num_words - 1), 즉 단어 사이에 들어갈 공백 개수(몫)입니다.sep는sep_size개만큼의 공백 문자열입니다.- 단어 목록의 각 단어를 순회하면서 결과 문자열에 단어와 구분자 공백을 차례로 붙이고,
suff_sp_cnt에서 사용한 공백 수를 차감합니다. - 순회가 끝나면 마지막 단어 뒤에 불필요하게 붙은 공백(
sep_size)을 되돌려 줍니다. - 결과 문자열 양쪽 끝의 여분 공백을 제거하고, 남은 공백
suff_sp_cnt개를 맨 뒤에 붙인 후 반환합니다.
파이썬 구현 예제
아래 코드를 통해 더 자세히 이해해 보겠습니다.
def solve(s):
res = ""
total_sp = s.count(" ")
suff_sp_cnt = total_sp
text_array = s.split()
num_words = len(text_array)
if num_words == 1:
res = text_array[0] + total_sp * " "
return res
sep_size = total_sp // (num_words - 1)
sep = sep_size * " "
for i in text_array:
res += i
res += sep
suff_sp_cnt -= sep_size
suff_sp_cnt += sep_size
res = res.strip()
res += suff_sp_cnt * " "
return res
s = " I love programming "
print(solve(s))입력
" I love programming "
출력
"I love programming "
코드 설명
이 알고리즘의 핵심은 크게 세 부분으로 나눌 수 있습니다.
- 공백 개수 계산:
s.count(" ")로 전체 공백 개수를 파악하고,s.split()으로 단어만 깔끔하게 추출합니다. - 균등 분배: 단어가 n개라면 단어 사이 구간은 n-1개이므로, 전체 공백을 n-1로 나눈 몫만큼 각 구간에 배치합니다.
- 남은 공백 처리: 나눗셈의 나머지에 해당하는 공백은 반복문 중 계산된
suff_sp_cnt에 누적되며, 최종적으로strip()으로 정리한 뒤 문자열 끝에 한꺼번에 붙여집니다.
시간 복잡도는 문자열 길이에 비례하는 O(n)이며, 공간 복잡도 역시 O(n)으로 효율적인 편입니다. 단어가 하나뿐인 특수 경우도 별도로 처리하고 있어 안전하게 동작합니다.