[G4] 백준 6137번 문자열 생성 C++ 덱, 문자열, 투 포인터

리뷰

 

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

문자열의 앞이나 뒤에서 문자를 하나씩 가져와 사전순으로 가장 빠른 문자열을 만드는 문제

 

 

전역 변수

• s : 초기 문자열을 저장할 덱
• t : 완성된 문자열을 저장할 문자열
• c : 각 문자를 입력 받기 위한 변수
• n : 문자열의 길이를 저장할 변수

 

함수

없음

 

 

문제풀이

1. n값을 입력 받고, n개의 문자를 c에 입력 받아 덱 s의 뒤에 push해준다.
2. s가 빌때까지 while루프를 수행하고, 변수 f, b에 덱의 맨 앞과 맨 뒤의 문자를 저장한다.
3. f가 b보다 클 경우 t에 b를 추가하고, s의 맨 뒤 요소를 제거한다.
4. b가 f보다 클 경우 t에 f를 추가하고, s의 맨 앞 요소를 제거한다.
5. f와 b가 같을 경우 중앙에서 만날때까지 요소를 비교하며 더 작은 요소가 먼저 나오는 쪽의 문자를 t에 추가하고, 추가한 요소를 덱에서 제거한다.
6. t의 크기가 80이상이 되었을 경우 t를 출력 후 개행문자를 삽입하고, t를 clear()처리한다.
7. while루프가 종료된 후 t에 남아있는 문자열을 출력한다.

 

트러블 슈팅

없음

 

 

참고 사항

1. 문자열 전체가 팰린드롬 형태라면 터질 수도 있다고 생각했는데 N이 2000이하라 충분할 것이라 판단했다.
2. 만들어진 사전순으로 가장 빠른 문자열을 출력한다. 80글자마다 새줄 문자를 출력해야 한다.
3. 오른쪽 이터레이터를 end()로 잡아줬다면 값을 참조할땐 오프셋을 한번 줄여줘야 마지막 요소를 반환한다.

 

정답 코드

#include<iostream>
#include<deque>
using namespace std;

deque<char> s;
string t;
char c;
int n;

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

	cin >> n;
	for (int i = 0; i < n; ++i) {
		cin >> c;
		s.push_back(c);
	}

	while (!s.empty()) {
		char f = s.front();
		char b = s.back();

		if (f > b) {
			t += b;
			s.pop_back();
		}
		else if (f < b) {
			t += f;
			s.pop_front();
		}
		else {
			bool flag = true;
			auto l = s.begin();
			auto r = s.end();
			--r;

			while (l < r) {
				if (*l > *r) break;
				else if (*l < *r) {
					flag = false;
					break;
				}
				++l;
				--r;
			}

			if (flag) {
				t += b;
				s.pop_back();
			}
			else {
				t += f;
				s.pop_front();
			}
		}

		if (t.size() >= 80) {
			cout << t << "\n";
			t.clear();
		}
	}

	if (!t.empty()) cout << t;
}