[백준OJ] 6137번 문자열 생성

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

6137번: 문자열 생성

---

 

 

풀이

투포인터를 이용해서 양 끝에서 가운데로 서서히 오면서 조건에따라 문자를 추가해주면된다.

1. s[left] < s[right]일때

이땐 s[left]를 t문자열뒤에 추가해준뒤, left++를 해준다.

2. s[left] > s[right]일때

이땐 s[right]를 t문자열뒤에 추가해준뒤, right--를 해준다.

3. s[left] == s[right] 일때

이땐, left+1과 right-1 부터 천천히 검사를 해준다. 두 문자가 같다면, 두 문자보다 안에있는 문자중에 더 빨리 나오는쪽을 먼저 빼준다면, 사전순서상 앞에 오는 문자열을 완성할 수 있다. 이때 해당 조건이 없다면, 모두 같은 문자이므로 앞뒤중 아무거나 하나를 추가해준뒤 땡겨주면된다.

 

예를들어 bacb 문자열이 있다고 해보자.

그럼 3번 조건에 의해 a와 c를 비교를 해본다. a와 c중 사전상 앞에오는 알파벳은 a이므로, a쪽에있는 b(left)를 빼주면

s="acb" / t="b" 가 된다.

 

다음은 2번조건에 걸려서

s="cb" / t="ba" 가 된다.

 

다음은 2번 조건에 걸려서

s="c" / t="bab" 가 된다.

 

다음은 3번조건에 걸려서

s="" / t="babc" 가 되며, 이것이 사전상 맨 앞에오는 문자열이 된다.

 

 

반응형

 

코드

#include<iostream>
#include<algorithm>
#include<string>
using namespace std;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	string s, t;
	int n;
	cin >> n;
	for (int i = 0; i < n; i++) {
		char data;
		cin >> data;
		s += data;
	}

	int left = 0;
	int right = n - 1;

	while (left <= right) {
		if (s[left] == s[right]) {
			int tl = left + 1;
			int tr = right - 1;
			bool flag = false;//바뀐지 체크해줌
			while (tl <= tr) {
				if (s[tl] < s[tr]) {
					t += s[left++];
					flag = true;
					break;
				}
				else if (s[tl] > s[tr]) {
					t += s[right--];
					flag = true;
					break;
				}
				else {
					tl++;
					tr--;
				}
			}
			if (!flag) {
				t += s[left++];
			}
		}
		else if (s[left] < s[right]) {
			t += s[left++];
		}
		else {
			t += s[right--];
		}
	}
	for (int i = 0; i < t.size(); i++) {
		if (i != 0 && i % 80 == 0) cout << "\n";
		cout << t[i];
	}
	return 0;
}