오큰수
출처 | 오큰수 [백준 17298]
문제
크기가 N인 수열 A = A1, A2, ..., AN이 있다. 수열의 각 원소 Ai에 대해서 오큰수 NGE(i)를 구하려고 한다. Ai의 오큰수는 오른쪽에 있으면서 Ai보다 큰 수 중에서 가장 왼쪽에 있는 수를 의미한다. 그러한 수가 없는 경우에 오큰수는 -1이다.
예를 들어, A = [3, 5, 2, 7]인 경우 NGE(1) = 5, NGE(2) = 7, NGE(3) = 7, NGE(4) = -1이다. A = [9, 5, 4, 8]인 경우에는 NGE(1) = -1, NGE(2) = 8, NGE(3) = 8, NGE(4) = -1이다.
입력
첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다.
출력
총 N개의 수 NGE(1), NGE(2), ..., NGE(N)을 공백으로 구분해 출력한다.
풀이1 [시간초과]
// 풀이 1 시간초과
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
// import java.util.Stack;
import java.util.StringTokenizer;
public class Main{
public static void main(String[] args) throws IOException{
BufferedReader scan = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(scan.readLine());
int [] arr = new int[N];
StringTokenizer st = new StringTokenizer(scan.readLine());
for (int i = 0; i< N; i++) {
arr[i] = Integer.parseInt(st.nextToken());
}
int count = 0;
while (count < N) {
int count1 = 0;
for (int i = count; i < N; i++) {
// System.out.println(arr[count]+ "!!");
if (arr[count] < arr[i]) {
System.out.print(arr[i] + " ");
break;
}
else {
count1++;
}
}
if (count1 == (N - count)) {
System.out.print(-1 + " ");
}
count++;
}
}
}풀이 2 [시간초과]
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;
import java.util.StringTokenizer;
public class Main{
public static void main(String[] args) throws IOException{
BufferedReader scan = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(scan.readLine());
// 배열 생성
StringTokenizer st = new StringTokenizer(scan.readLine());
int [] arr = new int[N];
for (int i = 0; i< N; i++) {
arr[i] = Integer.parseInt(st.nextToken());
}
Stack<Integer> index = new Stack<Integer>(); // 비교를 위한 배열 인덱스로서 스택 사용
StringBuilder sb = new StringBuilder();
index.push(0); // 가장 초기 비교값
for (int i = 1; i < N; i++) {
int count = i;
while (!index.empty()) {
// 오큰수를 만나는 경우
if (arr[index.peek()] < arr[count]) {
index.pop();
sb.append(arr[count] + " ");
// 마지막 수는 -1
if (i == N-1) {
sb.append(-1);
}
}
// 오큰수를 만나지 못해 다음 수와 비교하는 경우
else {
//
if (i == N-1) {
sb.append(-1 + " ");
}
count++;
}
if (count == N) {
sb.append(-1 + " ");
index.pop();
}
}
if (index.empty()) {
index.push(i);
}
}
System.out.print(sb);
}
}풀이 3
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Stack;
import java.util.StringTokenizer;
public class Main{
public static void main(String[] args) throws IOException{
BufferedReader scan = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(scan.readLine());
// 배열 생성
StringTokenizer st = new StringTokenizer(scan.readLine());
int [] arr = new int[N];
int [] res = new int[N];
for (int i = 0; i< N; i++) {
arr[i] = Integer.parseInt(st.nextToken());
}
Stack<Integer> index = new Stack<Integer>(); // 비교를 위한 배열 인덱스로서 스택 사용
index.push(0); // 가장 초기 비교값
for (int i = 1; i < N; i++) {
// 오른쪽으로 진행하면서 더 큰 수가 나올 때
while (!index.empty() && arr[index.peek()] < arr[i]) {
// 오큰수를 만나는 경우
res[index.pop()] = arr[i];
}
index.push(i);
if (index.empty()) {
index.push(i);
}
}
while (!index.empty()) {
res[index.pop()] = -1;
}
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
for (int i = 0; i < N ; i++) {
bw.write(res[i] + " ");
}
bw.write("\n");
bw.flush();
}
}출처
알고리즘 분류
기억창고👩🌾