#17299: 오등큰수
문제:
크기가 N인 수열 A = A1, A2, …, AN이 있다. 수열의 각 원소 Ai에 대해서 오등큰수 NGF(i)를 구하려고 한다.
Ai가 수열 A에서 등장한 횟수를 F(Ai)라고 했을 때, Ai의 오등큰수는 오른쪽에 있으면서 수열 A에서 등장한 횟수가 F(Ai)보다 큰 수 중에서 가장 왼쪽에 있는 수를 의미한다. 그러한 수가 없는 경우에 오등큰수는 -1이다.
예를 들어, A = [1, 1, 2, 3, 4, 2, 1]인 경우 F(1) = 3, F(2) = 2, F(3) = 1, F(4) = 1이다. A1의 오른쪽에 있으면서 등장한 횟수가 3보다 큰 수는 없기 때문에, NGF(1) = -1이다. A3의 경우에는 A7이 오른쪽에 있으면서 F(A3=2) < F(A7=1) 이기 때문에, NGF(3) = 1이다. NGF(4) = 2, NGF(5) = 2, NGF(6) = 1 이다.
입력:
첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째에 수열 A의 원소 A1, A2, …, AN (1 ≤ Ai ≤ 1,000,000)이 주어진다.
풀이:
우선 처음으로 이 문제를 풀기 전에 #17298: 오큰수 문제를 먼저 풀어보기를 권유한다. 위 링크에 문제를 어떻게 푸는 지 자세한 설명이 있으며 이 문제는 오큰수 문제에서 한가지를 추가하고 한가지 조건만 변경하면 풀 수 있다.
-
우선 각 숫자마다 개수를 세어줘야 되고 Ai의 최댓값은 1,000,000이기 때문이니까 1,000,000 크기의 int 배열을 만들어줘야 된다. 그리고 입력을 받을 때 그 값을 인덱스로 가진 배열의 값을 1 더해준다.
⭐여기서 조심 해야 될 것은 메인 함수 안에서 배열을 선언 시 배열의 최대 크기가 1,000,000 이상이 될 수가 없다. 그 이유로는 함수가 호출 될 때마다 해당 배열을 위한 메모리를 새로 생성하고 초기화 해야 된다. 이때 크기가 크면 초기화 시 값을 채워 넣을 때 시간이 오래 걸리는 문제가 발생하여 시스템에 따라 다르지만 하드웨어 적인 제한이나 스택의 운영 효율을 올리기 위해 스택의 크기를 제한하기도 한다. 그래서, 스택 오버플로우가 발생할 수 있으며 프로그램이 강제 종료 될 수 있다. 그래서 main 함수에 선언하면 프로그램이 입력을 받기 전에 강제 종료 된다. 하지만, 글로벌 변수로 선언 시에는 가능하므로 글로벌 변수로 선언 해주도록 하자. 자세한 내용은 LINON : Game Dev. 블로그의 글을 참고하면 된다.
-
오큰수와의 유일한 차이는 숫자의 크기가 아닌 그 숫자의 개 수를 비교한다는 것이다. 그것 빼고는 차이가 없기 때문에 while문에 2번째 if에서 s.top()과 NGF.top() 크기를 비교하였던 것을 배열[s.top()]과 배열[NGF.top()]의 크기를 비교하면 된다.
코드:
#include <iostream>
#include <stack>
using namespace std;
int amount[1000000] = {}; // 추가 된 배열 선언
int main(){
int n;
stack<int> s, NGF, answer;
//입력
cin >> n;
for(int i = 0; i < n; i++){
int temp;
cin >> temp;
//각 숫자를 인덱스로 나타내고 그 숫자의 개수를 배열에 저장
amount[temp]++; // 추가 된 배열 연산
s.push(temp);
}
while(!s.empty()){
//제일 오른쪽 숫자가 아닐 때
if(!NGF.empty()){
//오른쪽 숫자가 클 때
if(amount[s.top()] < amount[NGF.top()]){ //변경 된 if문
answer.push(NGF.top());
NGF.push(s.top());
s.pop();
}
//오른쪽 숫자가 작을 때
else{
NGF.pop();
}
}
//제일 오른쪽 숫자여서 NGF가 비어있을 때
else{
answer.push(-1);
NGF.push(s.top());
s.pop();
}
}
//정답 출력
for(int i = 0; i < n; i++){
if(!answer.empty()){
cout << answer.top() << " ";
answer.pop();
}
}
}
Leave a comment