[백준] 5430번: AC C++로 풀어보기

5430번 설명

생각

이 문제에서 해결해야 될 문제는 크게 두 가지다.

1. [숫자,숫자,숫자...]를 입력받고 어떻게 숫자만 쏙 빼서 덱에 넣을까?

2. 뒤집는 것과 지우는 것을 어떻게 구현하면 될까?

 

---

처음에는 1번 문제를 어떻게 풀었냐면,

1.  string으로 배열을 입력받는다.

2. '[', ',' ']'가 아니면 숫자로 바꿔서 덱에 push한다.

하지만 이렇게 하면 문제가 있다. 만약 두 자리 수의 숫자가 들어왔을 경우에도 숫자를 따로따로 인식하게 되기 때문이다.

 

그래서 어떻게 풀었냐면,

 

1. string으로 배열을 입력받는다.

2. ',', ']'가 아니면 또 다른 string 변수에 더해준다.

3. 만약 ',' 나 ']'이 나오면 string 변수를 stoi로 int로 바꿔주고 덱에 push한다.

4. string 변수를 초기화해준다.

---

2번 문제는 어떻게 풀어야할까?

 

처음에는 2번 문제를 어떻게 풀었냐면,

1. 지우는 것은 그냥 pop하면 되겠지.

2. 뒤집는 것은 덱의 front에서부터 전부 pop해서 또 다른 스택에 넣어준다.

3. 그리고 스택의 top을 pop해서 다시 덱에 넣어준다.

이렇게 풀면 어떤 문제가 생기냐면, 일단 시간초과가 날 가능성이 크다. 그리고 n이 0일 때의 처리를 안해줬기 때문에 오답처리된다.

 

그래서 어떻게 풀었냐면,

1. 일단 n이 0일 때를 따로 처리해줘야한다.(중요!! 정답률이 19%인 이유 중 하나.)

2. n이 0일 때 명령어가 R만 나온다면 그냥 '[]'를 출력하고, D가 한번이라도 나오면 'error'를 출력해야한다.

(이 때 마지막에 continue를 입력해야 한다. 마지막에 break로 했다가 16%에서 자꾸 틀려서 왜 틀렸는지 찾느라 1시간 걸렸다. 하필 예제 입력이 마지막에 n이 0일 때를 테스트해서 못 알아 챘었다.)

 

3. bool isreversed를 따로 하나 생성한다.(초기값은 false)

4. R이 나오면 isreversed를 true로 해준다.

5. D가 나왔을때 isreversed가 false라면 front를 pop해주고,

6. D가 나왔을때 isreversed가 true라면 back을 pop해준다.

7. 출력할 때에도 isreversed가 false라면 덱을 차례대로 출력하고,

8. isreversed가 true라면 덱을 거꾸로 출력해줘야한다.

9. 마지막으로 출력해줄 때도 문제인데, 처음에 나는 ','를 없애기 위해 '\b'를 사용했는데, 이러면 안 된다.(이러면 또 오답처리된다!)

10. 덱이 마지막으로 출력할 때에만 ','가 아닌 ']'를 출력하게 만들면 된다.

 

코드

#include <bits/stdc++.h>
using namespace std;


int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	deque <int> d;
	stack <int> s;
	string p;
	string ans;
	string strtemp = "";
	int n = 0;
	bool isreversed = false;
	int t;
	bool iserror = false;

	cin >> t; // 테스트 케이스의 개수

	while (t--) { // 테스트 케이스 횟수 동안 루프

		isreversed = false;
		iserror = false;

		if (!d.empty()) {
			d.clear(); // 덱 초기화
		}

		cin >> p; // 수행할 함수
		cin >> n; // 배열에 들어있는 수의 개수
		cin >> ans; // 배열에 들어있는 정수

		if (n == 0) { // n이 0일 때
			for (int i = 0; i < p.length(); i++) {
				if (p[i] == 'D') { // D가 한번이라도 나왔을 경우
					iserror = true;
					cout << "error" << "\n"; // error 출력
					break;
				}
			}

			if (iserror == false) { // D가 한번이라도 나오지 않았을 경우
				cout << "[]" << "\n"; // [] 출력
			}

			continue; // 여기 실수로 break로 했다가 1시간 날려먹었다..
		}


		for (int i = 0; i < ans.length(); i++) { // ans에 숫자들만을 추출해서 덱에 push
			if (ans[i] != ',' && ans[i] != '[' && ans[i] != ']') {
				strtemp += ans[i];
			}

			else if (ans[i] == ',' || ans[i] == ']') {
				d.push_back(stoi(strtemp));
				strtemp = "";
			}
		}

		for (int i = 0; i < p.length(); i++) { // 수행할 함수를 읽기 위한 loop
			if (p[i] == 'R') { // 만약 R이라면
				isreversed = !isreversed;
			}
			else if (p[i] == 'D') { // 만약 D라면

				if (d.empty()) { // 덱이 비어있다면
					cout << "error" << '\n';
					iserror = true;
					break;
				}

				else if (!d.empty() && isreversed == false) { // 뒤집어져있지 않을 때
					d.pop_front();
				}
				else if (!d.empty() && isreversed == true) { // 뒤집어져 있을 때
					d.pop_back();
				}
			}
		}

		if (iserror == false && d.empty()) { // error가 나지않았고 배열이 비어있을 경우
			cout << "[]" << "\n";
		}
		
		else if (iserror == false && !d.empty() && isreversed == false) { // 뒤집어져있지 않을 때
			cout << "[";
			for (int i = 0; i < d.size(); i++) {
				cout << d[i];
				if (i != d.size() - 1) {
					cout << ',';
				}
				else {
					cout << ']' << '\n'; // 마지막에만 
				}
			}
		}
		else if (iserror == false && !d.empty() && isreversed == true) { // 뒤집어져있을 때
			cout << "[";
			for (int i = d.size() - 1; i >= 0; i--) {
				cout << d[i];
				
				if (i != 0) {
					cout << ',';
				}
				else {
					cout << ']' << '\n'; // 마지막에만
				}
			}

		}
	}
}

 

결과

5430번 결과

왜 정답률이 19%인지 알겠다... 역대급으로 현타가 온 문제였다.