점점 강해지고 있습니다.
[Java] 백준 17298번: 오큰수
풀이 방법
자료구조 중 Stack을 사용해서 해결한 문제이다. 생각보다 어려웠다.
문제에서 말하는 것은 나보다 큰 애들 중 첫 번째로 만나는 애! 이기 때문에 시간초과가 나지 않으려면 앞으로 나아가면서 기존 배열을 스택을 통해 초기화해주는 식으로 해결해야 한다.
구체적으로 설명하자면 받은 수열을 첫번째부터 for문으로 돌려야 한다. 이 때,
if(
| 스택이 비었다 => 비교할 수가 없으니 스택에 삽입 |
마지막으로 스택에 넣은 숫자(peek()) > 현재 인덱스 숫자 => 오큰수가 아니니 스택에 삽입
) else (
while(스택의 마지막보다 현재 인덱스가 크다면 오큰수 => 스택 peek() < 현재 인덱스 수일 때까지 stack에서 pop())
)
이런 형태로 해결했다.
풀이 코드
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Stack;
import java.util.StringTokenizer;
public class BOJ_17298_오큰수 {
public static void main(String[] args) throws Exception {
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<>();
int[] numbers = new int[N];
for(int i=0; i<N; ++i) {
numbers[i] = Integer.parseInt(st.nextToken());
}
for(int i=0; i<N; ++i) {
while(true) {
if(stack.isEmpty() || numbers[stack.peek()] >= numbers[i]) {
stack.push(i);
break;
} else {
numbers[stack.pop()] = numbers[i];
}
}
}
while(!stack.isEmpty()) {
numbers[stack.pop()] = -1;
}
StringBuilder sb = new StringBuilder();
for(int i=0; i<N; ++i) {
sb.append(numbers[i]).append(' ');
}
System.out.println(sb);
}
}
Thank You For Reading
SeungJun Jeon