알고리즘/백준

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

시간빌게이츠 2022. 8. 14. 19:09
반응형

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

 

5430번: AC

각 테스트 케이스에 대해서, 입력으로 주어진 정수 배열에 함수를 수행한 결과를 출력한다. 만약, 에러가 발생한 경우에는 error를 출력한다.

www.acmicpc.net

 

문제 정리

배열이 주어짐.

명령어가 주어짐.

명령어는 문자열 형태로 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의 개수를 세어서 뒤집기라면 뒤에서 빼주고 뒤집지 않으면 앞에서 빼주면 됩니다.

 

전체코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
#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;
}
cs

 

반응형