취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 6137번 문제인 문자열 생성이다.
문제는 아래 링크를 확인하자.

https://www.acmicpc.net/problem/6137 

주어진 문자열의 맨 앞 또는 뒤의 글자를 하나씩 떼어내 만들어질 수 있는 모든 문자열 중 사전순으로 가장 빠른 문자열을 만드는 문제이다.

만약 주어진 문자열의 맨 앞글자와 뒷글자가 다르다면 사전순으로 먼저 오는 글자를 떼 새 문자열의 다음 글자로 사용하면 된다.

주어진 문자열의 맨 앞글자와 뒷글자가 같은 경우, 주어진 문자열이 팰린드롬(뒤집어 읽어도 같은 문자열, 회문) 문자열이 아니라면 앞에서부터 봤을 때와 뒤에서부터 봤을 때 처음으로 다른 글자가 나오게 되는데, 그중 사전순으로 빠른 쪽의 글자를 떼 새 문자열의 다음 글자로 사용해야 한다. 그 위치의 글자를 넣을 순서가 왔을 때 사전순으로 더 빠른 문자열을 얻으려면 어떻게 해야하는지를 떠올려보면 좋다. 팰린드롬 문자열의 경우 앞과 뒤 중 어떤 글자를 떼어도 상관없다.

아래는 제출한 소스코드이다.

#include <iostream>
using namespace std;

char s[2000];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	int N; cin >> N;
	for (int i = 0; i < N; i++) cin >> s[i];
	int L = 0, R = N - 1;
	int cnt = 0;
	while (L <= R) {
		int l = L, r = R;
		bool ispal = 1;
		while (l < r) {
			if (s[l] != s[r]) {
				ispal = 0;
				break;
			}
			l++; r--;
		}
		if (ispal) {
			cout << s[L];
			L++;
		}
		else {
			if (s[l] < s[r]) {
				cout << s[L];
				L++;
			}
			else {
				cout << s[R];
				R--;
			}
		}
		cnt++;
		if (cnt == 80) {
			cnt = 0;
			cout << '\n';
		}
	}
}