컴공댕이 공부일지
[ C++/cpp ] 백준 (5430 AC) ⭐구현, 덱 본문
백준 5430번 AC
(골드 5)
https://www.acmicpc.net/problem/5430
(정답 코드)
#include <iostream>
#include <deque>
using namespace std;
string solution(string &p, int &n, string &arr) {
deque<int> dq;
string ans = "[";
string num = "";
bool is_reverse = false;
// 숫자 배열 벡터에 차례로 저장
for(int i=1; i<arr.length()-1; i++) {
while(arr[i]!=',' && arr[i]!=']') { // 구분자 나올때까지 i++
num += arr[i];
i++;
}
dq.push_back(stoi(num));
num = "";
}
// RD 명령 수행
for(int i=0; i<p.size(); i++) {
// reverse
if(p[i]=='R') {
is_reverse = !is_reverse;
}
// delete
else {
if(dq.empty()) { // 더이상 지울 요소가 없다면 에러 출력
return "error";
}
is_reverse ? dq.pop_back() : dq.pop_front() ;
}
}
// 최종 배열 담기
if(is_reverse) {
while (!dq.empty()) {
ans+= to_string(dq.back());
dq.pop_back();
if(dq.empty()) {
break;
}
ans += ',';
}
} else {
while (!dq.empty()) {
ans+= to_string(dq.front());
dq.pop_front();
if(dq.empty()) {
break;
}
ans += ',';
}
}
return ans+']';
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
int t, n;
string p;
string arr;
cin >> t;
while(t--) {
cin >> p >> n >> arr;
cout << solution(p, n, arr) << '\n';
}
return 0;
}
📖 트러블 슈팅
1. 문자열 파싱 오류
구분자 ',' 기준으로 끊어 입력받기
### 수정 전 ###
for(int i=1; i<2*n; i+=2) {
v.push_back(arr[i]);
}
### 수정 후 ###
for(int i=1; i<arr.length()-1; i++) {
while(arr[i]!=',' && arr[i]!=']') { // 구분자 나올때까지 i++
num += arr[i];
i++;
}
v.push_back(stoi(num));
num = "";
}
숫자 배열을 입력해주는 방식이 특이했는데 쉼표를 구분자로 숫자값을 받아야한다. 한자리 수만 삽입되는 게 아니고 [10,20] 이런식일 수도 있는데.. 근데 간과하고 첨에 홀수 번 스트링의 인덱스만 취급해서 틀림..ㅋㅋ 졸린가...?
2. 시간 초과 해결하기
매번 벡터를 뒤집지말고, flag 변수로 뒤집힘 여부 표시만 하기
매순간 reverse 함수로 벡터를 실제로 뒤집었다. 근데 뭐 시뮬레이션 할 필요 없이 단순히 지우고 뒤집는 연산 뿐이니, 그래서 그냥 뒤집음 상태를 bool타입으로 저장해두는 방식으로 바꿈.
- reverse : 원본 벡터는 그대로 두고 뒤집힘 여부에 따라 출력 시 인덱스만 정방향/역방향 순회하면 된다.
- delete : 뒤집힘 여부에 따라 삭제 시 맨 앞에, 맨 뒤에 둘 중 하나를 지우면 된다.
### 수정 전 ### 실제로 벡터를 reverse 함수로 뒤집음.
for(int i=0; i<p.size(); i++) {
// reverse
if(p[i]=='R') {
reverse(v.begin(), v.end()); // 벡터 뒤집기
}
// delete
else {
if(v.empty()) { // 더이상 지울 요소가 없다면 에러 출력
return "error";
}
v.erase(v.begin()); // 첫번째 요소 삭제
}
}
### 수정 후 ### 실제로 뒤집지 않고 is_reverse로 뒤집힘 여부만 체크해놓고 삭제 연산도 이를 토대로 한다.
for(int i=0; i<p.size(); i++) {
// reverse
if(p[i]=='R') {
is_reverse = !is_reverse;
}
// delete
else {
if(v.empty()) { // 더이상 지울 요소가 없다면 에러 출력
return "error";
}
is_reverse ? v.erase(v.end() -1) : v.erase(v.begin()) ;
}
}
3. 더 빠른 코드 ?
- 삭제 연산 시간 단축을 위해 deque 사용하기
맞긴 했는데 너무 오래걸리네 더 효율화할 순 없을까?
기존 코드 시간이 너무 오래 걸리길래, 문제가 뭘까 했더니 벡터의 erase였다.
벡터는 끝 요소 삭제는 상관없지만, 중간이나 앞에서 요소를 삭제하면 그 뒤의 모든 요소를 당겨서 이동시켜야 하므로 O(n) 시간 복잡도를 가진다. 그래서 erase가 시간을 왕창 잡아먹는것. 그래서 ... deque를 썼다. 덱은 양쪽 끝에서 다 삭제가 O(1)의 시간 복잡도를 갖는다. - 새삼 자료구조 때 배운 내용 복기
아님 그냥 벡터를 쓰고, 요소를 굳이 안지우고 start, end 등의 범위 인덱스 변수를 사용해도 된다. 뒤집힌 상태로 삭제하면 start를 한 칸 움직이고, is_reverse가 false면 안뒤집혀있으니 end를 한 칸 당기고 이런식으로. 투포인터처럼? 근데 그냥 디큐 쓰는 게 깔끔하다. 맨 위에 첨부한 정답 코드가 디큐 사용한 버전이다. 실제로 시간이 기존에 벡터보다 700ms에서 32ms로 줄었다. 굿.
아 디큐 쓰다가 또 깜빡한건데, for반복문으로 완전탐색할 때, size()변수 함부로 쓰면 안된다. pop하면서 자료구조의 size가 변동되니까 반복 덜 돌았는데 막 종료되고 그래버린다. 기초적인 내용인데 벡터처럼 습관적으로 size 쓰다가 바부같은 실수가 나오는 포인트...ㅎ back()로 값 취한 뒤에 pop 해주는 것도 잊지말기.
// 최종 배열 담기
if(is_reverse) {
while (!dq.empty()) {
ans+= to_string(dq.back());
dq.pop_back();
if(dq.empty()) {
break;
}
ans += ',';
}
} else {
while (!dq.empty()) {
ans+= to_string(dq.front());
dq.pop_front();
if(dq.empty()) {
break;
}
ans += ',';
}
}
공부하기 싫으니 ps가 넘 재밋구 .. 컴네 공부하기 실탓 구현문제나 풀고싶다 ㅎㅎ..
'문제 풀이 > 코딩 문제 풀이 모음' 카테고리의 다른 글
[ C++/cpp ] 백준 (11726 2×n 타일링) ⭐다이나믹프로그래밍 (0) | 2024.10.10 |
---|---|
[ C++/cpp ] 백준 (1654 랜선 자르기) ⭐이분 탐색 💦 (0) | 2024.07.20 |
[ C++/cpp ] 백준 (11561 좌표 정렬하기2) ⭐pair vector 정렬, 비교함수 (0) | 2024.07.18 |
[ C++/cpp ] 백준 (2108 통계학) ⭐최빈값 구하기, 최장 길이 부분 수열 (0) | 2024.07.11 |
[ C++/cpp ] 백준 (1018 체스판 다시 칠하기) ⭐브루트포스 알고리즘 (1) | 2024.03.29 |