1. 문제 설명
- 1~N까지 오름차순으로 스택에 하나씩 집어넣는다.
- 스택에 하나씩 들어올 때, 적절히 POP하여, 문제에서 원하는 수열을 만들 수 있는지 구하라
- 만들 수 있다면 PUSH = + , POP = - 로 그간 해왔던 명령어를 출력하고,
만들 수 없다면 NO를 출력하라
2. 문제 푸는 방법
A. 첫 번째 방법 (STACK 자료 구조 이용)
(1) 답이 되는 수열(이하 ans)과 스택에 입력하는 순서인 오름차순 수열(이하 arr)을 배열에 저장했다.
(2) 둘 다 지시자를 가지고 있다.
ans의 지시자를 ansIndicator, arr의 지시자를 arrIndicator라고 할 때,
a. arrIndicator가 가르키고 있는 것이 ansIndicator보다 작거나 같으면 stack에 arrIndicator가 가르키고 있는 것을 Push하고 arrIndicator를 하나 올린다.
b. Stack의 맨 꼭대기 값과 ansIndicator가 가르키고 있는 값이 같으면, Stack 꼭대기 값을 pop하고 ansIndicator를 하나 올린다.
c. 만약 Stack 꼭대기의 값이 ansIndicator보다 크면, Stack에서 아무리 POP해도 원하는 수열을 만들 수 없기 때문에, NO를 출력 한다.
B. 두 번쨰 방법 (배열을 스택처럼 이용)
[변수에 대한 설명]
a. top = Stack의 Peek를 가르키는 것을 배열에서 구현하기 위해 사용하는 변수로, 배열에서 제일 최근에 들어온 값을 지칭하는 변수이다.
b. index = 답이 될 수열의 특정 원소를 가르키고 있는 지시자이다.
[문제 푸는 방법]
(1) for문을 1 ~ N 까지 돈다.
(2) stack에 일단 하나 집어 넣는다.
(3) 다음 while 문 돌면서 stack의 top과 index가 가르키고 있는 ans의 원소가 같은지 확인한다.
(4) 만약 같다면, top-- (pop하고 그 밑에걸 가르키는 것을 의미), index++ (다음 원소를 가르키는 것을 의미) 한다.
(5) 1~n까지 다 돌고 나면, stack에 잔재해 있는 나머지 값들에 대해서 (4)를 한번 더한다.
(6) 근데 만약에 (5)를 했는데도 Stack에 잔재해 있는 값이 남아있다면, 답이 되는 수열을 못 만든다는 소리가 되므로, NO를 출력한다.
3. 코드 분석
A. 첫 번쨰 방법에 대한 풀이
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
/*
* 1874번 스택 수열
* */
public class Main {
static int N;
static int [] ans;
static int [] arr;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// 1. 입력 받기---------------------------------------------------------------
N = Integer.parseInt(br.readLine());
arr = new int [N];
ans = new int [N];
for (int i = 1; i <= N; i++) {
arr[i-1] = i;
ans[i-1] = Integer.parseInt(br.readLine());
}
StringBuilder sb = new StringBuilder();
Stack<Integer> stack = new Stack<>();
// 2. 배열과 답의 값을 비교해서, 배열 <= 답이면, 배열의 표시자를 하나씩 올리면서, [stack]에 집어넣는다.
// 3. stack.peek() == 답이면, stack 에서 pop 하고, 답의 표시자를 하나 올린다.
// 4. stack.peek() > 답이면 NO를 출력하고 프로그램을 종료한다.
int ansIndicator = 0;
int arrIndicator = 0;
while (ansIndicator < N) {
while (arrIndicator < N && arr[arrIndicator] <= ans[ansIndicator]){
sb.append("+\n");
stack.push(arr[arrIndicator]);
arrIndicator++;
}
while (!stack.isEmpty() && stack.peek() == ans[ansIndicator]){
stack.pop();
sb.append("-\n");
ansIndicator++;
}
if(!stack.isEmpty() && stack.peek() > ans[ansIndicator]){
System.out.println("NO");
return;
}
}
System.out.println(sb);
}
}
B. 두 번쨰 방법에 대한 풀이
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
/*
* 1874번 스택 수열
* */
public class Main {
static int [] ans;
public static void main(String[] args) throws IOException {
// 1. 값 입력 ---------------------------------------------------------
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
ans = new int [N];
for (int i = 0; i < N; i++) {
ans[i] = Integer.parseInt(br.readLine());
}
// [stack]을 배열로 구현
int [] stack = new int [N];
// top은 Stack의 지시자, stack 배열에 값이 찰수록 올림. -> 뺄 때마다 내림
int top = -1;
StringBuilder sb = new StringBuilder();
int index = 0;
// stack 에 값 넣으면서 바로바로
for (int i = 1; i <= N; i++) {
// 1) 같은 경우가 아니라면 stack에 오름차순으로 값을 push 한다.
stack[++top] = i;
sb.append("+\n");
// 2) stack에 값이 존재하고, stack의 탑이랑 뽑아야할 값이랑 같으면 POP한다.
while (top != -1 && stack[top] == ans[index]){
top--; // 지시자 한 단계 내리기 pop을 구현한 것
index++; // 지금 답은 이제 해결 했음으로 다음으로 넘어간다.
sb.append("-\n"); // 값 넣기
}
}
// 3) Stack이 empty가 아니고, stack의 peek이 답의 값과 같으면 pop
while (top != -1 && stack[top] == ans[index]){
top --;
index ++;
sb.append("-\n");
}
// 4) 3번에서 [stack]의 peek 과 현재 출력해야 하는 답 부분이 어긋나면 해당 문제는 풀 수 없는 문제 이므로
// stack 배열을 맨 아래까지 보지 않은 채, while loop를 나간다.
// 따라서 top이 맨 밑바닥인 -1까지 오지 않으면 NO를 출력한다.
System.out.println(top == -1? sb : "NO");
}
}
'알고리즘 > 문제 풀이' 카테고리의 다른 글
💜 백준 10250 ACM 호텔 (0) | 2024.04.23 |
---|---|
💜 백준 11729번 하노이 탑 이동순서 (0) | 2024.04.20 |
💜 백준 7490. 0 만들기 JAVA (0) | 2024.04.17 |
💜 백준 3109 뱀 JAVA (0) | 2024.04.15 |
💜 백준 2085 사탕게임 JAVA (0) | 2024.04.11 |