백준 5430 AC c++ [컴공과고씨]

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

5430번: AC

 

문제 정리

배열이 주어짐.

명령어가 주어짐.

명령어는 문자열 형태로 R은 배열 뒤집기 D는 배열의 맨 앞 원소 빼기 두 가지로 구성됨.

명령어를 수행후 남은 배열 원소를 구해라.

단, 원소가 없을 때 D가 수행되면 error를 출력하라.

 

문제 해결 방법

이 문제 같은 경우는 deque를 이용해서 풀 수 있습니다.

저 같은 경우는 인덱스를 조작을 이용해서 deque를 사용하지 않고 풀었습니다.

deque는 queue와 비슷하지만 다른 점은 양쪽에서 pop과 push를 사용할 수 있습니다.

 

제가 푼 방식과 deque를 이용한 방법 모두 문제를 푸는 큰 틀은 같기 때문에 제가 푼 방법으로 설명하겠습니다.

이 문제는 사실 문제의 해결 방법은 쉬운데 문자열을 받고 출력하는 부분을 잘 체크해 주어야 합니다.

 

1. 입력 배열 숫자로 바꾸기

먼저 명령어와 주어진 배열을 string으로 받아 줍니다.

주어지는 배열을 보면 [1,2,3] 이런 식으로 주어지기 때문에 숫자만 분리해주어야 합니다.

string으로 받아 하나씩 읽으면서 숫자면 string 변수에 +를 해줍니다. 이유는 [100,99] 이런식으로 한 자리 숫자가 아닐 경우 때문입니다. 그 후 숫자가 아닌 것이 나오면 모아둔 숫자를 int형으로 바꾸어주고 배열에 넣어 줍니다.

 

2. 명령어 수행

명령어를 수행하기 앞서 시작 인덱스와 끝 인덱스를 정해줍니다.

만약 배열에 있는 숫자가 1,2,3,4 라면 시작 인덱스는 0, 끝 인덱스는 3. 이런식으로 만들어줍니다.

그리고 숫자가 하나도 없는 경우 끝 인덱스를 -1로 만들어줍니다.

 

이렇게 한 후 D가 나오기 전까지 R의 개수를 세어줍니다.

그 후 D가 나오면 앞의 R의 개수가 짝수개이면 뒤집을 필요가 없고 홀수개면 뒤집어 주어야 하기 때문에

시작 인덱스와 끝 인덱스를 바꾸어 줍니다.

 

그 후 먼저 원소가 하나도 없는지 확인합니다. 원소가 하나도 없다면 error를 출력해 주어야 함으로 표시를 위해 끝 인덱스를 -1해줍니다.

원소를 빼는 경우 맨 앞에서 빼주어야합니다.

시작 인덱스가 더 크면 시작 인덱스 -1를 해주면 되고 시작 인덱스가 더 작다면 시작 인덱스에 +1을 합니다.

만약 둘다 같다면 마지막 원소이므로 끝 인덱스를 -1로 만들어주어서 원소가 비었다고 표시해 줍니다.

 

마지막으로 명령어 수행이 끝난 후 위에서는 D가 나올때 까지 R의 개수를 세어 D가 나오면 R을 처리했기 때문에

명령어가 RDRRR이런식으로 D가 나오지 않고 R에서 끝난 경우가 있습니다.

그래서 마지막에 남은 R명령어를 처리를 해주어야합니다. 

 

예를 들면 1,2,3,4 가 있을 때 명령어가 RD라고 하면 시작 : 0, 끝 : 3 

먼저 R이 홀수이기 때문에 시작과 끝을 바꾸어주면 시작: 3, 끝: 0 이 되고

시작이 끝 보다 크기 때문에 -1을 해서 시작 : 2, 끝 0 이 됩니다. 그 후 시작 부터 끝까지 출력해주면

3,2,1이 나오게 됩니다.

 

그 후 출력하는 부분입니다.

끝이 -1 이라면 원소가 비어있음을 출력.

끝이 -2 라면 error 출력

그 후 시작과 끝의 인덱스 크기 비교 후 그 사이의 값을 출력해주면됩니다.

 

만약 deque를 사용한다면 D가 나올때까지 R의 개수를 세어서 뒤집기라면 뒤에서 빼주고 뒤집지 않으면 앞에서 빼주면 됩니다.

 

전체코드

#include <iostream>
#include <string>
using namespace std;
int main(){
    int T;
    cin >> T;
    for (int t = 0; t < T; t++){
        int n;
        string p, a;
        int num[100002] = {0};
        cin >> p;
        cin >> n;
        cin >> a;
 
        int idx = 0; // 배열 인덱스
        int tdx = 0; // 명령어 인덱스
        string tm = "";
        while(a[tdx] != ']'){
            if(a[tdx] == '[')
                tdx++;
            else if(a[tdx] == ','){
                num[idx] = stoi(tm); // int 형 변환 후 배열에 저장
                idx++; 
                tdx++;
                tm = "";
            }else{
                tm += a[tdx]; // 숫자 +
                tdx++;
            }
        }
        // 마지막 숫자 배열에 저장
        if(tm != ""){
            num[idx] = stoi(tm);
            idx++;
        }
 
        int start_pos = 0; // 시작 인덱스
        int end_pos = idx-1; // 끝 인덱스
        int cnt = 0; // R개수
        for (int i = 0; i < p.length();i++){ // 명령어 수행
            if(p[i] == 'R'){ // 뒤집기
                cnt++;
            }else{
                if(end_pos == -1){ // 원소 하나도 없는 경우
                    end_pos--;
                    cnt = 0;
                    break;
                }
                if(cnt%2 != 0){ // 뒤집기 실행
                    int tmp = start_pos;
                    start_pos = end_pos;
                    end_pos = tmp;
                }
                if(start_pos > end_pos)
                    start_pos -= 1;
                else if(start_pos < end_pos)
                    start_pos += 1;
                else 
                    end_pos = -1;
                cnt = 0; // R개수 초기화
            }
        }
        if(cnt != 0){ // 마지막에 남은 R명령 처리
            if(cnt%2 != 0 && end_pos > -1){ 
                int tmp = start_pos;
                start_pos = end_pos;
                end_pos = tmp;
            }            
        }
        
        if(end_pos == -1){
            cout << '[' << ']';
        }else if(end_pos == -2){
            cout << "error";
        }else if(start_pos >= end_pos){
            cout << '[';
            for (int i = start_pos; i > end_pos; i--){
                cout << num[i] << ',';
            }
            cout << num[end_pos] << ']';
        }else if(start_pos < end_pos){
            cout << '[';
            for (int i = start_pos; i < end_pos; i++){
                cout << num[i] << ',';
            }
            cout << num[end_pos] << ']';
        }
        cout << endl;
    }
    return 0;
}