이 문제에 대한 설명이 너무 부족하다.
이 문제만 보고 완벽하게 이해하고 넘어간다는게 정말 힘든 것 같다.
예제 입력 1부터 설명하겠다.
첫번째 줄 8은 숫자를 총 8개를 입력한다는 뜻이고,
4를 입력 -> 1 2 3 4를 push (4번 / +는 4개 저장)
그리고 맨 마지막 4를 pop (1번 / -는 1개 저장)
그럼 내 스택에는 1, 2, 3이 저장되어있고
다음에 입력할 숫자는 3이기 때문에 peek했을 때 3이면 pop하고 끝 (1번 / -는 1개 저장)
그다음 입력하는 숫자는 6, 근데 우리가 지금까지 입력한 숫자 중 최댓값은 4다 ( 맨 처음에 입력한 숫자는 4였다 )
따라서 최댓값보다 큰 5, 6만 push (2번 / +는 2개 저장)
그리고 맨 마지막 6을 pop (1번 / -는 1개 저장) => 다시 최댓값은 6임
그리고 8을 입력 최댓값은 6이기 때문에
7, 8만 push (2번 / +는 2개 저장)
그리고 맨 마지막 8을 pop (1번 / -는 1개 저장) => 최댓값은 8
지금까지 현황을 보면 , 1 2 3 4 저장 후 4 제거
=> 1 2 3 (최댓값 4)
3 입력 ( peek()을 했는데, 같으니까 pop)
=> 1 2
6 입력, 6은 제거
=> 1 2 5 (최댓값 6)
8 입력, 8은 제거
=> 1 2 5 7 (최댓값 8)
그리고 이어지는 7 5 2 1이 입력되기 때문에 pop 4번 , -4개 저장
따라서, + + + + - - + + - + + - - - - - 이렇게 결과를 나타낼 수 있다.
스택이 비어있기 때문에 +, -에 대한 결과를 출력해주면 되고스택이 비어있지 않으면 NO를 출력하면 된다
애초에 이 문제 설명이 너무 부실하기 때문에 이해 못하는사람이 훨씬 많을 것이다.
이 설명을 보면 쉽게 풀 수 있다.
똑같이 예제 입력2는 스택에 3이 남기 때문에 NO를 출력하면 되는 것임.
간단하게 입력 2에 대한 예시를 쓰겠다.
1입력, 그리고 pop
+ -,
2입력, 그리고 pop
+ -,
5입력, 3 4 5 그리고 5는 pop
+ + + -
3입력 근데 최댓값은 5이기 때문에 입력 x
4입력, peek했을 때 입력 값이랑 같기 때문에 pop
-
스택에는 3이 남아있기 때문에 NO를 출력하면 됨.
= 내가 접근한 방법 =
난 총 4개 메서드를 만들어서 활용했다.
일단 내 최종 코드다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;
public class Main {
public static Stack<Integer> stack = new Stack<>();
public static StringBuilder sb = new StringBuilder();
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// 1. input
int n = Integer.parseInt(br.readLine());
int max = 0;
for (int i = 0; i < n; i++) {
int num = Integer.parseInt(br.readLine());
checkEmpty(num, max);
max = Math.max(max, num);
}
int size = stack.size();
if (size == 0) {
System.out.println(sb);
} else {
System.out.println("NO");
}
}
public static void checkEmpty(int num, int max) {
if (!stack.empty()) {
// 스택이 비어있지 않을 때,
// 1. peek 값이랑 num 값을 비교하고 같으면 pop
if (stack.peek() == num) {
deleteNumber();
} else {
// 2. max 보다 큰 num 만 저장한다.
checkMaxNumberAndAddNumber(num, max);
}
} else {
// 스택이 비어있을 때, 그냥 push
addNumber(num, max);
}
}
public static void addNumber(int num, int max) {
for (int i = max + 1; i <= num; i++) {
stack.push(i);
sb.append("+").append("\n");
}
stack.pop();
sb.append("-").append("\n");
}
public static void checkMaxNumberAndAddNumber(int num, int max) {
if (num > max) {
for (int i = max + 1; i <= num; i++) {
stack.push(i);
sb.append("+").append("\n");
}
stack.pop();
sb.append("-").append("\n");
}
}
public static void deleteNumber() {
stack.pop();
sb.append("-").append("\n");
}
}
= 설명 =
먼저 static을 이용해서 Stack, StrinBuilder을 생성했다.
public static Stack<Integer> stack = new Stack<>();
public static StringBuilder sb = new StringBuilder();
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// 1. input
int n = Integer.parseInt(br.readLine());
int max = 0;
for (int i = 0; i < n; i++) {
int num = Integer.parseInt(br.readLine());
checkEmpty(num, max);
max = Math.max(max, num);
}그 후, 8이라는 숫자를 입력 받고 반복문 시작
예제 입력 1처럼
1. 4라는 숫자를 입력했다고 생각해보자.
그럼 맨 처음 입력에는 최댓값이 0이고, checkEmpty라는 메서드를 한 번 진행 후 최댓값을 4로 갱신해준다.
checkEmpty 메서드를 보자
public static void checkEmpty(int num, int max) {
if (!stack.empty()) {
// 스택이 비어있지 않을 때,
// 1. peek 값이랑 num 값을 비교하고 같으면 pop
if (stack.peek() == num) {
deleteNumber();
} else {
// 2. max 보다 큰 num 만 저장한다.
checkMaxNumberAndAddNumber(num, max);
}
} else {
// 스택이 비어있을 때, 그냥 push
addNumber(num, max);
}
}처음 4를 입력했기 때문에, else문을 타서 addNumber 메서드로 이동한다.
public static void addNumber(int num, int max) {
for (int i = max + 1; i <= num; i++) {
stack.push(i);
sb.append("+").append("\n");
}
stack.pop();
sb.append("-").append("\n");
}addNumber 메서드는 max를 기준으로 내가 입력한 num까지 push를 한 후, 마지막을 pop하는 과정이다.
이 과정을 통해 내 Stack에는 1, 2, 3이 저장되어있다.
2. 3을 입력
max의 값은 4이기 때문에 아무런 처리가 안 되지만 checkEmpty를 살펴보면
public static void checkEmpty(int num, int max) {
if (!stack.empty()) {
// 스택이 비어있지 않을 때,
// 1. peek 값이랑 num 값을 비교하고 같으면 pop
if (stack.peek() == num) {
deleteNumber();
} else {
// 2. max 보다 큰 num 만 저장한다.
checkMaxNumberAndAddNumber(num, max);
}
} else {
// 스택이 비어있을 때, 그냥 push
addNumber(num, max);
}
}스택이 비어있지 않을 때, peek 값과 num값이 같기 때문에 deleteNumber 메서드로 이동한다.
pop만 하고 끝.
public static void deleteNumber() {
stack.pop();
sb.append("-").append("\n");
}
3. 6을 입력
checkEmpty에서 스택이 비어있지 않기 때문에, checkMaxNumberAndAddNumber 메서드로 이동.
public static void checkMaxNumberAndAddNumber(int num, int max) {
if (num > max) {
for (int i = max + 1; i <= num; i++) {
stack.push(i);
sb.append("+").append("\n");
}
stack.pop();
sb.append("-").append("\n");
}
}내가 입력한 숫자가 최댓값보다 크면 이 반복문을 수행하고, pop까지 진행하는데
최댓값이 더 크면 아무런 처리를 하지 않는다.
지금 포스팅하면서 생각한건데, 이 메서드에서 확인하지 말고
처음부터 이 조건을 만족하는지 확인한 후,
만족 => checkMaxNumberAndAddNumber 메서드 수행
만족x => 아무것도 수행 x
이 형태로 바꾸는게 더 깔끔했을 것 같다.
이러한 접근을 통해서 해결했다.
문제가 더 자세하게 나와있었으면 정답률이 이렇게 낮진 않았을 문제같다.
