[백준] 17299번 오등큰수 JAVA (자바) 풀이

문제 17299번

 :  크기가 N인 수열 A = A1, A2, ..., AN이 있다. 수열의 각 원소 Ai에 대해서 오등큰수 NGF(i)를 구해라

 :  Ai가 수열 A에서 등장한 횟수를 F

 :  Ai의 오등큰수는 오른쪽에 있으면서 F가 큰 수 중에서 가장 왼쪽에 있는 수를 의미한다

 :  그러한 수가 없는 경우에 오등큰수는 -1

 

 

  (예시)

    A = [3, 5, 2, 7]인 경우 NGE(1) = 5, NGE(2) = 7, NGE(3) = 7, NGE(4) = -1
    A = [9, 5, 4, 8]인 경우 NGE(1) = -1, NGE(2) = 8, NGE(3) = 8, NGE(4) = -1이다.

 

 

 [입력]

  

 :  첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)

 :  둘째에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)

 

 [출력]

 :  총 N개의 수 오등큰수를 공백으로 구분해 출력

 

 [문제 이해]

 

 : 오등큰수는 count가 아니다 수열 안에 있는 숫자 넣어줘야 한다

 :  문제푸는 방식을 외워야 한다

    무조건 스택 안의 peek값과 다음 수열을 비교한다

 :  오큰수와 다른점은 peek값과 다음수열을 비교하는 것이 아닌 다음 수열의 count 값을 비교하는 것이다

 :  count란 수열안에 같은 숫자가 몇회 반복되어 나왔는지의 횟수를 의미한다

 

 :  비교해봐서 오큰등수 못구하면 더 비교하지말고 push한 다음 바로 다음 것들끼리 다시 비교한다

    그리고나서 그다음번에 오큰등수를 구하게 되면 해당 수열을 pop하고

    이전에 못구했던 숫자들을 하나씩 다시 비교하면 된다

 

 :  더이상의 비교대상이 없을 때까지 비교한 뒤 마지막 수열에 남는 것들은 -1 처리해준다

 

  <그림설명>

 

수열	1	1	2	3	2	1
Index	0	1	2	3	4	5

count

3

2

1

- 수열 순서대로 count 센 것

- 1부터 나왔으니 총 개수 3개, 다음 2 나왔으니 총 개수 2개, 다음 1 나왔으니 총 개수 1

 

 

1단계	2단계	3단계	4단계	5단계	6단계	7단계	8단계	9단계
			3		4
		2	2	2	2	2		5
	1	1	1	1	1	1	1	1
0	0	0	0	0	0	0	0	0

 * 이 스택에 들어가는 수는 수열이 아닌 Index 이다  

 

단계 1)

처음에는 스택에 아무 것도 없어서 일단 Index 0 번을 넣고 시작 (오큰수랑 같다)

사실상 Index 0 을 가진 1 이다

 

단계2)

스택의 peek인 Index 0과 옆의 수 Index 1 이자 1의 count를 비교한다 

둘다 1이기 때문에 횟수 즉 count 가 같다

오등큰수를 구할 수 없으므로 일단 Index 1을 push 하고 그 다음으로 넘어간다

 

단계3)

스택의 peek인 Index 1과 옆의 수 Index 2 이자 2의 count를 비교한다 

Index 2의 count가 더 작으므로 오등큰수를 구할 수 없다

Index 2를 push하고 다음으로 넘어간다

 

단계4)

스택의 peek인 Index 2와 옆의 수 Index 3 이자 3의 count를 비교한다 

Index 3의 count가 더 작으므로 오등큰수를 구할 수 없다

Index 3을 push하고 다음으로 넘어간다

 

단계5)

스택의 peek인 Index 3과 옆의 수 Index 4 이자 2의 count를 비교한다 

Index 4의 count가 더 크므로 오등큰수를 구할 수 있다 이때 Index4의 count 는 2 이다

고로 Index 3의 오등큰수는 2이다

Index 3은 다썼으니 pop하고 다음으로 넘어간다

 

단계6)

스택의 peek인 Index 2와 이어서 아까 비교하던 수 Index 4이자 2의 count를 비교한다 

둘다 2이기 때문에 횟수 즉 count 가 같다

오등큰수를 구할 수 없으므로 일단 Index 4를 push 하고 그 다음으로 넘어간다

 

단계7)

스택의 peek인 Index 4과 옆의 수 Index 5이자 1의 count를 비교한다 

Index 5의 count가 더 크므로 오등큰수를 구할 수 있다 이때 Index 5의 count는 3 이다

