[백준] 17298번 오큰수 / Java, Python
Baekjoon Online Judge
algorithm practice
- 단계별 문제풀기
18. 스택
스택을 구현하고 사용해 봅시다.
스택을 구현하고 사용해 봅시다.
Java / Python
6. 오큰수
스택으로 풀 수 있는 꽤 어려운 문제
이번 문제는 크기가 N인 수열에서 각 원소에 대해 오른쪽에 있으면서 해당 원소보다 큰 수 중에서 가장 왼쪽 수를 구하는 문제입니다.
수열을 탐색할 때, 현재 원소가 이전에 있는 원소보다 작을 때 까지 수열의 index를 stack에 추가(push) 하는 것입니다. 만약 현재 원소가 스택의 top 원소를 인덱스로 하는 수열의 원소보다 클 경우 stack의 원소를 pop하면서 해당 인덱스에 해당하는 원소들을 현재 원소로 바꿔주는 원리입니다.
- Java
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.StringTokenizer;
import java.util.Stack;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
Stack<Integer> stack = new Stack<Integer>();
int N = Integer.parseInt(br.readLine());
int[] seq = new int[N];
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
for(int i = 0; i < N; i++) {
seq[i] = Integer.parseInt(st.nextToken());
}
for(int i = 0; i < N; i++) {
// 스택이 비어있지 않고
// 현재 원소 > 스택의 맨 위 원소가 가리키는 원소
// 조건을 만족할 때 까지 stack의 원소를 pop
// 해당 인덱스의 값을 현재 원소로 변환
while(!stack.isEmpty() && seq[stack.peek()] < seq[i]) {
seq[stack.pop()] = seq[i];
}
stack.push(i);
}
// 스택의 모든 원소를 pop하면서 해당 인덱스의 value = -1로
while(!stack.isEmpty()) {
seq[stack.pop()] = -1;
}
StringBuilder sb = new StringBuilder();
for(int i = 0; i < N; i++) {
sb.append(seq[i]).append(' ');
}
System.out.println(sb);
}
}
- Python
import sys
N = int(sys.stdin.readline())
seq = list(map(int, sys.stdin.readline().split()))
stack = []
result = [-1 for _ in range(N)]
stack.append(0)
i = 1
while stack and i < N:
while stack and seq[stack[-1]] < seq[i]:
result[stack[-1]] = seq[i]
stack.pop()
stack.append(i)
i += 1
for i in range(N):
print(result[i], end = " ")
Author And Source
이 문제에 관하여([백준] 17298번 오큰수 / Java, Python), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@jini_eun/백준-17298번-오큰수-Java-Python저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)