[백준] 14298-오큰수(Java)
우선 내가 처음으로 푼 골드문제다...! 물론 완벽히 내힘으로 풀진 못했지만 그래도 어찌저찌 풀었다.
단계별로 풀기에서 스택 카테고리에 있던 문제라 좀 더 힌트가 되지 않았나 싶다.
접근 방법
이 문제를 처음 읽었을 때는 왜 스택을 써야하지..? 라는 생각이 들었다. 처음에 생각한 방법은 이중 포문이였다. 하지만 이중포문을 돌게 되면 시간복잡도가O(n^2)
이므로 시간초과로 인해 통과할 수 없었다. 그래서 자연스럽게 스택을 써야하는 이유를 알게 되었다.
로직 설명
먼저 여기서는 수열의 각 원소를 가리키는 변수 t
가 필요하고, 답을 구하기 위해 잠시 담아두는 temp스택
과 진짜 답을 담는 NGE스택
이 필요하다.
t(수열)는 뒤에서부터 차례로 검사한다.
- temp가 비어있으면 (=t보다 오른쪽에 큰수가 없다는 뜻)
NGE.push(-1);
temp.push(t);
- temp가 비어있지 않으면, temp에서 t값보다 작은것을 모두 pop해서 빼버림. ==> temp에는 t보다 오른쪽에 있으며, 큰값만 존재.
- 만약 temp에 있는 모든 원소를 빼서 isEmpty()==true이면,
NGE.push(-1);
temp.push(t);
- 아니라면,
NGE.push(temp.peek());
==> t의 오큰수
temp.push(t);
구현 코드
import java.io.*;
import java.util.*;
import java.util.Stack;
public class No17298_오큰수 {
public static void main(String[] args) throws IOException, EmptyStackException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
int tc = Integer.parseInt(br.readLine());
String[] str = br.readLine().split(" ");
Stack<Integer> temp = new Stack<>();
Stack<Integer> NGE = new Stack<>();
int t=0;
for (int i=tc-1;i>=0;i--) {
t=Integer.parseInt(str[i]);
if(temp.isEmpty()) {
NGE.add(-1);
temp.push(t);
}
else {
while (!temp.isEmpty() && t >= temp.peek())
temp.pop();
if (!temp.isEmpty()) {
NGE.add(temp.peek());
}
else {
NGE.add(-1);
}
temp.add(t);
}
}
for (int i=0;i<tc;i++)
sb.append(NGE.pop()+" ");
System.out.println(sb.toString());
}
}
이렇게 되면 O(N)까지 시간복잡도를 줄일 수 있게 된다.
처음에는 스택을 3개써서 하느라 또 시간초과가 나왔다. 이런 방법을 생각하는게 아직까진 어렵지만, 풀이방법을 익히고 점점 연습하다 보면 괜찮아질거라고 생각한다!
Author And Source
이 문제에 관하여([백준] 14298-오큰수(Java)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@kekim20/백준-14298-오큰수Java저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)