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)