백준 1251번: 단어 나누기

백준 1251번: 단어 나누기

 

1251번: 단어 나누기

 

- 그리디 알고리즘을 활용하여 품. 세 단어로 쪼갤 수 있는 경우의 수를 모두 실행하여 그 중 사전순으로 가장 앞서는 단어를 출력함

• 이중 for문을 활용하여 단어를 세 단어로 나눈다(아래 코드에서 i와 j가 세 단어로 나누는 일종의 경계선).
• 나눈 뒤에 문제처럼 뒤집어 준다. 이는 reverse()를 활용한다
• 뒤집은 세 단어를 합한 뒤에 tmp 리스트에 저장한다
• tmp 리스트에는 세 단어가 따로 저장 돼 있으므로 join()을 통해 하나의 단어로 만든 뒤에 sort한다
• 가장 처음에 있는 단어가 정답이다

아래는 파이썬 코드

 

	word = list(input())
	answer = []
	tmp = []
	for i in range(1, len(word) - 1):
	for j in range(i + 1, len(word) ):
	a = word[:i]
	b = word[i:j]
	c = word[j:]
	a.reverse()
	b.reverse()
	c.reverse()
	tmp.append(a + b + c)
	for a in tmp:
	answer.append(''.join(a))
	print(sorted(answer)[0])

view raw BOJ_1251.py hosted with ❤ by GitHub