문제 설명
문제
크기가 N인 수열 A = A1, A2, ..., AN이 있다. 수열의 각 원소 Ai에 대해서 오등큰수 NGF(i)를 구하려고 한다.
Ai가 수열 A에서 등장한 횟수를 F(Ai)라고 했을 때, Ai의 오등큰수는 오른쪽에 있으면서 수열 A에서 등장한 횟수가 F(Ai)보다 큰 수 중에서 가장 왼쪽에 있는 수를 의미한다. 그러한 수가 없는 경우에 오등큰수는 -1이다.
예를 들어, A = [1, 1, 2, 3, 4, 2, 1]인 경우 F(1) = 3, F(2) = 2, F(3) = 1, F(4) = 1이다. A1의 오른쪽에 있으면서 등장한 횟수가 3보다 큰 수는 없기 때문에, NGF(1) = -1이다. A3의 경우에는 A7이 오른쪽에 있으면서 F(A3=2) < F(A7=1) 이기 때문에, NGF(3) = 1이다. NGF(4) = 2, NGF(5) = 2, NGF(6) = 1 이다.
입력
첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다.
출력
총 N개의 수 NGF(1), NGF(2), ..., NGF(N)을 공백으로 구분해 출력한다.
https://www.acmicpc.net/problem/17299
17299번: 오등큰수
첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다.
www.acmicpc.net
문제 해설 및 풀이
풀이1
코드 해설
Ai를 순방향으로 탐색하면서 기존에 있던 F(Ai)의 값보다 큰 값을 발견하고 기록하고 제거 한다면 풀수 있지 않은가?근데 여기서 기존의 값이 저장되어 있다는 것은 앞에 어떤 F(Ai)값 이상이였다고 할 수 있다. 예를 들어 F(Ai)값이 저장된 것이 8,9,10 이라고 생각하면 이것은 모순 된다.
8은 9보다 작아서 삭제되어야 했으며 9는 10보다 작기때문에 삭제되어야 했다. 즉 기록되어 있는 값을 내림 차순 혹은 같은 값이 될 것을 알 수 있다.
여기서 스택을 사용하면 10,10,10,10,9,9에서 현재 값이 10일때 3번 인덱스에서 멈춰서 더 탐색을 하지 않을 수 있다.
코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.Stack;
import java.util.StringTokenizer;
public class N17299 {
public static void main(String[] args) throws IOException {
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
int n=Integer.parseInt(in.readLine());
StringTokenizer st = new StringTokenizer(in.readLine());
int[] A = new int[n];
HashMap<Integer, Integer> F = new HashMap<>();
//F의 갯수를 초기화 하면서 A배열을 초기화 한다.
for(int i=0;i<n;i++){
A[i]=Integer.parseInt(st.nextToken());
if(!F.containsKey(A[i])){
F.put(A[i],0);
}
F.put(A[i],F.get(A[i])+1);
}
int[] result = new int[n];
Stack<Integer> stack = new Stack<>();
for(int i=0;i<n;i++){
//만약 지금까지 들어온 인덱스의 F()값이 현재 인덱스의 F()값보다 작으면 스택에서 제거 하고 현재의 값을 기록한다.
while (!stack.isEmpty() && F.get(A[stack.peek()])<F.get(A[i])){
result[stack.pop()]=A[i];
}
//현재 인덱스를 기록한다.
stack.push(i);
}
//만약에 스택에 값이 남아 있다는 것은 스택에 있는 F()값보다 큰F()값을 찾지 못했다는 뜻이다.
while (!stack.isEmpty()){
result[stack.pop()]=-1;
}
StringBuilder sb = new StringBuilder();
for(int i=0; i<n; i++) {
sb.append(result[i] + " ");
}
System.out.println(sb);
}
}
풀이2
코드 해설
A를 역순으로 순회하면서 현재 있는 것과 앞에 지나왔던 것들을 비교하여 F(Ai)값이 현재보다 큰것이 있다면 기록하고 없다면 -1를 기록하면 되지 않을까?여기서 앞에 지나온 것들의 가장 최근 것은 뒤에 있는 값보다 작을 수 밖에 없다.
예를 들어 앞서 기록된 것들이 10,9,8이라면 9와 8은 10보다 작기때문에 선택 될 수 없다.
그렇기에 제거 해줌으로써 검색 속도를 증가 시킬 수 있다. 여기서 스택을 사용 할 수 있는데 첫번재 역순 순회와 기록또한 역순으로 해야하기에 기록과 지나왔던 값을 저장하는 부분을 사용 할 수 있다.
코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.Stack;
import java.util.StringTokenizer;
public class N17299 {
public static void main(String[] args) throws IOException {
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
int n=Integer.parseInt(in.readLine());
StringTokenizer st = new StringTokenizer(in.readLine());
//역순으로 순회하기 위해 스택을 사용한다.
Stack<Integer> stack = new Stack<>();
HashMap<Integer, Integer> F = new HashMap<>();
for(int i=0;i<n;i++){
stack.add(Integer.parseInt(st.nextToken()));
if(!F.containsKey(stack.peek())){
F.put(stack.peek(),0);
}
F.put(stack.peek(),F.get(stack.peek())+1);
}
Stack<Integer> history = new Stack<>();
Stack<Integer> result=new Stack<>();
while (!stack.isEmpty()){
Integer pop = stack.pop();
//현재값보다 작거나 같은 값들을 제거한다.
while (!history.isEmpty()&&F.get(pop)>=F.get(history.peek())) history.pop();
//현재보다 큰값이 없으면 -1
if(history.isEmpty()){
result.add(-1);
}else{
result.add(history.peek());
}
//현재를 기록한다.
history.add(pop);
}
StringBuilder sb = new StringBuilder();
while (!result.isEmpty()){
sb.append(result.pop()+" ");
}
System.out.println(sb);
}
}