17299 자바 ] 오등큰수(풀이)

※ 문제

출처(https://www.acmicpc.net/problem/17299)

---

문제 이해하기.

'예제 입력 1'로 설명해보겠다.

7

1 1 2 3 4 2 1

 

우선 7가지의 숫자의 각 개수를 구한다.

1은 3개, 2는 2개, 3은 1개, 4는 1개이다.

입력값의 개수만큼 숫자의 개수를 작성하면 '3 3 2 1 1 2 3'이 되는데 이 숫자에 대한 오큰수를 구하면 되는 것이다.

오큰수는 3 3 2 1 1 2 3 중 가장 앞에 있는 숫자 3보다 큰 숫자는 없기 때문에 -1이 되고

마찬가지로 다음 3도 -1이며 그다음 숫자는 2보다 큰 3이 존재하기 때문에 입력값인 1이 되는 것이다.

이렇게 구하면 정답은 '-1 -1 1 2 2 1 -1'이 나온다.

---

1. 성공

 1) 설계

  - 오큰수의 로직을 그대로 가져와서 사용했다. 단 오등큰수는 문자열 숫자의 각 개수의 오큰수를 구하는 것이기에 개수의 원래 값을 연결하여 불러와야 한다.

 - 오큰수와 같이 '1 1 2 3 4 2 1'을 뒤에서부터 순서대로 비교한다. 그리고

 

먼저,

가로 ①. 입력값 1의 개수 3은 가장 오른쪽에 있기 때문에 비교 값이 존재하지 않는다. 이 경우 결과 스택에 -1을 push 하고 임시 스택에 3을 push 한다.

가로 ②. 입력값 2의 개수 2는 임시 스택에 있는 3과 비교한 후 결과 스택에 push 하고 임시 스택에 2를 push 한다.

가로 ③. 입력값 4의 개수 1은 임시 스택에 있는 2와 비교한 후 결과스택에 push 하고 임시 스택에 1을 push 한다.

가로 ④. 입력값 3의 개수 1은 임시 스택에 1보다 크기 때문에 1을 pop 해서 제거해준다.(이때 오등 큰 수에서는 입력값의 index를 따라가기 위한 조치도 필요하다.) 그리고 수행 2번과 3번을 통해 보다 큰 값과 비교한다.

가로 ⑤. ④번과 마찬가지로 끝까지 비교한다.

가로 ⑥. ④, ⑤번처럼 끝까지 비교한다.

가로 ⑦. 결과를 다 구했으므로 break; 종료한다.

 2) 코드

import java.io.*;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.Stack;
import java.util.StringTokenizer;

public class Main {
    static Stack<Integer> stack = new Stack<>();
    static Stack<Integer> resultStack = new Stack<>();
    static Stack<Integer> tempStack = new Stack<>();
    static HashMap<Integer, Integer> map = new HashMap<>();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int N = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        ArrayList<Integer> list = new ArrayList<>();

        /** list:입력값, map:숫자별 개수 */
        for(int i=0; i<N; i++) {
            list.add(Integer.valueOf(st.nextToken()));
            map.put(list.get(i), map.getOrDefault(list.get(i), 0)+1);
        }

        /** stack:입력값 index에 알맞은 숫자별 개수 */
        for(int i=0; i<N; i++) {
            stack.push(map.get(list.get(i)));
        }

        int idx = N-1;
        while(!stack.isEmpty()) {
            int temp = stack.pop();

            // 우측에 값이 없기 때문에 -1
            if(idx == N-1) {
                tempStack.push(temp);
                resultStack.push(-1);

            // 현재값 보다 임시스택의 값이 큰 경우
            } else if(!tempStack.isEmpty() && temp < tempStack.peek()) {
                resultStack.push(list.get(idx+1));
                tempStack.push(temp);
            } else {
                // 현재값 보다 임시스택의 값이 큰 경우 없음
                if(tempStack.isEmpty()) {
                    resultStack.push(-1);
                    tempStack.push(temp);

                // 임시스택의 값을 하나 삭제하고 다음 값으로 stack 및 index 세팅
                } else {
                    tempStack.pop();
                    stack.push(temp);
                    list.remove(idx+1);
                    idx++;
                }
            }

            idx--;
        }

        while(!resultStack.isEmpty()) {
            bw.write(resultStack.pop() + " ");
        }
        bw.flush();
        bw.close();
    }
}

 

 

오등큰수를 풀기 전에 오큰수를 한 번 풀어보는 것을 추천한다.

https://jfbta.tistory.com/185

17298 자바 ] 오큰수(풀이)

---

문제의 예제는 모두 통과하였으나 정확도의 이슈가 해결되지 않은 분은 아래 반례로 확인해보기 바랍니다.

※ 반례

11
1 10 999999 7 999998 3 1 4 1000000 3 1000000
정답 : -1 3 3 3 3 -1 -1 1000000 -1 -1 -1 

 

3

1 3 2

정답 : -1 -1 -1