https://www.acmicpc.net/problem/5430
문제 정리
배열이 주어짐.
명령어가 주어짐.
명령어는 문자열 형태로 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 |
'알고리즘 > 백준' 카테고리의 다른 글
백준 5525 IOIOI c++ [컴공과고씨] (0) | 2022.08.22 |
---|---|
백준 6064 카잉 달력 c++ [컴공과고씨] (0) | 2022.08.16 |
백준 14500 테트로미노 C++ [컴공과고씨] (0) | 2022.08.14 |
백준 13459 구슬 탈출 c++ [컴공과고씨] (0) | 2022.08.13 |
백준 2665 미로만들기 c++ [컴공과고씨] (2) | 2022.08.12 |