안녕하세요
인포돈 입니다.
백준 알고리즘 5430번 풀이입니다.
* 참고사항
- 개발환경은 eclipse을 기준으로 작성되었습니다.
- java언어를 이용하여 문제를 풀이합니다.
- 알고리즘 문제는 풀이를 보고 해답을 찾는 것도 중요하지만 무엇보다 스스로 풀이를 시도해봐야 합니다!!
(해당 풀이를 보기 전 충분히 문제에 대해 고민해봐야 합니다!)
- 해당 풀이 말고도 수많은 풀이 방법이 존재합니다.
백준 5430 (AC)
문제
선영이는 주말에 할 일이 없어서 새로운 언어 AC를 만들었다. AC는 정수 배열에 연산을 하기 위해 만든 언어이다. 이 언어에는 두 가지 함수 R(뒤집기)과 D(버리기)가 있다.
함수 R은 배열에 있는 숫자의 순서를 뒤집는 함수이고, D는 첫 번째 숫자를 버리는 함수이다. 배열이 비어있는데 D를 사용한 경우에는 에러가 발생한다.
함수는 조합해서 한 번에 사용할 수 있다. 예를 들어, "AB"는 A를 수행한 다음에 바로 이어서 B를 수행하는 함수이다. 예를 들어, "RDD"는 배열을 뒤집은 다음 처음 두 숫자를 버리는 함수이다.
배열의 초기값과 수행할 함수가 주어졌을 때, 최종 결과를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 테스트 케이스의 개수 T가 주어진다. T는 최대 100이다.
각 테스트 케이스의 첫째 줄에는 수행할 함수 p가 주어진다. p의 길이는 1보다 크거나 같고, 100,000보다 작거나 같다.
다음 줄에는 배열에 들어있는 수의 개수 n이 주어진다. (0 ≤ n ≤ 100,000)
다음 줄에는 [x1,..., xn]과 같은 형태로 배열에 들어있는 수가 주어진다. (1 ≤ xi ≤ 100)
전체 테스트 케이스에 주어지는 p의 길이의 합과 n의 합은 70만을 넘지 않는다.
출력
각 테스트 케이스에 대해서, 입력으로 주어진 정수 배열에 함수를 수행한 결과를 출력한다. 만약, 에러가 발생한 경우에는 error를 출력한다.
입력 예제
4
RDD
4
[1,2,3,4]
DD
1
[42]
RRD
6
[1,1,2,3,5,8]
D
0
[]출력 예제
[2,1]
error
[1,2,3,5,8]
error성공 코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Deque;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.StringTokenizer;
public class Main {
static int T;
static StringBuilder sb = new StringBuilder();
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
T = Integer.parseInt(br.readLine());
loop: for(int i = 0 ; i < T ; i++) {
//boolean check_err = false;
boolean re = true;
int N;
LinkedList<Integer> q = new LinkedList<>();
char[] function;
function = br.readLine().toCharArray();
N = Integer.parseInt(br.readLine());
StringTokenizer st = new StringTokenizer(br.readLine(),"[],");
while(st.hasMoreTokens())
q.add(Integer.parseInt(st.nextToken()));
for(char ch : function) {
if(ch == 'R') {
re = !re;
continue;
}
if(q.isEmpty()) {
//check_err = true;
sb.append("error").append("\n");
continue loop;
} else {
if(re == true)
q.pollFirst();
else
q.pollLast();
}
}
/*if(check_err == true) {
sb.append("error").append("\n");
}else*/ if(re == true && !q.isEmpty()) {
sb.append("[" + q.pollFirst());
while(!q.isEmpty()) {
sb.append("," + q.pollFirst());
}
sb.append("]").append("\n");
}else if(re==false && !q.isEmpty()){
sb.append("[" + q.pollLast());
while(!q.isEmpty()) {
sb.append("," + q.pollLast());
}
sb.append("]").append("\n");
}else {
sb.append("[]").append("\n");
}
}
System.out.println(sb);
}
}사실 해당 알고리즘은 어느 정도 생각을 하면서 풀었는데.... 뒤쪽에 있는 append뒤에 \n 개행 문자를 안 써줘서 2시간을 헤매버렸습니다... ㅜㅜ 사실 알고리즘은 나름 고민만 잘하시면 크게 어려울 것이 없습니다. STEP을 따라가며 이해 보도록 하죠
알고리즘 흐름도
입력 받기 -> R, D규칙 적용하기 -> 출력하기
STEP1 문제 이해하기
문제의 이해는 굉장히 쉽습니다. 아래 규칙을 따라가면 됩니다.
R이 나오면 문자를 뒤집는다.
D가 나오면 문자를 버린다.
아무것도 없을 때 D가 나오면 error를 출력한다.
아무것도 없을 때 R이나 오면 그냥 그대로 출력한다.
이 4가지만 고려해주면 끝!
STEP2 R규칙 해결하기
앞선 R규칙은 2가지만 고려해 주면 됩니다.
우선 R이 나오면 문자를 뒤집는다.
이 규칙은 잘 생각해야 합니다. 큐를 사용하면서 하나하나 뒤로 보내주는 것이 아니라 바로 인덱스 변수를 활용해서 빼내어야 할 위치를 표현해주면 됩니다.
말로만 하면 이해가 어려우니 바로 알려드리겠습니다.
loop: for(int i = 0 ; i < T ; i++) {
boolean re = true;
int N;
LinkedList<Integer> q = new LinkedList<>();
char[] function;
function = br.readLine().toCharArray();
N = Integer.parseInt(br.readLine());
StringTokenizer st = new StringTokenizer(br.readLine(),"[],");
while(st.hasMoreTokens())
q.add(Integer.parseInt(st.nextToken()));
for(char ch : function) {
if(ch == 'R') {
re = !re;
continue;
}
if(q.isEmpty()) {
//D 규칙 적용
} else {
if(re == true)
q.pollFirst();
else
q.pollLast();
}
}
}길어 보이는데 사실 큰 규칙은 없습니다. 앞서 선언한 것은 전부 변수들입니다. 앞서 말한 거꾸로를 체크해 주는 변수가 바로 boolean re 이 값이 true라면 앞에서부터 false라면 뒤에서부터 하라는 뜻!
일단은 다른 변수는 입력을 받기 위한 변수들이죠. 입력받는 거야 뭐.... 쉬우니 그냥 넘어가겠습니다.
간단히 설명만 하자면
q : 숫자를 담을 큐
function : RD와 같은 함수를 저장하기 위한 배열
N : 몇 개의 숫자를 담을 것인지 나타내는 변수
st : 입력을 [ ] , 3가지 토큰으로 나누어주기 위한 변수
입니다.
간다히 function이라는 배열에 R이 담겨있으면 re변수를 부정해 줍니다. 그 뒤에는 이제 D라는 함수가 나올 경우를 체크해 줘야 합니다. 그 뒤는 D규칙을 이해하면서 같이 이해 보도록 하죠.
STEP 3D 규칙 해결하기
loop: for(int i = 0 ; i < T ; i++) {
boolean re = true;
int N;
LinkedList<Integer> q = new LinkedList<>();
char[] function;
function = br.readLine().toCharArray();
N = Integer.parseInt(br.readLine());
StringTokenizer st = new StringTokenizer(br.readLine(),"[],");
while(st.hasMoreTokens())
q.add(Integer.parseInt(st.nextToken()));
for(char ch : function) {
if(ch == 'R') {
re = !re;
continue;
}
if(q.isEmpty()) {
sb.append("error").append("\n");
continue loop;
} else {
if(re == true)
q.pollFirst();
else
q.pollLast();
}
}
}앞선 코드에서 if(q.isEmpty())의 로직만 추가해 준 상황입니다. 앞서 if문에서 R이라는 함수에 거리지 않았다면 D라는 함수가 왔었겠죠?
그렇다면 여기에서는 D의 함수가 들어왔을 경우를 해결해 줘야 합니다.
D가 나오면 문자를 버린다.
아무것도 없을 때 D가 나오면 error를 출력한다.
우선 만약에 q가 비어있다면 error를 출력해야겠죠. 그다음 다시 반복문을 속행해 줍니다. 여기서 continue loop는 ch의 다음을 따라가는 게 아닙니다.
바로 이 상위에 있는 loop: for(int i = 0 ; i < T ; i++) 이 루프 문으로 돌아가는 것이죠. 즉, 이번 function에서는 더 이상 수행하지 말고 error를 넣고 끝내라는 의미
만약 아니라면 re를 한 번 더 확인합니다. 왜냐하면 뒤에서 버릴지 앞에서 버릴지 알기 위해서죠. 이에 따라서 덱 큐에서 pollFirst, pollLast를 활용해 버려 주면 끝~
STEP 4 출력하기
사실 이번 알고리즘에서 가장 헤맸던 출력하기입니다...... 별것도 아니지만 은근히 헷갈리는 부분이 많았죠.
if(re == true && !q.isEmpty()) {
sb.append("[" + q.pollFirst());
while(!q.isEmpty()) {
sb.append("," + q.pollFirst());
}
sb.append("]").append("\n");
}else if(re==false && !q.isEmpty()){
sb.append("[" + q.pollLast());
while(!q.isEmpty()) {
sb.append("," + q.pollLast());
}
sb.append("]").append("\n");
}else {
sb.append("[]").append("\n");
}앞선 문제들을 모두 포함해 줍니다.
re가 true라면 앞에서 해야 하죠. 단 q가 비어있지 않아야 합니다.
그럴 경우 [ 을 출력해 주고 q에서 하나를 끝낸 뒤 나머지 값들을 , 과함께 출력하고 마지막에 ]를 출력합니다.
그 반대의 경우라면 반대로 해주면 끝이겠죠?
만약에 아니라면 그냥 비어있는 []를 출력해주면 끝~
'알고리즘 > 백준알고리즘' 카테고리의 다른 글
| [백준알고리즘-JAVA]10773번 풀이(제로) - 초보도 이해하는 풀이 (0) | 2021.09.17 |
|---|---|
| [백준알고리즘-JAVA]10828번 풀이(스택) - 초보도 이해하는 풀이 (0) | 2021.09.16 |
| [백준알고리즘-JAVA]1021번 풀이(회전하는 큐) - 초보도 이해하는 풀이 (0) | 2021.09.14 |
| [백준알고리즘-JAVA]1966번 풀이(프린터 큐) - 초보도 이해하는 풀이 (0) | 2021.09.13 |
| [백준알고리즘-JAVA]11866번 풀이(요세푸스 문제) - 초보도 이해하는 풀이 (0) | 2021.09.12 |
