15. 17299번 오등큰수

 

문제 이해

저번 17298번 오큰수 문제는 해당 숫자보다 오른쪽에 있으면서 그 숫자보다 큰숫자들 중에서 제일왼쪽에 있는 수를 고르는 것이였다면

 

이번 17299번 오등큰수 문제는 해당 숫자의 수량보다 오른쪽에 있으면서 그 숫자의 수량보다 큰 수량들 중에서 가장 왼쪽에 있는 수를 고르는 것이다.

 

즉 입력받는 숫자를 비교하는 것이아닌 입력받은 숫자를 한번더 가공해서 비교하여 결과를 도출해 내는 것이라 할 수 있겠다.

 

	명령받은수	7
수열 A의 값		1	1	2	3	4	2	1
수열 A의 값들의 수량		3	3	2	1	1	2	3

예제를 받으면 위와 같다

위 예제를 실행하게되면 아래와 같은 결과가 나와야한다

-1

-1

1

2

2

1

-1

실질적으로 비교할 수는

1 1 2 3 4 2 1 이 아닌

 

3 3 2 1 1 2 3 이라고 봐야 한다는 것

 

따라서 나는 3 3 2 1 1 2 3 으로 가공 할 수 있게끔 하나의 배열을 더 추가했다

int N = Integer.parseInt(br.readLine());

int[] A = new int[N];
int[] B = new int[N];
int[] C= new int[???];

A는 명령받은 수 들이 들어갈 배열
B는 결과 값이 들어갈 배열
C는 A를 가공해 넣어둘 배열

이때 포인트는 1 1 2 3 4 2 1 에서 

1은 3개

2는 2개

3은 1개

4는 1개 일때 이것들을 어떻게 정의해서 넣는가 이다

 

C[A[n]] = C[A[n]]+1;

이렇게 반복문을 돌리면 어떨까 하고 고심끝에 생각해냈다.

반복이 돌아간다면 아래와 같을것이다

C[A[0]] = C[A[0]] + 1;
이때 A[0]은 1
따라서 C[1] = C[1] + 1;
A[0] 값인 1이 C에 들어갈때마다 C[1]에 1을 추가한다. 다음으로

C[A[1]] = C[A[1]] + 1;
A[1]은 1
C[1] = C[1] + 1;
위에서 이미 1이 추가되었으므로 C[1]은 2가 된다. 다음으로

C[A[2]] = C[A[2]] + 1;
A[2]는 2
C[2] = C[2] + 1;
C[2]는 이전에 아무값이 없었으므로 1이 추가되어 1이된다.

이제 대강 그림이 보이지않는가?

위와같이 반복하게되면 C[1] , C[2], C[3], C[4] 가 생길것이고

이때의 1,2,3,4는 각각 A배열의 값과 동일하게 된다.

따라서 C[1]은 값 1의 개수

C[2]는 값 2의 개수

C[3]은 값 3의 개수

C[4]는 값 4의 개수가 되겠다.

 

이제 이를 17298번 오큰수에서 풀었던 코드에서 살짝만 수정해주면 가능 할 것이다.

 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Stack;
 

public class training2 {

	public static void main(String[] args) throws Exception {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        Stack<Integer> stack = new Stack<>();

        //입력받는 명령의 수
        int N = Integer.parseInt(br.readLine());
        
        //입력받은 수가 들어갈 배열A
        int[] A = new int[N];
        
        //결과값이 들어갈 배열 B
        int[] B = new int[N];
        
        //A배열의 값들의 개수를 파악할 배열C
        int[] C = new int[1000001];
        //이때의 1000001은 문제에서 주어진 명령의수가 최대일때를 가정하에 만들었다
        


        for (int i = 0; i < N; i++){
            B[i] = -1;
        }
        //결과 배열의 모든값을 -1로 초기화 

        
        String[] arr = br.readLine().split(" ");
        stack.push(0);
        // 입력받을 수들을 받아 A배열에 넣는 과정
        for (int i = 0; i< N; i++) {
        A[i] = Integer.parseInt(arr[i]);
        }
        
        // A값의 개수를 확인하는 C배열
        for (int i = 0; i< N; i++) {
        C[A[i]] = C[A[i]] +1;
        }

        for (int i = 1; i < N; i++) {
        	if(stack.isEmpty()){
            	stack.push(i);
            }
            while (!stack.isEmpty() && C[A[i]] > C[A[stack.peek()]]) {
                //스택의 가장 윗부분의 값과 비교해서 클때까지 반복

                B[stack.pop()] = A[i];  
            }
            stack.push(i);
        }

        for (int i = 0; i < N; i++){
            bw.write(B[i] + " ");
            //결과값
        }
         
        bw.flush();
        bw.close();
    }
}

결과