[BOJ-JAVA] 17299번: 오등큰수
문제
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
수열이 주어질 때 각각 인덱스의 수에서 오른쪽에 있는 수 중 가장 개수가 많은 최좌측 수를 구하는 문제이다.
https://www.acmicpc.net/problem/17298
17298번: 오큰수
첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다.
www.acmicpc.net
오큰수 문제와 상당히 유사한 대신 개수를 사용한다는 점이 다르다.
문제풀이
우선 주어진 수열의 가장 큰수를 이용해 배열을 만들고 개수를 센 후 배열에 저장해둔다. (여기서 index는 각 수를 의미, 저장된 값은 개수)
여기서도 역시나 stack을 이용해서 문제를 해결한다. 수열을 차례로 확인하며 count가 큰 수가 나올 때까지 index를 stack에 push하고, count가 큰 수를 만나면 stack.peek와 비교해가며 값을 count가 큰 수로 변경한다.
https://miraekwak.tistory.com/165
[BOJ-JAVA] 17298번: 오큰수
문제 https://www.acmicpc.net/problem/17298 17298번: 오큰수 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다. www.acmicpc.net 수열
miraekwak.tistory.com
오큰수 풀이에서 count를 추가한 것이다.
Java Code
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Stack;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.valueOf(br.readLine());
String[] line = br.readLine().split(" ");
int[] arr = new int[N];
for(int i=0; i<N; i++) {
arr[i] = Integer.valueOf(line[i]);
}
int[] count = new int[Arrays.stream(arr).max().getAsInt()+1];
for(int num: arr) {
count[num] += 1;
}
Stack<Integer> stack = new Stack<>();
for(int i=0; i<N; i++) {
while(!stack.empty() && count[arr[i]] > count[arr[stack.peek()]]) {
arr[stack.pop()] = arr[i];
}
stack.push(i);
}
while(!stack.empty()){
arr[stack.pop()] = -1;
}
StringBuilder sb = new StringBuilder();
for(int ngf: arr){
sb.append(ngf).append(' ');
}
System.out.println(sb);
}
}