[백준] 1251. 단어 나누기

문제

알파벳 소문자로 이루어진 단어를 가지고 아래와 같은 과정을 해 보려고 한다.

먼저 단어에서 임의의 두 부분을 골라서 단어를 쪼갠다. 즉, 주어진 단어를 세 개의 더 작은 단어로 나누는 것이다. 각각은 적어도 길이가 1 이상인 단어여야 한다. 이제 이렇게 나눈 세 개의 작은 단어들을 앞뒤를 뒤집고, 이를 다시 원래의 순서대로 합친다.

예를 들어,

• 단어 : arrested
• 세 단어로 나누기 : ar / rest / ed
• 각각 뒤집기 : ra / tser / de
• 합치기 : ratserde

단어가 주어지면, 이렇게 만들 수 있는 단어 중에서 사전순으로 가장 앞서는 단어를 출력하는 프로그램을 작성하시오.

 

입력

첫째 줄에 영어 소문자로 된 단어가 주어진다. 길이는 3 이상 50 이하이다.

출력

첫째 줄에 구하고자 하는 단어를 출력하면 된다.

예제 입력 1

mobitel

예제 출력 1

bometil

---

문제 이해

우선 이 문제는 이해하는 데 시간이 오래 걸렸다... 질문 게시판을 봐도 이해가 잘 되지 않아 직접 경우를 다 따져가면서 문제를 이해해보았다. 예제1에 입력값 mobitel을 쪼개는 경우는 6C2 = 15가지이다. 왜 6C2인지에 대한 설명은 아래와 같다.

m

✔

o

✔

b

✔

i

✔

t

✔

e

✔

l

mobitel이 주어졌을 때, 이를 3개의 단어로 쪼개기 위해서는 쪼개는 지점 2개를 선택해야 한다. mobitel의 글자 길이는 7로 글자 하나하나 사이의 간격은 7-1 = 6개가 생긴다. 따라서 6개의 파란색 체크 중 2개를 선택하는 경우의 수이므로 6C2 = 15가지이다.

 

그럼 15가지의 경우를 모두 나열해보자.

m	o	bitel
m	ob	itel
m	obi	tel
m	obit	el
m	obite	l
mo	b	itel
mo	bi	tel
mo	bit	el
mo	bite	l
mob	i	tel
mob	it	el
mob	ite	l
mobi	t	el
mobi	te	l
mobit	e	l

이제 나눠진 각 단어들을 앞뒤 뒤집어보자.

m	o	letib
m	bo	leti
m	ibo	let
m	tibo	le
m	etibo	l
om	b	leti
om	ib	let
om	tib	le
om	etib	l
bom	i	let
bom	ti	le
bom	eti	l
ibom	t	le
ibom	et	l
tibom	e	l

이제 각 단어들을 합쳐보자.

moletib

mboleti

mibolet

mtibole

metibol

ombleti

omiblet

omtible

ometibl

bomilet

bomtile

bometil

ibomtle

ibometl

tibomel

이제 이 15가지 단어들 중에 사전 순으로 가장 앞서는 단어를 출력하면 된다. 

첫글자만 비교해도 b로 시작하는 단어가 가장 앞서는 단어 후보가 된다. bomilet, bomtile, bometil

이 중 두번째, 세번째 단어는 모두 om으로 같으므로 네번째 단어를 비교하면 i, t, e 중 e가 제일 빠르므로 bometil이 정답이다.

풀이 방향

우선 가장 간단한 풀이로 위에서 설명한 것처럼 모든 조합의 경우를 구한 다음, 각 단어를 뒤집어서 그 단어들 중 가장 사전순으로 앞의 단어를 뽑는 풀이를 생각했다. 

3가지 단어로 쪼개는 과정은 이중 for문을 이용하여 6개의 간격 중 첫번째 간격부터 두번째, 다음은 세번째, 이런식으로 선택하는 방법을 구현하였다. 

 

즉, 빨간색 체크를 먼저 선택하고(바깥쪽 for문)

m

✔

o

✔

b

✔

i

✔

t

✔

e

✔

l

그 다음 안쪽 for문에서 빨간색 체크 뒤에 있는 체크를 선택한다. 

m

✔

o

✔

b

✔

i

✔

t

✔

e

✔

l

그렇게 단어를 세가지로 자르고 이를 파이썬의 reverse()함수를 이용하여 뒤집은 다음, 이를 하나의 문자열로 합쳐서 리스트에 저장하여 파이썬의 min()함수를 이용해 가장 사전 상 앞의 단어를 출력하는 형태로 구현한다.

 

내 풀이

word = list(input())
res = []

for i in range(1, len(word) - 1): 
    for j in range(i + 1, len(word)): # 3개의 단어로 쪼개기 위해 지점 2개 지정
        first = word[:i] # 첫 번째 단어
        second = word[i:j] # 두 번째 단어
        third = word[j:] # 세 번째 단어

        # 각 단어 뒤집기
        first.reverse()
        second.reverse()
        third.reverse()

        # 뒤집은 단어를 합쳐서 리스트에 저장
        res.append("".join(first + second + third))

# 리스트에서 가장 작은 단어 출력하기 위해 min함수 이용(아스키 코드 이용해서 min으로 구할 수 있는 듯?)
print(min(res))

단어를 자르는 과정을 이중 for문으로 구현하였다. i는 빨간색 체크의 위치(인덱스)를 의미하고, j는 주황색 체크의 위치(인덱스)를 의미한다. 이 때, i의 범위는 1부터 len(word) - 2까지로 설정하였는데, 반드시 단어의 길이가 1이상이어야 하므로 word의 길이보다 하나 작은 값을 range의 인자로 넣어주었다. 또한, j는 i 이후부터 탐색하므로 i+1부터 len(word) - 1까지로 범위를 설정해주었다. 

파이썬의 슬라이싱은 word[:i]일 경우 i-1번째 값까지 자른다를 의미하므로, 우리가 생각하는 간격의 의미를 구현할 수 있다. 각 단어를 first, second, third에 저장하고, reverse()를 이용해 문자열을 뒤집어준다. 그 후, res 리스트에 join함수를 이용해 공백없이 이어 붙인 문자열을 하나씩 저장해준다.

그 후 파이썬의 min()함수를 이용해 res 리스트에 저장된 모든 경우의 최종 문자열 중 가장 사전 상 앞에 있는 단어를 출력해준다. min()함수가 문자열에서도 적용되는 이유는 아스키코드를 이용하기 때문에 숫자 최소값을 구하는 함수인 min()을 사용할 수 있다고 생각했다. 실제로 검색해본 결과 ASCII 값을 비교하여 가장 낮은 값 즉, 사전 상 가장 앞에 있는 값을 반환한다고 한다. 

 

[참고] ASCII Table