11주차. 오등큰수

17299. 오등큰수

https://www.acmicpc.net/problem/17299

17299번: 오등큰수

📌문제

- 예제1

  📝입력

7
1 1 2 3 4 2 1

  💻출력

-1 -1 1 2 2 1 -1

📌풀이

문제를 풀기위한 흔적

풀이 법은 오큰수와 비슷하다. 다만 각 숫자가 수열에서 몇번 나오는지 체크해줘야 했기때문에 Map을 활용했다. 원래는 Map에 저장한 등장 횟수를 토대로 다시 배열을 만들 생각이었는데, 다시 생각해보니까 그럴 필요가 없었다. map에서 바로 get 해오면 되니까 말이다.

미적감각 0%

마찬가지로 스택에는 인덱스를 넣어준다. 배열의 사이즈만큼 for문을 돌면서 체크할 숫자(인덱스)의 배열 값 즉, 수열에서 해당하는 숫자가 몇번나왔는지를 Map을 통해서 개수를 구해오고, 스택 top에 해당하는 인덱스 또한 마찬가지로 개수를 구해온다. 이 둘을 비교해서 현재 체크하려는 숫자가 더 크면 answer 배열 값에 해당 배열의 값을 넣어주면 된다.

 

위의 그림을 예제로 설명하자면, 인덱스 0,1, 2, 3, 4까지는 아무 일 없이 stack에 들어가게 된다. 이때 수열의 숫자 중 빨갛게 표시된 2를 체크하게 될 때, 2가 나온 개수는 2번, 그리고 4가 나온 개수는 1번이므로  2가 인덱스 4번째 배열(4)의 오등큰수가 된다. 인덱스 4는 체크해줬으므로 pop해주고 while문을 통해 그다음 스택의 top이 되는 인덱스 3을 비교해준다. 3또한 2가 오등큰수이므로 정답 배열에 2를 넣어준다. 이런 식으로 정답을 찾아가면 된다.

 

1568ms 262352kb

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.Map;
import java.util.Stack;
import java.util.StringTokenizer;

public class 오등큰수 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[] arr = new int[n];
        int[] answer = new int[n];
        StringTokenizer st = new StringTokenizer(br.readLine());
        Map<Integer, Integer> map = new HashMap<>();
        Stack<Integer> stack = new Stack<>();

        for (int i = 0; i < n; i++){
            int num = Integer.parseInt(st.nextToken());
            arr[i] = num;
            map.put(num, map.getOrDefault(num, 0) + 1);
        }

        stack.add(0);
        for(int i = 1; i < n; i++){
            while(!stack.isEmpty() && map.get(arr[i]) > map.get(arr[stack.peek()])){
                answer[stack.pop()] = arr[i];
            }
            stack.add(i);
        }
        StringBuilder sb = new StringBuilder();
        for(int num : answer){
            if(num == 0) sb.append(-1).append(" ");
            else sb.append(num).append(" ");
        }
        System.out.println(sb);

    }
}