- 문제 링크
백준 5430번 - AC
해결 전략
본 문제의 해결 아이디어를 떠올리는 것은 사실 그다지 어렵지 않다. 오히려 이 문제는 알고리즘적 사고가 중요하다기보다는 구현 스킬과 입출력 방식들의 속도 차이 이해가 더 중요한 문제이다.
우선, 문제 해결 알고리즘은 간단하다. 함수 문자열을 받아놓고, 배열 문자열을 받은 후, 거기서 숫자들만 뽑아내서 실제 선형 자료구조를 구축하고, 함수 문자열을 쭉 훑으면서 자료구조에 수정을 가해주면 된다.
이때, 속도 효율 증가를 위한 몇 가지 센스가 있는데,
1) deque이나 list stl을 굳이 사용할 필요가 없다. 이들은 본디 배열보다는 속도가 느리기 때문이다. n이 100,000까지이고, D연산이 한쪽 끝에서만 이루어지기 때문에 출력 시의 인덱스 조정을 해도 되므로 굳이 stl을 쓸 필요가 없다.
2) R연산의 경우, 실제 뒤집기를 하는 것은 절대 하면 안된다. n이 100,000이므로, 한번 뒤집을 때마다 선형 반복이 필요한데, 이것이 누적되면 너무나 느려지기 때문이다. 백프로 시간초과가 날 것이다.
~> R이 짝수번 입력된 상황(즉, 처음 입력 순서와 같은 상황)과 홀수번 입력된 상황(뒤집힌 상황)을 구별해, 짝수 상황일 경우 배열의 앞을 한칸 땡겨주고, 홀수 상황일 경우 배열의 뒤를 한칸 땡겨주면 된다.
~> 출력 시에 인덱싱으로 마치 삭제된 것처럼 꾸밀 수 있기 때문이다.
이런식으로 알고리즘을 간단하게 구현할 수 있다. 몇 가지 예외 상황에서의 출력 조건만 잘 맞춰주면 마무리될 것이다.
오히려, 이 문제의 관건은 처음에 [1,2,3,4,5]같은 식으로 입력되는 문자열의 처리 방법이다. 처음에 본인은 이를 scanf로 ,나 ]문자가 나타나기 전까지 문자열을 잘라서 입력받고, 그 문자열을 sscanf로 정수화하는 방식을 택했다. 결국 시간초과가 났다. 문제가 무엇일까 정말 모르겠었다. 인터넷 서칭을 해보니 다음과 같은 사실을 알 수 있었다.
scanf나 sscanf는 그 자체의 속도는 느린 편이 아니지만, 문자열을 입력받는 경우엔 형식 플래그로 짧게 입력받더라도, 항상 전체 문자열의 길이를 체킹하는 과정이 포함되어 있다는 것이다.
이 사실을 전혀 모르고 있었다. 즉, 요약하자면, scanf나 sscanf는 적어도 문자열을 반복적으로 입력받는 상황에선 속도가 우수하지 못하다는 것이다.
이를 어떻게 해결할까 좀 고민을 해봤는데, 결국 "그냥 cin으로 처리하면 되는 것 아닌가?"라는 생각이 떠올랐다. 그리고 이것이 맞는 방식이었다.
"cin >> char"는 그 문자가 문자열에 포함된 것이더라도, 오로지 하나의 문자만 입력받는다. 즉, scanf에 형식플래그를 두는 Naive한 방식을 굳이 택할 필요가 없던 것이다.
이러한, 평소에 우리가 잘 신경쓰지 않는 구현적 스킬, 문자열 처리 측면의 스킬이 요구되는 문제였다. 이 문제에서 알게 된 새로운 사실들을 앞으로 오래도록 잊지 말자.
아래는 코드이다.
#include <iostream>
#include <string.h>
// BOJ - 5430 AC
using namespace std;
char p[100001];
int lst[100000], lstSize;
void solve(void) {
bool reverse = false;
int left_D = 0, right_D = 0, total, printCnt = 0;
for (int i = 0; i < strlen(p); i++) {
if (p[i] == 'D') {
if (reverse) right_D++;
else left_D++;
}
else {
if (reverse) reverse = false;
else reverse = true;
}
}
total = lstSize - (left_D + right_D);
if (total < 0) { cout << "error\n"; return; }
cout << '[';
if (reverse) {
for (int i = lstSize - right_D - 1; i >= left_D; i--) {
cout << lst[i]; printCnt++;
if (printCnt != total) cout << ',';
}
}
else {
for (int i = left_D; i < lstSize - right_D; i++) {
cout << lst[i]; printCnt++;
if (printCnt != total) cout << ',';
}
}
cout << "]\n";
}
int main(void) {
int t, n; char temp;
ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
cin >> t;
while (t--) {
lstSize = 0; cin >> p >> n;
for (int i = 0; i < n; i++) { cin >> temp >> lst[i]; lstSize++; }
cin >> temp;
if (n == 0) cin >> temp;
solve();
}
return 0;
}
