[백준 / #5430 / C++] AC

이번 문제는 자료구조에 관한 문제이다.

 

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

5430번: AC

 

문제 해석:

 

 

문제에서 테스트 케이스의 수 T 가 주어지면 주어진 수 만큼 연산을 실행해야한다. T는 최대 100이며 함수 P는 최대

 

100,000이다. 함수 P에서 R이 나오면 배열을 반대로 뒤집고, D가 나오면 배열에서 원소를 삭제해야한다. 만일 모든 R 함수

 

에 대해 배열을 하나하나 뒤집으려 한다면 시간 초과는 당연할 것이다. 그렇다면 어떻게 접근하는가? 바로 데큐(Double-

 

Ended Queue)를 사용하면 쉽게 접근할 수 있다. R 함수를 실행하여 위치를 변경해주고 D 함수를 실행한다면 단순히 뒤쪽

 

에서 원소를 삭제해주고 출력을 뒤에서부터 하면 되기 때문에 R 연산이 쉬워진다.

 

 

 

알고리즘 해석 및 코드:

 

 

 이 코드를 해설할 때 다루고 싶었던 부분이 있다. 바로 isdigit() 함수이다. isdigit() 함수는 char 형의 자료가 만약 십진수\

 

의수로 변환이 가능하다면 true를 반환하고 아니라면 false를 반환한다. 이러한 함수를 이용해 문제에서 주어진 배열을 입

 

력받아 데큐로 넣는다. 데큐에 삽입할 때 주의할 점은 string이 비어있을 때만 삽입해야 한다는 점이다. 그렇지 않으면

 

string이 비어있어도 데큐에 삽입하게 되므로 빈 string 하나의 연산이 추가된다.

 

 

  이제 주어진 함수 P를 하나씩 따라간다. 만약 R일때 int sig가 0 (코드에서 0을 앞쪽으로 나타내었음) 일 때, sig를 1 즉, 뒤

 

쪽을 가르키도록 하였고 마찬가지로 sig가 1일때는 0이 되도록 하였다. 그 후 D 연산을 만난다면 삭제해야 하므로 sig의 값

 

을 확인해 현재 어느 위치를 가르켜야 하는지 확인하였고, 만약 sig가 0이면 pop_front(), 1이면 pop_back() 연산을 실행하

 

여 문제의 요구 조건에 맞춰주었다. 그런데 만약 이미 데큐가 비어있는데 D 함수를 실행하면 error를 출력해야 하므로 출력

 

한 후 sig를 3으로 바꿔 이미 error를 출력하였음을 알려주었다. 모든 연산이 끝난 후 만약 sig가 3이 아니면 (error를 출력하

 

지 않았다면) 데큐에 남아있는 수들을 출력해주었는데 이 때도 sig 값을 확인하여 앞/뒤에서부터 출력을 해준다.

 

 

 

 

문제는 비교적 쉬웠으나 입력받은 배열에서 수만 추출해내는 isdigit()함수와 데큐에 넣어줄 때 string이 비어있지 않을 때만

 

넣어주는 조건을 생각해내지 못해 시간이 조금 걸렸다. 이러한 부분만 조심하면 금방 풀 수 있을 것이다,