[5430번] AC

5430번: AC

 

www.acmicpc.net

#include <iostream>
#include <string>
#include <vector>
using namespace std;
vector<int>v;
int T, n, input_num, front_p , end_p, dir_flag, error_flag; // dir = 0 : -> , 1 : <-
string command, input_number_arr, temp_num;

int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	cin >> T;
	for (int t = 0; t < T; t++) {
		cin >> command;
		cin >> n;
		cin >> input_number_arr;
		dir_flag = 0;
		error_flag = 0;
		front_p = end_p = -1;
		//입력
		if (n > 0) {
			//문자열 number의 처음은 고정으로 '[' 이기 때문에 범위에서 제외하고 시작, 마지막 ]는 숫자를 저장하기 위한 트리거로 남겨놓음
			for (int i = 1; i < input_number_arr.size(); i++) {
				if (input_number_arr[i] == ',' || input_number_arr[i] == ']') {
					int made_num = stoi(temp_num);
					v.push_back(made_num);
					temp_num.clear();
				}
				else {
					temp_num.push_back(input_number_arr[i]);
				}
			}
		}
		if (n != 0) {
			front_p = 0;
			end_p = v.size() - 1;
		}
		//명령어 진행
		for (int c = 0; c < command.size(); c++) {
			if (command[c] == 'R') {
				if (dir_flag == 0) {
					dir_flag = 1; //정방향 -> 역방향
				}
				else {
					dir_flag = 0; //역방향 -> 정방향
				}
			}
			else {//command == D
				if (front_p == -1 && end_p == -1) {
					cout << "error" << '\n';
					error_flag = 1;
					break;
				}
				else {
					if (dir_flag == 0) {
						front_p++;
					}
					else {
						end_p--;
					}
					if (front_p > end_p) front_p = end_p = -1;//front_p가 end_p값보다 크다는 것은 배열이 비었다는 것.
				}
			}
		}
		//출력
		if (error_flag == 0) {
			if (front_p != -1) { //배열이 비지 않았을 때
				cout << '[';
				if (dir_flag == 0) {
					for (int i = front_p; i < end_p; i++) cout << v[i] << ',';
					cout << v[end_p] << ']' << '\n';
				}
				else {
					for (int i = end_p; i > front_p; i--) cout << v[i] << ',';
					cout << v[front_p] << ']' << '\n';
				}
			}
			else cout << "[]" << '\n';//배열이 비었을 때

		}
		//초기화 부분
		v.clear();
		command.clear();
	}
}

풀이과정

1.

입력 받을 때 1-100까지 숫자이므로 단순히 스트링을 한칸씩 읽어 저장하면 2자리 이상의 숫자가 제대로 저장되지 않는다.

그렇기 때문에 ',' 와 ']'를 트리거 삼아 해당 문자를 만나기 전까지 문자(숫자)를 따로 문자열에 저장을 하고 특수 문자를 만나면 그 문자열을 stoi 함수를 이용해서 숫자로 변환해 벡터에 저장한다.

2.

문자열을 벡터에 다 입력을 했으면 배열의 처음과 끝 인덱스를 front_p, end_p에 저장해준다.

3.

들어온 명령을 하나씩 읽으면서 반복진행하는데

R일 경우 현재 탐색 진행 방향이 정방향(->) 일 경우 dir_flag를 1로  역방향(<-)일 경우 0으로 바꿔준다.  

(dir_flag == 0 : 정방향 , dir_flag == 1 : 역방향)

D일 경우 배열이 비어있는지를 판별해서 비어 있지않으면 진행 방향에 따라 front_p와 end_p를 움직여 준다.

(front_p가 end_p보다 크면 배열이 빈 경우, 이 때 front_p와 end_p를 -1로 만들어 준다.)

4. 출력은 배열이 비었을 때와 비어 있지 않을 때를 나눠서 출력한다.

 

이 문제를 풀때는 벡터를 진짜 뒤집거나, 원소를 삭제하지 않고 인덱스를 가르키는 변수를 이용해서 뒤집거나 삭제된 것 처럼 풀면된다.

실제 reverse 함수를 쓰는 경우 시간초과가 발생한다.

백준 질문게시판에 적혀있는 주의점이다.

1. R 명령이 들어온다고 진짜로 배열의 모든 원소를 뒤집으면 절대로 안 됩니다. N개의 원소의 순서를 정말로 바꾸면 당연히 그 원소 수만큼 시간이 걸리고, 그걸 최대 10만 번 수행해야 하니 테스트 케이스 1개만으로도 100억번의 연산이 수행됩니다. R 명령의 핵심은 실제로 원소를 뒤집지 않고도 뒤집힌 것과 같은 효과를 내도록 구현하는 것입니다. std::reverse() 역시 사용해서는 안 됩니다.
2. D 명령에 대해서 보통 배열의 맨 앞 원소를 무작정 지워서는 안 됩니다. C++의 vector::erase(), Java의 ArrayList.remove(), Python의 list.pop() 등으로 배열의 첫 번째 원소를 지울 시, 그 뒤에 있는 모든 원소들을 전부 한 칸씩 앞으로 당겨오게 되므로, 그 시간 역시 원소의 수에 비례하여 소요됩니다. 라이브러리 함수는 호출만 하면 N개의 원소를 기적같이 O(1)에 처리해주는 마법사가 아닙니다. 저렇게 원소를 당겨오는 작업 없이도 D의 기능을 구현할 수 있어야 합니다.
3. 빈 배열은 []로 출력해야 합니다. 아무것도 출력하지 않거나 error를 출력하면 안 됩니다.
4. 배열이 비어있는데 R을 하는 건 에러가 아닙니다.
5. 테스트 케이스마다 초기화가 잘 됐는지 확인하세요. 그리고 매 케이스마다 개행 문자를 항상 출력하는지 확인하세요.
6. 처음 배열의 상태에 대한 문자열의 길이는 최대 400001자입니다. 입력 문자 배열 크기를 잘 설정하세요.
7. 처음 배열의 상태로 빈 배열이 주어지는 경우를 조심하세요. 수가 무조건 하나 이상 있다고 가정하고 코드를 작성하면 이런 경우를 제대로 처리하지 못할 수 있습니다.
8. 조건문 안에 strlen(str) 를 절대로 넣지 마세요. strlen은 문자열의 처음부터 널 문자가 나올 때까지 한 글자씩 확인하므로, 반복문을 한 바퀴 돌 때마다 문자열의 길이만큼의 시간이 걸립니다.
9. 단순히 R과 D의 개수만 세고 나중에 몰아서 처리하는 건 당연히 안 됩니다. R을 할 때마다 D를 했을 때 지워지는 원소가 달라지기 때문입니다.'
10. 배열에 들어있는 수는 최대 100입니다. 무조건 한 글자로 가정하고 구현하면 안 됩니다. 참고로, 예제에도 두자리의 수가 하나 등장하지만 어차피 지워지는 원소이기 때문에 한 글자로 가정해도 "예제는" 답이 잘 나올 수 있습니다. 예제를 믿지 마세요.