문제 정보
플랫폼 : 백준
분류 : Stack (스택)
난이도 : 골드 4
링크 : https://www.acmicpc.net/problem/9184
시간제한 및 메모리 제한 검증
O(n) 풀이
자료형 : 최대 1백만, int
풀이
스택을 두개 사용한다. 한 개는 정답 스택이고, 한 개는 임시 스택이다.
정답 스택은 말 그대로 정답을 담은 스택이고,
임시 스택은 오른쪽부터 수를 차곡차곡 쌓은 스택이다.
진행은 왼쪽에서부터 검사하는 것이 아니라, 오른쪽부터 검사한다.
-
임시 스택이 존재하면서, 현재 값이 임시 스택의 top보다 크거나 같은동안 임시 스택을 pop한다.
오른쪽 수 (임시 스택의 top)는 왼쪽 수보다 커야하기 때문이다. -
만약 임시 스택이 비어있으면 정답 스택에 -1을 쌓는다.
오른쪽에 자신보다 큰 수가 없음을 의미한다.2-2. 만약 임시 스택의 값이 있으면, 임시 스택의 top 값을 정답 스택에 push한다.
자신보다 큰 가장 가까운 오른쪽 수를 정답 스택에 추가함을 의미한다.
이 때 주의해야할 점은, 임시 스택을 pop 하지 않고 peek으로 얻은 값을 push하는 것이다. -
현재 값을 임시 스택에 쌓는다.
글로만 보면 이해가 쉽지 않으므로 그림과 함께 설명한다.
예제 입력 1의 값인
4
3 5 2 7을 통해 설명하겠다.
1번에서 임시 스택이 없으므로 Pass
2번에서 임시 스택이 비어있으므로 정답 스택에 -1을 추가한다.
3번에서 현재값을 임시 스택에 추가한다.
이후에 현재값은 2가된다.
1번에서 임시 스택에 값이 있으면서, 2 >= 임시스택의 pop인 동안 임시 스택을 pop한다.
2-2번에서 임시 스택에 값이 있으므로 임시 스택의 top을 정답 스택에 push한다.
4번에서 현재값을 임시 스택에 넣는다.
현재값은 5이다.
1번에서 임시 스택에 값이 있으면서, 5 >= 임시스택의 pop인 동안 임시 스택을 pop한다.
2-2번에서 값이 있으므로 임시 스택의 top을 정답 스택에 push한다.
4번에서 임시 스택에 현재값을 추가한다.
현재 값은 3이다.
1번에서 임시 스택에 값이 있으면서, 3 >= 임시스택의 pop인 동안 임시 스택을 pop한다.
2-2번에서 임시 스택의 top을 정답 스택에 push한다.
4번에서 임시 스택에 현재값을 추가하고 for문은 종료된다.
정답 스택에 있는 것을 순서대로 출력하면 5 7 7 -1이 정답이다.
코드
import java.util.*;
import java.io.*;
public class Main {
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
Stack<Integer> ans = new Stack<Integer>();
Stack<Integer> tmp = new Stack<Integer>();
StringBuilder sb = new StringBuilder();
int n = stoi(br.readLine());
String[] input = br.readLine().split(" ");
for(int i = n-1; i >= 0; i--) {
int num = stoi(input[i]);
while(!tmp.isEmpty() && (num >= tmp.peek())) {
tmp.pop();
}
if(tmp.isEmpty()) {
ans.add(-1);
}else {
ans.add(tmp.peek());
}
tmp.add(num);
}
while(!ans.isEmpty()) {
sb.append(ans.pop() + " ");
}
System.out.println(sb);
}
public static int stoi(String str) {return Integer.parseInt(str);}
}
더 많은 정답 코드
블로그를 쓰기 이전에 풀어본 문제들이 많다. 해설강의는 없지만, 백준 문제의 풀이 코드가 필요한 경우 이곳을 클릭하여 소스코드를 참조해보도록 하자. 단, 코드만 복사-붙여넣기 하는것은 본인에게 결코 도움이 되지 않는다. 반드시 먼저 생각해보고, 막히는 경우에 참고하고 왜 이렇게 코드가 작성됐는지를 다시 한 번 생각해보는 습관을 들이자.
