백준
[JAVA] 백준 5430번: AC
스파게티 코더
2024. 9. 1. 20:47
문제
- R 연산은 배열을 뒤집는 연산, D 연산은 배열의 첫 번째 수를 버리는 연산이다.
- 숫자가 담긴 배열이 문자열 형태로 주어지고 수행해야 하는 연산이 문자열로 주어질 때, 연산을 수행한 결과를 출력하는 문제.
아이디어
- 배열이 "[1,2,3]"과 같이 문자열로 주어지기에 문자열 파싱을 잘해야 숫자를 뽑아내고 배열에 저장할 수 있다.
- Java의 substring 메서드로 문자열의 앞, 뒤에 붙어있는 '[', ']' 문자를 제거한 후, split 메서드를 통해 ','를 기준으로 숫자를 뽑아낸다.
- 문자열을 뒤집는 연산의 경우 직접 배열을 뒤집는 reverse 메서드를 떠올릴 수 있겠지만, 배열의 길이가 길어질수록 시간초과가 발생할 확률이 상당히 높다.
- 이에 배열이 뒤집힌 상태인지 아닌지 체크하는 boolean 타입의 isReversed 변수를 두고, 'R' 연산이 주어질 때마다 isReversed 플래그 값을 뒤집는다.
- 그리고 'D' 연산을 처리하는 방식에 따라 두 가지 풀이로 나뉜다.
- (첫 번째 풀이) Deque을 사용한다.
- 'D' 연산이 주어지고 덱이 비어있으면 error를 출력 후 종료, 비어있지 않다면 아래 동작을 수행한다.
- isReversed 플래그가 true면 덱에서 removeLast 즉, 뒤에서 숫자를 제거하고,
- false 이면 덱에서 원래대로 removeFirst 즉, 앞에서 숫자를 제거한다.
- 이후, isReversed 플래그 값을 기준으로 앞/뒤 에서부터 숫자를 출력한다.
- 'D' 연산이 주어지고 덱이 비어있으면 error를 출력 후 종료, 비어있지 않다면 아래 동작을 수행한다.
- (두 번째 풀이) 배열과 포인터 두 개를 사용한다.
- 배열의 인덱스를 가리키는 start, end 변수를 두고, 숫자를 제거할 때마다 가운데로 한 칸씩 이동시킨다.
- 'D' 연산이 주어지고 start와 end가 같은 인덱스를 가리킬 경우 배열이 빈 상태이므로 error를 출력 후 종료하고, 그렇지 않으면 아래 동작을 수행한다.
- isReversed 플래그가 true면 end-- 즉, 뒤를 가리키는 인덱스를 앞으로 당기고,
- flase 이면 원래대로 start++ 즉, 앞을 가리키는 인덱스를 뒤로 민다.
- 이후, 첫 번째 풀이와 똑같이 isReversed 플래그 값을 기준으로 출력한다.
- 가장 나를 괴롭혔던 테스트케이스는 n이 0으로 들어오는 경우, 즉 빈 배열이 들어올 때였다.
- 이에 그냥 n이 0으로 들어오면 위 연산을 무시하고 에러를 발생시키는지 아닌지만 파악해서 출력한다.
첫 번째 풀이 (ArrayDeque 사용)
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
int T = Integer.parseInt(br.readLine());
for(int t=0; t<T; t++) {
// 배열 연산 처리를 위한 덱 선언
Deque<Integer> deque = new ArrayDeque<>();
String command = br.readLine();
int n = Integer.parseInt(br.readLine());
String numbers = br.readLine();
// 만약 들어오는 숫자가 1개 이상일 때
if (n > 0) {
// 문자열을 파싱해서 숫자(문자 타입)를 문자열 배열에 저장
String[] numArr = numbers.substring(1, numbers.length() - 1).split(",");
// 이후 문자열로 구성된 숫자를 정수 타입으로 덱에 저장
for (String num : numArr) {
deque.addLast(Integer.parseInt(num));
}
}
// 역방향인지 체크하기 위한 변수 선언
boolean isReversed = false;
// 에러 발생 유무 파악을 위한 변수 선언
boolean flag = false;
// 명령어 실행
for(char c: command.toCharArray()) {
// 뒤집는 연산일 경우, isReversed 반전
if(c == 'R') {
isReversed = !isReversed;
}
else {
// 덱이 비었는데 숫자를 제거하는 경우 에러 발생
if(deque.isEmpty()) {
flag = true;
break;
}
// 역방향 상태면 뒤에서 제거
if(isReversed) {
deque.removeLast();
}
// 정방향 상태면 앞에서 제거
else {
deque.removeFirst();
}
}
}
// 연산 수행 중 에러가 발생했으면 error 출력 후 종료
if(flag) {
sb.append("error").append('\n');
}
else {
sb.append('[');
int count = 0;
// 덱이 빌 때까지 숫자를 StringBuilder에 저장
while(!deque.isEmpty()) {
// ','를 답안 예시와 같이 출력하기 위해 맨 마지막 숫자에는 붙이지 않음
if(count != 0) {
sb.append(',');
}
// 역방향 상태면 뒤에서부터 저장
if(isReversed) {
sb.append(deque.removeLast());
}
// 정방향 상태면 앞에서부터 저장
else {
sb.append(deque.removeFirst());
}
count++;
}
sb.append(']').append('\n');
}
}
System.out.println(sb);
}
}두 번째 풀이 (배열 사용)
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
int T = Integer.parseInt(br.readLine());
for(int t=0; t<T; t++) {
String command = br.readLine();
int n = Integer.parseInt(br.readLine());
String numbers = br.readLine();
// 숫자 제거시 체크하기 위한 인덱스 포인터 두 개 선언
int start = 0;
int end = n;
boolean isReversed = false;
boolean flag = false;
if (n > 0) {
// 문자열 파싱 후 문자열 배열에 숫자 저장
String[] numArr = numbers.substring(1, numbers.length() - 1).split(",");
// 연산 수행
for(int i=0; i<command.length(); i++) {
if(command.charAt(i) == 'R') {
isReversed = !isReversed;
}
else {
// 배열에 숫자가 비었을 때 에러 발생
if(start == end){
flag = true;
break;
}
// 역방향이면 뒤 인덱스 앞으로 당기기
if(isReversed) {
end--;
}
// 정방향이면 앞 인덱스 뒤로 밀기
else {
start++;
}
}
}
// 중간에 에러가 발생했으면 에러 출력
if(flag) {
sb.append("error").append('\n');
}
else {
sb.append('[');
// 역방향이면 뒤에서부터 숫자 저장
if(isReversed) {
for(int i=end-1; i>=start; i--) {
sb.append(numArr[i]);
if(i != start) {
sb.append(',');
}
}
}
// 정방향이면 앞에서부터 숫자 저장
else {
for(int i=start; i<end; i++) {
sb.append(numArr[i]);
if(i != end-1) {
sb.append(',');
}
}
}
sb.append(']').append('\n');
}
}
// n이 0일경우, D 연산으로 에러가 발생하는지 아닌지만 파악 후 종료
else {
if (command.contains("D")) {
sb.append("error\n");
} else {
sb.append("[]\n");
}
}
}
System.out.println(sb);
}
}
채점 결과
기타
- 확실히 덱을 쓰는 것 보다 배열과 포인터 두 개 만으로 푼 풀이가 메모리 사용량도 적고, 시간도 적게 걸렸다.
- 예외 테스트케이스가 많아 여러번 틀리고 고생했다...