[백준] 1251번 단어 나누기 C++ 풀이

mobitel​

mobitel​

---

알고리즘 분류

• 구현
• 문자열
• 브루트포스 알고리즘
• 정렬

---

문제 설명

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

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

예를 들어,

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

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

---

입력 설명

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

---

출력 설명

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

---

예제 입력

mobitel

---

예제 출력

bometil

---

아이디어

먼저 3등분을 하고 2중 for문으로 각 등분 사이의 경계 범위를 조정해 가면서 사전순으로 더 작은 값을 찾는다.

---

알고리즘

3등분으로 나눈 부분을 앞에서부터 a, b, c라고 한다면 a는 0부터 시작해서 최대 입력받은 string size의 -2의 범위까지 포함할 수 있다.

b는 a가 포함한 범위 바로 다음 부터 string size의 -1 -i 범위까지 포함할 수 있다.

c는 a와b를 제외한 나머지 부분을 모두 포함하면 된다.

이렇게 만든 a, b, c를 각각 reverse로 뒤집은 다음 하나로 합쳐서 기존의 answer과 비교하여 더 작다면 이 값을 answer로 사용한다.

---

코드

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
int main()
{
	string str,ans="";
	cin>>str;
	for(int i=1; i<=str.size()-2; i++)
	{
		for(int j=1; j<=str.size()-1-i; j++)
		{
			string a = str.substr(0,i);
			string b = str.substr(i,j);
			string c = str.substr(i+j);
			reverse(a.begin(), a.end());
			reverse(b.begin(), b.end());
			reverse(c.begin(), c.end());
			if(ans == "") ans = (a+b+c);
			else if(ans > (a+b+c)) ans = (a+b+c);
		}
	}
	cout<<ans<<"\n";
	return 0;
}

---

후기

문제 링크 -> https://www.acmicpc.net/problem/1251

 

5시간을 고민하면서 대단히 많은 예외처리를 하는 코드를 작성하다가 실패해서 결국 정답 코드를 찾아봤다.

발상은 굉장히 간단한데 구현할 때 범위를 제대로 정해줘야 하는 부분이 중요해서 그 부분을 좀 신중하게 생각해 보면 좋다.

---

본 블로그의 모든 글은 개인적인 학습 내용이므로 다양한 오류가 있을 수 있습니다.

오류를 발견하신다면 해당 내용 댓글로 알려주시면 감사하겠습니다!