[백준] 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번: 오등큰수
첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다.
www.acmicpc.net
* 독학으로 익히는 코딩이라 틀린 것이 있을 수 있습니다. 오류가 있다면 댓글을 통해 알려주세요. 감사합니다. *