Algorithm/baekjoon
[BOJ 5430] AC
식빵민
2022. 7. 25. 21:11


https://www.acmicpc.net/problem/5430
5430번: AC
각 테스트 케이스에 대해서, 입력으로 주어진 정수 배열에 함수를 수행한 결과를 출력한다. 만약, 에러가 발생한 경우에는 error를 출력한다.
www.acmicpc.net
문제 분석
- 제한 시간 1초 : Big-O 기준 약 1억
- 테스트 케이스 100개, 수행할 함수 최대 100,000개, 처리할 정수 100,000개
- 수행할 함수 와 처리할 정수의 개수의 합 최대 700,000개
- 목표:
각 함수 수행시간 - O(1) - 계획:
R입력시 재 정렬을 하면 무조건 시간초과가 뜰 것이므로 <deque>를 이용해 앞뒤로 관리
D입력시 가장 앞, 혹은 뒤를 삭제해야하므로 <deque>를 이용해 앞뒤로 관리
R 입력시 bool 변수를 이용해 정순, 혹은 역순으로 관리 - 주의사항
[.,..,...,.]식의 입력을 정수형 배열로 변환해주어야 함
정수형 배열을 [.,..,...,.]식으로 출력해 주어야 함
string arr, num, p;
deque<int> toInt;
int t, n;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cin >> t;
while (t--) {//테스트 케이스 만큼 반복
cin >> p >> n >> arr;
bool r = false; //reverse("R")
bool er = false; //error체크
if (n > 0) {// n=0,문자열 "[]" 이 입력될 경우도 있음
// 문자열 입력을 정수형 deque로 변환
for (int i = 1; i < arr.length(); i++) {
if (arr[i] != ',' && arr[i] != ']') {
num += arr[i];
} else {
toInt.push_back(stoi(num));
num = "";
}
}
}
for (char i: p) {
if (i == 'D') {
if (toInt.empty()) {// deque에 값이 없는데 삭제하라 그러면 error
cout << "error" << "\n";
er = true;
break;
}
if (r)//현재 역순이면
toInt.pop_back();//맨뒤 삭제
else//정순이면
toInt.pop_front();//맨앞 삭제
} else r = !r;
}
if (er)continue;//error 상태면 출력 안함
n = toInt.size();
cout << "[";//[부터 출력
if (!r) {//정순
while (n--) {//deque 크기만큼 반복
cout << toInt.front();//앞에서부터 출력
toInt.pop_front();//출력하면 삭제
if (n > 0) cout << ",";//출력할게 남아있으면 쉼표 출력
}
} else {//역순
while (n--) {
cout << toInt.back();
toInt.pop_back();
if (n > 0) cout << ",";
}
}
cout << "]" << "\n";//출력 끝나면 "]"출력
}
return 0;
}
문제를 풀면서 쉽게 생각해내지 못한 예외가 "n=0" 이다.
그러다 0이면 error가 발생한다고 생각했다가 "틀렸습니다"를 보았다. ㅠㅠ
사실 n에 0을 입력하고 []를 입력하고 R만 시행해주면 error가 발생하지 않아야 한다.
그래서 입력시에 n이 0이 아닐때 수열을 입력받게 했고, 위와 같이 코드를 바꿨더니 "맞았습니다"를 봤다!!^^
느낀 점
- <deque>쓰는데에 있어서 슬슬 익숙해지기 시작했다.
- 이 문제를 풀면서 string입력을 정수형으로 바꿔주는데에 애를 먹었는데 덕분에 stoi()라는 함수를 알게 됐다.
- 처음부터 시간복잡도를 어느정도 계산하면서 푸니까 풀이방식 생각하는데에는 시간이 오래걸렸지만 "시간초과"가 뜨는 것을 방지 할 수 있어 푸는 시간이 오히려 짧아 진거 같다.
시간 복잡도
- t번 반복하는 while문
- 문자열->정수 : O(n)
- 함수 수행 : O(n)
- 출력 : O(n)
➣ 약 O(n^2)
함수 수행+처리할 수의 개수 ≤ 700,000
테스트 케이스 ≤ 100
➣ 약 O(70,000,000)