[백준(BOJ)] 5430번 AC C++

문제 : https://www.acmicpc.net/problem/5430

5430번: AC

 

어떤 문제인가?

 

명령어와 수열을 입력받고 명령어에 맞게 연산을 실행한 후 결과를 출력하면 된다.

 

 

접근 방법

처음에는 벡터에 문자를 저장했다.

그리고 R이 입력될 때마다 reverse함수로 정말 벡터를 역순으로 만들어줬다.

 

당연히 결과는 시간 초과......

 

그래서 다른 방법을 생각하다가 할 수 있는 연산이 2개밖에 없으니

정말 뒤집지 말고 뒤집어졌다고 생각하고 연산을 하기로 했다.

만약 현재 상태가 뒤집어져있는 상태가 아닐 때 D가 입력되면 맨 앞을 지우면 되는 것이고,

뒤집어져있는 상태일 때 D가 입력되면 맨 뒤를 지우면 된다.

 

그래서 pop_front, pop_back 연산이 가능한 deque를 사용하기로 했다.

 

 

 

int t, n;
string p, arr;
cin >> t;

for (int i = 0; i < t; i++) {
    cin >> p;
    cin >> n;
    cin >> arr;

문제에서 주어진 변수들을 선언하고 입력받는다.

 

 

arr 입력이 [1,2,3,4]와 같이 입력되어서 '[', ']', ', '를 처리하여 숫자만 남겨줘야 했다.

 

arr.erase(remove(arr.begin(), arr.end(), '['), arr.end());
arr.erase(remove(arr.begin(), arr.end(), ']'), arr.end());

그래서 erase와 remove 함수를 사용해 먼저 [, ]를 제거했다.

그리고 ,를 기준으로 문자를 나눠야 했다.

자바를 사용했다면 split함수로 간단하게 끝냈을 텐데 c++ 에는 split함수가 없어서 구글의 힘을 빌렸다.

 

deque<string> split(string str, char Delimiter) {
    istringstream iss(str);
    string buffer;

    deque<string> result;

    while (getline(iss, buffer, Delimiter)) {
        result.push_back(buffer);
    }

    return result;
}

deque <string>을 리턴해주는 split함수이다.

 

deque<string> realArr = split(arr, ',');

이제 arr을 ', '을 기준으로 split함수를 통해 나누고, 나누어진 문자들을 realArr이라는 deque에 넣어줬다.

 

bool reverse = false;
bool isPossible = true;

현재 뒤집어져있는지 여부를 판단할 reverse와 수행 가능 여부를 판단할 isPossible을 선언해줬다.

 

for (int j = 0; j < p.size(); j++) {
    if (p[j] == 'R') {
        reverse = !reverse;
    } else if (p[j] == 'D') {
        if (realArr.empty()) {
            cout << "error\n";
            isPossible = false;
            break;
        }
        if (reverse) {
            realArr.pop_back();
        } else {
            realArr.pop_front();
        }
    }
}

먼저 명령어가 R일 때다.

reverse가 true이면 false로, false면 true로 바꿔준다.

 

D가 명령어 일 때이다.

만약 deque가 비어있는데 삭제 연산을 하려고 하는 것이기 때문에 수행 불가능이다.

따라서 error를 출력하고 isPossible을 false로 바꿔준 다음 break로 탈출한다.

 

오류 상황이 아닐 때는 정상적으로 삭제를 해주어야 한다.

이때 reverse변수를 통해 현재 뒤집어져있지 않은 상태라면 pop_front를 통해 맨 앞을 삭제하고

뒤집어져있는 상태라면 pop_back을 통해 맨 뒤를 삭제한다.

 

 

if (isPossible) {
    cout << "[";
}
if (isPossible && reverse) {
    while (!realArr.empty()) {
        cout << realArr.back();
        realArr.pop_back();
        if (!realArr.empty()) {
            cout << ",";
        }
    }

} else if (isPossible && !reverse) {
    while (!realArr.empty()) {
        cout << realArr.front();
        realArr.pop_front();
        if (!realArr.empty()) {
            cout << ",";
        }
    }
}
if (isPossible) {
    cout << "]\n";
}

이제 명령어에 따른 연산을 다 수행하고 반복문을 탈출한 상태이다.

만약 isPossible이 false인 상태로 나왔다면 위의 코드는 실행이 안 될 것이다.

 

그리고 reverse가 true냐 false냐에 따라 출력되는 순서도 바뀐다.

reverse가 true라면 뒤에서부터 출력을 하고

reverse가 false라면 앞에서부터 출력을 하면 끝이다!

 

 

 

무엇이 어려웠는가?

이 문제 같은 경우는 문제를 어떻게 하면 효율적으로 풀 수 있는지 생각해내는 것이 어려웠다.

제한시간을 고려하지 않아도 된다면 아주 쉽게 풀 수 있었지만, 시간제한이 있어 그렇게 간단한 문제가 아니었다.

R 연산을 생각해내는 것이 꽤 오래 걸렸다. 지금 다시 보면 아주 간단해 보이지만.... 

나머지 D연산이나 예외처리 같은 경우는 어렵지 않았다. 

 

 

배운 점

 

문제를 직관적으로 이해하는 것도 좋지만

문제의 숨은 의도를 파악하고 실행시간을 어떻게 하면 줄일 수 있을지 많이 고민해봐야겠다고 느꼈다.

 

물론 "빠르고 정확하게"

 

https://github.com/farmJun/Algorithm_BOJ_PS/blob/main/%EC%8D%B8%EB%A8%B8%EC%BD%94%EB%94%A9/5430.cpp

GitHub - farmJun/Algorithm_BOJ_PS: 백준 알고리즘 문제풀이 기록 레포짓입니다.