[Java] 5430번. AC
1. 문제 분석
이 문제는 배열을 입력받고, 입력한 명령어를 실행한 후 결과 배열을 출력하는 문제이다.
이 때 명령어는 두가지 종류이다.
R : 배열을 뒤집는다.
D : 가장 앞의 요소를 버린다.
이 때, 배열에는 100,000만큼의 수가 들어갈 수 있고, 명령어(R, D)는 최대 100,000개 이다.
백준 문제를 풀면서 은근 '시간초과'를 많이 경험했기에
실제로 R명령어에서 모든 배열을 실제로 뒤집으면 시간초과가 날 것이다 라는 직감이 들었다.
어차피 삭제는 가장 앞에서만 되고,
뒤집으면 가장 뒤에 있던 요소가 가장 앞으로 오는 것이므로
R이 나오면 뒤를 삭제하는 것으로 바꾸도록 구현하였다.
이 때, 뒤를 삭제하고 있는데 R이 또 나오면 앞을 삭제해야 하므로
on/off 버튼처럼 앞/뒤를 표시할 수 있는 boolean 타입을 이용하였다.
이러한 방식으로 R이 나올 때마다 앞/뒤로 변경하고
D가 나오면 현재 포인터의 위치를 삭제하고 배열이 비어있는 경우 error를 발생시키면 된다.
❗ 중요 포인트 ❗
문제에서 자세한 설명이 없었지만 추가적으로 구현되어야 할 것이 있었다.
(이거 제대로 구현 안되면 계속 틀렸다고 뜸)
만약 주어진 예시를 잘 풀었는데도 틀렸다고 뜨면 아래 항목들을 체크해보자.
1. 빈 문자열은 출력하지 않는 것이 아니라 '[]'로 출력해야 한다.
2. 빈 배열을 R명령어로 뒤집는 것은 error가 아니다.
3. error가 한 번 발생하면 뒤의 모든 명령어는 생략된다.
즉, 빈 배열에 'DDD'를 하면 error가 세번 출력되는 것이 아니라 한번만 출력되어야 한다.
4. 최종 출력 배열에서 수 사이에 공백이 없다. [1, 2, 3, 4] 가 아니라 [1,2,3,4]이다.
2. 구현
테스트 케이스를 입력받고 테스트케이스 만큼 반복하는 과정과 각종 값들을 입력받는 과정은 생략하겠다.
사용할 주요 변수
direction : 현재 방향을 의미한다. true이면 정방향, false이면 역방향이다.
해결 과정
(1) 명령어가 R일 때
direction을 바꾼다.
(2) 명령어가 D일 때
배열이 비어있으면 error를 발생시킨다.
direction이 true(정방향)이면 가장 앞의 요소를 삭제한다.
direction이 false(역방향)이면 가장 뒤의 요소를 삭제한다.
(3) 모든 명령어를 실행하고 최종적으로 출력한다.
direction이 false이면 최종적으로 배열이 뒤집힌 상태여야 하기 때문에 뒤집어서 출력한다.
direction이 true이면 그냥 배열을 출력하면 된다.
위 방식대로 코드를 단순히 작성하면 아래와 같은 코드가 된다.
* 아래 코드는 잘못된 코드입니다.
for(int j=0; j<command.length(); j++){
switch (command.charAt(j)){
case 'R':
direction = !direction;
break;
case 'D':
if(deque.isEmpty()) {
bw.write("error\n");
break;
}
if(direction){
deque.pollFirst();
}
else{
deque.pollLast();
}
break;
}
}
위 코드를 빈 배열에서 'DDDD'를 실행하면 error라는 메세지가 4번 출력된다.
이를 위해서 한 번 error가 발생하면 뒤의 명령어들이 실행이 되지 않도록
switch문을 나간 후 for문도 나가서 다음 명령어를 실행하지 않아야 하는데
위의 구조상 이를 해결하기에는 어려웠다.
따라서 isError라는 error를 체크하는 boolean 타입의 변수를 이용해서
isError가 true이면 for문을 종료시키거나 반복해서 출력되지 않도록 해주어야 한다.
3. 최종코드
import java.io.*;
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;
class Main{
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringBuilder sb = new StringBuilder();
int testCase = Integer.parseInt(br.readLine());
for(int i=0; i<testCase; i++){
String command = br.readLine();
int size = Integer.parseInt(br.readLine());
boolean direction = true;
boolean isError = false;
String input = br.readLine();
input = input.substring(1, input.length()-1);
String[] tokens = input.split(",");
Deque<Integer> deque = new ArrayDeque<>();
for(int j=0; j<size; j++) {
deque.addLast(Integer.parseInt(tokens[j].trim()));
}
for(int j=0; j<command.length(); j++){
switch (command.charAt(j)){
case 'R':
direction = !direction;
break;
case 'D':
if(deque.isEmpty()) {
isError=true;
break;
}
if(direction){
deque.pollFirst();
}
else{
deque.pollLast();
}
break;
}
}
if(isError){
bw.write("error\n");
}
else{
sb.setLength(0);
sb.append("[");
if(direction){
while(!deque.isEmpty()){
sb.append(deque.pollFirst()).append(',');
}
}
else{
while(!deque.isEmpty()){
sb.append(deque.pollLast()).append(',');
}
}
if(sb.length()>1)
sb.setLength(sb.length()-1);
sb.append("]\n");
bw.write(sb.toString());
}
}
br.close();
bw.close();
}
}위의 최종 코드가 옳은 코드이기는 하나 살짝 복잡해 보이기는 한다.
또한 빈 배열에 DDDD명령어를 실행하면 출력이 되지는 않지만 실제로 뒤의 불필요한 D명령어를 실행하기는 한다.
그래서 isError가 true이면 for문 밖에 나가면서 바로 error 메시지를 출력하게 수정하였고,
isError가 아닐 때만 최종 배열을 출력하는 형식으로 작성했더니 코드가 조금 더 가독성이 좋아진 느낌이다.
하지만, 뒤의 불필요한 명령어를 실행하지 않기 때문에 성능이 좋아질 줄 알았지만
백준 제출 결과를 보면 오히려 성능이 저하했다고 볼 수 있었다.
(수정전) 시간 : 744ms / 메모리 : 94076KB
(수정후) 시간 : 772ms / 메모리 : 96732KB
import java.io.*;
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;
class Main{
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringBuilder sb = new StringBuilder();
int testCase = Integer.parseInt(br.readLine());
for(int i=0; i<testCase; i++){
String command = br.readLine();
int size = Integer.parseInt(br.readLine());
boolean direction = true;
boolean isError = false;
String input = br.readLine();
input = input.substring(1, input.length()-1);
String[] tokens = input.split(",");
Deque<Integer> deque = new ArrayDeque<>();
for(int j=0; j<size; j++) {
deque.addLast(Integer.parseInt(tokens[j].trim()));
}
for(int j=0; j<command.length(); j++){
switch (command.charAt(j)){
case 'R':
direction = !direction;
break;
case 'D':
if(deque.isEmpty()) {
isError=true;
break;
}
if(direction){
deque.pollFirst();
}
else{
deque.pollLast();
}
break;
}
if(isError){
bw.write("error\n");
break;
}
}
if(!isError){
sb.setLength(0);
sb.append("[");
if(direction){
while(!deque.isEmpty()){
sb.append(deque.pollFirst()).append(',');
}
}
else{
while(!deque.isEmpty()){
sb.append(deque.pollLast()).append(',');
}
}
if(sb.length()>1)
sb.setLength(sb.length()-1);
sb.append("]\n");
bw.write(sb.toString());
}
}
br.close();
bw.close();
}
}