반응형
11-15 01:35
- Today
- Total
Link
개발하는 고라니
[백준] 5430번 : AC 본문
반응형
[Deque, 문자열]
문제는 상당히 직관적이고 길지 않아서 이해하는데 어려움은 없지만, 생각한 것을 구현을 할 수 있느냐에 관한 문제와 시간, 메모리의 효율 그리고 자료구조 덱(Deque)을 알고 있는가에 대한 문제가 있다.
아, 그리고 원소의 값으로 주어지는 것이 한 자릿수가 아님에 절대로 유의하자. 이 점을 간과하여 덱을 쓰지않고 문자열 객체로만 할 수 있을 줄 알았으나, 원소의 값은 1 이상 100 이하이다.
덱이란 간단히 말해, 큐(Queue)가 선입선출(First-in First-out, FIFO)이라면, 덱은 양방향에서 삽입 및 반출이 가능한 자료구조이다. 문제에서 주어진 함수 R, D가 있는데 R이 나올 때 마다 이를 뒤집는다면, 두세번 쯤이야 문제없지만, 최대 10만번의 함수가 존재할 수 있기에 뒤집는 것은 사용하지 않는 것이 좋다.
나는 뒤집힌 상태 또는 뒤집히지 않은 상태를 boolean 타입 변수에 저장했고, 그에 따라 삭제도 앞에서 혹은 뒤에서 진행했다.
# Code </>
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Deque;
import java.util.LinkedList;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int t = Integer.parseInt(br.readLine());
StringBuilder result = new StringBuilder();
for(int a=0; a<t; a++){
boolean error = false;
boolean reverse = false;
Deque<String> deque = new LinkedList<>();
/* cmd : R, D를 한줄에 받음 */
String cmd = br.readLine();
int n = Integer.parseInt(br.readLine());
/* arr: [1,2,3,59,5,...,100 */
String arr = br.readLine();
/* arr: 1,2,3,59,5,...,100 */
arr = arr.substring(1, arr.length() - 1);
StringTokenizer st = new StringTokenizer(arr, ",");
/* ','를 기준으로 숫자만 추출해 덱에 삽입 */
for(int i=0; i<n; i++) { deque.add(st.nextToken()); }
/* 덱의 메서드를 최대한 사용하지 않기 위해 원소의 개수 n을 직접 관리 (시간적 효율성) */
/* R, D 함수를 차례로 수행 */
for(char c:cmd.toCharArray()){
if(c == 'R') reverse = !reverse;
else{
/* error 인지 확인 */
if(n - 1 < 0) {
error = true;
break;
}
if(reverse) { //역방향
deque.pollLast();
n--;
}
else{ //정방향
deque.poll();
n--;
}
}
}
if (error)
result.append("error\n");
else{
result.append('[');
for(int i=0; i<n; i++)
result.append(reverse? deque.pollLast() : deque.poll()).append(i == n-1? "" : ',');
result.append(']').append('\n');
}
}
System.out.print(result);
}
}
반응형
'Programming > 백준' 카테고리의 다른 글
[백준] 18405번 : 경쟁적 전염 (0) | 2021.05.26 |
---|---|
[백준] 3709번 : 레이저빔은 어디로 (0) | 2021.05.13 |
[백준] 5884번 : 감시 카메라 (0) | 2021.05.11 |
[백준] 16441번 : 아기돼지와 늑대 (0) | 2021.05.10 |
[백준] 1034번 : 램프 (0) | 2021.05.10 |
Comments