[Java] 백준(골드-5) 5430번 - AC
문제 풀이
이 문제는 자료구조 중 양쪽 연산이 가능한 Deque(덱)을 이용해 풀 수 있는 문제이다.
아이디어 도출
덱을 이용하는 이유는 바로 시간초과를 피하기 위함이다. 필자는 아무 생각 없이 문제 제약사항을 읽지 않고 배열을 뒤집는 R 함수의 과정에서 Collections.reverse() 메소드를 이용해 풀었더니 시간초과가 발생했다.
그런데 문제를 조금 만 더 자세히 살펴보면, 주어진 배열을 뒤집을 필요가 없다는 것을 알 수 있었다. 아래 예시를 살펴보자.
1
2
3
4
5
6
7
8
9
10
11
12
[1,2,3,4], front=1
1. R 함수 실행
[1,2,3,4] front=4
2. D 함수 실행
[1,2,3] front=3
2. D 함수 실행
[1,2] front=2
=> [2,1]
덱을 이용하면 위와 같이 배열을 뒤집는 과정을 구현할 필요없이 양쪽의 원소를 제거하는 메소드를 통해 뒤집는 것과 유사한 동작을 구현할 수 있다. 이를 통해 도출한 아이디어는 다음과 같다.
- Deque에 주어진 정수 배열을 담는다.
- 함수 문자열 p를 순회하며 R 함수시에는 스위치 변수를 변경해주고, 이 스위치 변수를 통해 D 함수를 수행한다.
- D 함수를 수행할 때, 빈 덱에서 원소를 제거하려고 하면
error문자열을 결과에 담는다. - 모든 D 함수를 수행했다면 스위치 변수를 통해 오름차순으로 담을지 내림차순으로 담을지를 결정하여 결과에 담으면 된다.
위 아이디어대로 구현하면 간단하게 풀 수 있다.
정답률 16%에서 멈추고 틀렸습니다가 나올 수 있다. 이 때 덱의 사이즈를 고려해서 양쪽 제거 연산을 수행해야 하므로 덱의 원소가 하나라도 있을 경우에만 양쪽 제거 연산을 수행하도록 구현하였다.
문제 풀이를 위해 작성한 코드는 아래와 같다.
작성코드
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
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
import java.io.*;
import java.util.*;
class Main {
// 전역으로 사용할 Deque 선언
static ArrayDeque<Integer> d;
// 각 테스트케이스별 결과를 담을 StringBuilder 선언
static StringBuilder sb;
public static void main(String[] args) throws IOException {
/**
* Deque을 활용해 R 함수를 구현하는 것이 핵심이다.
*/
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int T = Integer.parseInt(br.readLine());
for(int i=0; i<T; i++) {
// 주어진 배열 원소를 담아 연산을 수행할 Deque
d = new ArrayDeque<>();
// 결과를 담을 문자열
sb = new StringBuilder();
// 입력으로 주어지는 함수, 배열의 길이, 배열 원소
String p = br.readLine();
int length = Integer.parseInt(br.readLine());
String input_nums = br.readLine();
// 주어진 배열이 함수를 수행할 수 있는 원소가 있을 경우만 연산을 수행한다.
if(length>0) {
// 주어진 배열 파싱하여 Deque에 답는다.
input_nums = input_nums.substring(1, input_nums.length()-1);
String[] nums = input_nums.split(",");
for(int j=0; j<nums.length; j++) {
d.add(Integer.parseInt(nums[j]));
}
}
/**
* 함수 수행 - R, D
* R일 때 Collections.reverse() 메소드를 사용하면 시간초과가 발생한다.
* Deque의 특성을 이용해 양쪽으로 front를 변경해가며 연산을 수행하면 된다.
*/
AC(p, d);
// AC 함수 호출을 통해 쌓인 StringBuilder 출력.
bw.write(sb+"\n");
}
bw.close();
br.close();
}
/**
* R 함수시 스위치만 해준 후, Deque에 D 연산으로 양쪽 제거를 먼저 한다.
* D 연산이 모두 종료된 후 스위치변수와 Deque 원소를 통해 내림차순이나 오름차순 정렬을 해준다.
*/
static void AC(String p, ArrayDeque<Integer> d) {
String[] cmds = p.split("");
// R 함수를 수행하기 위해 양쪽으로 스위치하기 위한 변수
boolean reverse = false;
for(String cmd : cmds) {
// R 함수로 인해 뒤집어야 할 경우 스위치한다.
if(cmd.equals("R")) {
reverse = !reverse;
}
/**
* D 함수일 경우 빈 덱을 삭제하려고 할 경우 error를 담는다.
*
*/
else if(cmd.equals("D")) {
if(reverse) {
if(d.pollLast() == null) {
sb.append("error");
return;
}
} else {
if(d.pollFirst() == null) {
sb.append("error");
return;
}
}
}
}
/**
* D 연산 종료 후 배열 원소를 정렬하여 저장한다.
* reverse==true라면 마지막 수 저장후, 내핌차순(덱의 역방향) 정렬
* reverse==false라면 첫번째 수 저장후, 오름차순(덱의 정방향) 정렬
* 이떄, Duque의 원소가 1개 이상 있어야 한다.
*/
sb.append("[");
if(d.size() > 0) {
if(reverse) {
sb.append(d.pollLast());
while(!d.isEmpty()) {
sb.append("," + d.pollLast());
}
}
else {
sb.append(d.pollFirst());
while(!d.isEmpty()) {
sb.append("," + d.pollFirst());
}
}
}
sb.append("]");
}
}
출처
- 해당 문제의 저작권은 문제를 만든이에게 있으며 자세한 내용은 문제 링크에서 참조바랍니다.