💁♀️ 스택 이용!
N의 최대크기가 1,000,000이므로 반복문으로 오큰수를 찾으면 제한 시간을 초과한다.
스택에 다음 아이디어를 추가해 이 문제를 풀어보자
이 문제는 아이디어를 알고나서도 잘 이해가 안됐던 문제이다.
핵심 아이디어
- 스택에 새로 들어오려는 수가 현재 스택의 top에 존재하는 수보다 크면 그 수는 오큰수가 된다.(스택에는 값이 아닌 인덱스를 넣기!)
- 오큰수를 구한 후 수열에서 오큰수가 존재하지 않는 숫자에 -1을 출력해야한다. (스택에 남아있는 수)
문제 푸는 순서
- 스택이 채워져있고, A[index] > A[top]인 경우 pop한 인덱스를 이용하여 정답 수열에 오큰수를 저장한다. pop은 조건이 만족하는 동안 계속 반복한다.
- 현재 인덱스를 스택에 push하고, 다음 인덱스로 넘어간다.
- 과정 1~2를 수열 길이만큼 반복한 후 현재 스택에 남아있는 인덱스에는 -1을 저장한다.
예시 2로 살펴보자.
스택에 비어있으니 인덱스 0을 push하고 다음 인덱스 1로 넘어간다. (top = 0 , index = 1 / stack = 0)
이제 스택이 채워졌으니 과정 1을 한다.
A[index] < A[top] 이라서, 현재 인덱스를 또 스택에 push 하고 다음 인덱스로 넘어간다. (top = 1, index = 2 / stack = 1 0)
A[index] < A[top] 이라서, 현재 인덱스를 또 스택에 push 하고 다음 인덱스로 넘어간다. (top = 2, index = 3 / stack = 2 1 0)
A[index] > A[top]으로 과정1의 조건을 만족하기때문에, A[top == 2]에 해당하는 오큰수를 A[index == 3]값으로 저장한 후 A[top]은 pop한다.(top = 1, index = 3 / stack = 1 0)
또 조건을 만족하므로 한 번 더 수행한다. A[top ==1]의 오큰수는 A[index == 3]의 값이 된다.
(top = 0, index = 3 / stack = 0)
A[index] < A[top]이므로 현재 인덱스를 스택에 push한다.
(top = 1 / stack =1 0)
다음 인덱스는 없으므로 (배열끝까지 완료), 현재 스택에 남아있는 인덱스인 A[1], A[0]의 오큰수는 존재하지않는 -1로 저장한다.
Troubleshooting
class makeOne {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
StringTokenizer st = new StringTokenizer(br.readLine());
Stack<Integer> stack = new Stack<Integer>();
int[] A = new int[N+1];
int[] answer = new int[N+1];
for(int i =1; i<= N ;i++) {
A[i] = Integer.parseInt(st.nextToken());
}
int index = 2;
stack.add(1);
while(index <= N) {
if(A[index] > A[stack.peek()] && !stack.isEmpty()) { // trouble!!
answer[stack.pop()] = A[index];
} else if(stack.isEmpty() || (A[index] <= A[stack.peek()])) {
stack.push(index++);
}
}
while(!stack.isEmpty()) {
answer[stack.pop()] = -1;
}
for(int i=1; i<=N; i++) {
System.out.print(answer[i] + " ");
}
}
}문제
조건문의 조건이 문제였다.
나는 스택이 비어을때 예외처리도 처음에 하지못했고, 에러로 발견해서 예외처리를 진행했다.
그런데 조건문의 순서도 중요한것이었다!!!
원인
if(A[index] > A[stack.peek()] && !stack.isEmpty()) 이렇게 쓰면, 스택이 비어있을때에도 peek()작업을 수행해서 에러가 발생한다.
조건문에서도 실행 순서가 중요하다!
가장 첫번째 연산 먼저 수행한다!
해결
if(!stack.isEmpty() && A[index] > A[stack.peek()]) 수정
Troubleshooting 2
위 코드에서 해당 조건문만 수정했다.
문제
시간초과를 받았다
단순 반복문만 사용하면 이중반복문으로 시간초과가 될 수 있어서 스택을 이용해 개선했는데, 또 어디가 문제였을까?
원인
System.out.println()이 은근 시간초과의 원인인것같다.
알아보니 얼마나 차이가날까 싶겠지만 꽤 차이가 나는걸로 보인다..
특히 N의 최대가 1,000,000으로 아주 큰수이니..!
해결
출력시 System.out.println()대신 BufferedWriter을 사용해서 출력하도록 수정했다.
앞으로 코테에서는 무조건 BufferedWriter를 사용합시다!!!
제출코드
import java.io.*;
import java.util.*;
class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
StringTokenizer st = new StringTokenizer(br.readLine());
Stack<Integer> stack = new Stack<Integer>();
int[] A = new int[N+1];
int[] answer = new int[N+1];
for(int i =1; i<= N ;i++) {
A[i] = Integer.parseInt(st.nextToken());
}
int index = 2;
stack.add(1);
while(index <= N) {
if(!stack.isEmpty() && A[index] > A[stack.peek()]) {
answer[stack.pop()] = A[index];
} else if(stack.isEmpty() || (A[index] <= A[stack.peek()])) {
stack.push(index++);
}
}
while(!stack.isEmpty()) {
answer[stack.pop()] = -1;
}
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
for(int i=1; i<=N; i++) {
bw.write(answer[i] + " ");
}
bw.flush();
}
}