이번에는 백준 5430번 AC 문제를 풀어보았습니다.
처음에는 R 명령이 나올 때마다 실제로 배열을 뒤집으면 되겠다고 생각했습니다.
하지만 R의 개수가 많아질 경우 계속 뒤집는 연산이 발생하여 비효율적이었습니다.
그래서 실제로 뒤집지 않고 현재 배열이 뒤집힌 상태인지만 reverse_flag로 관리하도록 구현하였습니다.
이후 D 연산은 현재 방향에 따라 앞이나 뒤에서 하나를 제거하는 방식으로 해결하였습니다.
문제 설명
정수 배열과 명령어가 주어집니다.
명령어는 다음 두 가지입니다.
R: 배열을 뒤집는다.D: 첫 번째 원소를 제거한다.
배열이 비어있는 상태에서 D를 수행하면 error를 출력해야 합니다.
최종 배열의 상태를 출력하는 문제입니다.
풀이 아이디어
입력받은 문자열에서 [와 ]를 제거한 뒤 ,를 기준으로 분리하여 deque에 저장하였습니다.
R 명령은 실제로 배열을 뒤집지 않고 reverse_flag만 변경하였습니다.
D 명령은 현재 방향에 따라 앞이나 뒤에서 원소를 제거하였습니다.
모든 명령이 끝난 뒤 뒤집힌 상태라면 한 번만 reverse를 수행하여 출력하였습니다.
코드
#include <bits/stdc++.h>
using namespace std;
int T;
deque<int> split(string s, char delim){
deque<int> return_vec;
auto start = 0;
auto end = s.find(delim);
while(end != string::npos){
return_vec.push_back(stoi(s.substr(start, end - start)));
start = end + 1;
end = s.find(delim, start);
}
return_vec.push_back(stoi(s.substr(start)));
return return_vec;
}
int main() {
cin >> T;
for (int i = 0; i < T; i++) {
string func, inp_num;
int inp_num_cnt;
bool flag = true;
bool reverse_flag = false;
cin >> func >> inp_num_cnt >> inp_num;
inp_num = inp_num.substr(1, inp_num.size() - 2);
deque<int> ret;
if (inp_num.size())
ret = split(inp_num,',');
for (int j=0; j<func.size(); j++) {
if (func[j] == 'R' && ret.size()) {
reverse_flag = !reverse_flag;
}
else {
if (ret.empty()) {
flag = false;
break;
}
if (reverse_flag)
ret.pop_back();
else
ret.pop_front();
}
}
if (reverse_flag)
reverse(ret.begin(), ret.end());
if (flag) {
cout << "[";
for (int k=0; k<ret.size(); k++) {
if (k != ret.size() - 1)
cout << ret[k] << ",";
else
cout << ret[k];
}
cout << "]\n";
}
else {
cout << "error" << '\n';
}
}
return 0;
}풀이 흐름
- 입력 문자열에서
[와]를 제거합니다. - 문자열을
,기준으로 분리하여 deque에 저장합니다. - 명령을 하나씩 수행합니다.
R은 방향만 변경합니다.D는 현재 방향에 따라 앞이나 뒤의 원소를 제거합니다.- 모든 명령이 끝난 뒤 필요한 경우 한 번만 배열을 뒤집습니다.
- 결과를 출력합니다.
구현 포인트
1. 문자열을 deque로 변환
입력 문자열에서 대괄호를 제거한 뒤 split 함수를 이용하여 숫자를 deque에 저장하였습니다.
inp_num = inp_num.substr(1, inp_num.size() - 2);
if (inp_num.size())
ret = split(inp_num, ',');이후 deque를 이용하여 앞과 뒤에서 모두 삭제할 수 있도록 구현하였습니다.
2. 뒤집기 연산 처리
R 명령이 들어왔다고 해서 실제로 배열을 뒤집지는 않았습니다.
if (func[j] == 'R' && ret.size()) {
reverse_flag = !reverse_flag;
}현재 배열이 뒤집힌 상태인지만 저장하도록 구현하였습니다.
3. 삭제 연산 처리
현재 방향에 따라 삭제 위치를 다르게 하였습니다.
if (reverse_flag)
ret.pop_back();
else
ret.pop_front();실제로 배열을 뒤집지 않아도 같은 결과를 얻을 수 있습니다.
4. 에러 처리
배열이 비어있는 상태에서 D 연산이 수행되면 바로 종료하였습니다.
if (ret.empty()) {
flag = false;
break;
}이후 "error"를 출력하도록 구현하였습니다.
5. 마지막에 한 번만 뒤집기
모든 명령이 끝난 뒤 뒤집힌 상태라면 한 번만 reverse를 수행하였습니다.
if (reverse_flag)
reverse(ret.begin(), ret.end());중간마다 뒤집지 않고 마지막에 한 번만 수행하여 불필요한 연산을 줄일 수 있었습니다.