고로 Index 4의 오등큰수는 1이다

Index 4은 다썼으니 pop하고 다음으로 넘어간다

 

단계8)

스택의 peek인 Index 2와 이어서 아까 비교하던 수 Index 5이자 1의 count를 비교한다 

Index 5의 count가 더 크므로 오등큰수를 구할 수 있다 이때 Index 5의 count는 3 이다

고로 Index 2의 오등큰수는 1이다

Index 2는 다썼으니 pop하고 다음으로 넘어간다

 

단계9)

스택의 peek인 Index 1과 이어서 아까 비교하던 수 Index 5이자 1의 count를 비교한다 

둘다 1이기 때문에 횟수 즉 count 가 같다

오등큰수를 구할 수 없으므로 일단 Index 5를 push 하고 그 다음으로 넘어간다

 

단계10)

이제 더이상 비교할 수가 남아있지 않으므로 스택 안의 모든 수를 -1로 출력한다

 

 

오   등   큰   수      결     과
- 1	- 1	1	2	1	- 1
단계 10 참고	단계 10 참고	단계 8 참고	단계 5 참고	단계 7 참고	단계 10 참고

 

 [스택 연산]

 

push(e)	스택의 맨 위에 요소 e 추가
pop()	스택의 맨 위 요소를 삭제
peek(s)	스택의 맨 위 요소를 삭제하지 않고 반환
top()	스택 맨 위에 있는 데이터 값 반환
isEmpty()	스택에 원소가 없으면 'True', 있으면 'False' 값 반환
isFull()	스택에 원소가 없으면 'False', 있으면 'True' 값 반환

 

 [코드]

 

import java.io.*;
import java.util.*;
public class Main {
	public static void main(String[] args) throws IOException {
		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());
		int[] arr = new int[n];
		String[] input = br.readLine().split(" ");
                int count[] = new int[1000001]; //횟수담기
 
		for(int i = 0; i < n; i++){
			arr[i] = Integer.parseInt(input[i]);
                        count[arr[i]]+=1; // 카운트의 같은 배열이면 +1씩 증가
                }
		
		for(int i = 0; i < n; i++) {
			while(!stack.isEmpty() && count[arr[stack.peek()]] < count[arr[i]]) {
                            arr[stack.pop()] = arr[i];
			}
			stack.push(i); //오큰수랑 같다
                }
		
		while(!stack.isEmpty())
			arr[stack.pop()] = -1;
		
		for(int i = 0; i < n; i++)
			bw.write(arr[i]+" ");
		
        bw.flush();
	return;
    }
}

 

 [해설]

 :  Stack<Integer> stack = new Stack<>();  스택선언

 :  int n = Integer.parseInt(br.readLine());  첫째줄 개수 입력받기

 :  int[] arr = new int[n];  수열 담을 배열 선언

 :  int count[] = new int[1000001];  횟수담기

 :  String[] input = br.readLine().split(" ");  두번째 줄 공백으로 구분하기

    다른 표현1)
    StringTokenizer st = new StringTokenizer(br.readLine, " ")
     
    다른 표현2)
    String s = br.readLine();
    String spt[] = s.split(" ");
        
 :  for(int i = 0; i < n; i++){
               arr[i] = Integer.parseInt(input[i]);  입력들 배열에 담는게 제일 먼저다
               count[arr[i]]+=1;  같은 수들끼리의 count +1씩 증가
     }

 :  for(int i = 0; i < n; i++) {
              while(!stack.isEmpty() && count[arr[stack.peek()]] < count[arr[i]]) {
                    오큰수는 스택의 peek와 그다음 수열을 비교했지만
                    오등큰수는 스택 peek의 count와 그 다음 수열의 count를 비교한다
                          arr[stack.pop()] = arr[i]; 해당수열 빼고 오등큰수로 바꾸기
             }            
             stack.push(i);  다음 인덱스 추가하기 (오큰수랑 같다)
    }

 :  while(!stack.isEmpty())
             arr[stack.pop()] = -1;  마지막으로 스택 안에 남은 애들 -1로 바꿔주기 (오큰수랑 같다)

 :  for(int i = 0; i < n; i++)
             bw.write(arr[i]+" ");  출력하기
            

 

이제 풀어보러 갈께요 :)

 

 

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

17299번: 오등큰수

 

* 독학으로 익히는 코딩이라 틀린 것이 있을 수 있습니다. 오류가 있다면 댓글을 통해 알려주세요. 감사합니다. *