17299 - 오등큰수

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

17299번: 오등큰수

 

 

랭크 : 골드 3

 

17298 오큰수와 세트인 문제다. 접근법도 거의 흡사하다.

 

---

1. 문제 이해

 

=> 크기가 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)이 주어진다.

출력 : 총 N개의 수 NGF(1), NGF(2), ..., NGF(N)을 공백으로 구분해 출력한다.

---

2. 재정의 & 추상화

 

입력이 7 1 1 2 3 4 2 1 이면, 1이 3개, 2가 2개, 3이 1개, 4도 1개이므로 => -1 -1 1 2 2 -1 -1.

각 수열 숫자에서, 오른쪽 숫자 중 처음으로 본 숫자보다 빈도가 높은 수를 프린트. 

그러면 수열의 숫자별 빈도를 필수적으로 알아야겠네. 입력 배열의 처음부터 끝까지 무조건 한번은 찍어야겠고.

 

 

 

---

3. 설계

 

각 숫자별 빈도를 담은 frequency 배열을 만든다. frequency[1] 은 1의 빈도값이며, frequency[10]은 10의 빈도 값이다. 

처음 for문을 돌면서, cin으로 값을 입력받아 frequency배열과 입력 배열을 초기화한다.

그리고 stack을 만들어 두번째 for문을 돌면서, 오등수에서 했던 방식과 동일하게 구현한다. 단, 주의점은,

 

  for (int i = 0; n > i; i++)
  {
    while (!stack.empty() && frequency[nums[stack.top()]] < frequency[nums[i]])
    {
      nums[stack.top()] = nums[i];
      stack.pop();
    }
    stack.push(i);
  }

 

이전 오등수에서는 단순히  현재 값과 stack.top() (인덱스임에 주의) 인덱스의 값을 비교하면 됐었지만,

(즉, nums[stack.top( )] < nums[i] 였지만), 오등급수에서는 빈도 수가 크냐 작느냐를 비교하므로 frequency[nums[stack.top( )]] 와 frequency[nums[i]]를 비교해야 한다.

 

 

 

---

4. 검증 

 

총 for문 2번 + 남은 stack의 길이만큼 순회. 통과했다. vector와 pair을 사용한 이전 코드는 시간 초과로 통과하지 못했다ㅠ

 

 

---

5. 구현 

 

#include <iostream>
#include <stack>

using namespace std;

int main(void)
{
  int n, num, idx = 0;
  int frequency[1000001] = {0}, nums[1000001] = {0};
  stack<int> s;

  cin >> n;
  cin.ignore();

  for (int i = 0; n > i; i++)
  {
    cin >> num;
    frequency[num] += 1;
    nums[i] = num;
  }

  for (int i = 0; n > i; i++)
  {
    while (!s.empty() && frequency[nums[s.top()]] < frequency[nums[i]])
    {
      nums[s.top()] = nums[i];
      s.pop();
    }
    s.push(i);
  }

  while (!s.empty())
  {
    nums[s.top()] = -1;
    s.pop();
  }

  for (int i = 0; n > i; i++)
    cout << nums[i] << ' ';

  return 0;
}

 

 

---

 

6. 피드백 & 복기

 

  for (int i = 0; n > i; i++)
  {
    while (!stack.empty() && frequency[nums[stack.top()]] < frequency[nums[i]])
    {
      nums[stack.top()] = nums[i];
      stack.pop();
    }
    stack.push(i);
  }

 

코드 동작은 알지만, 이 부분에서 num[stack.top()] = nums[i] 할 때 몇번이나 헤맸었다. frequency, nums, stack 세 배열이 뒤죽박죽으로 들어가니 꽤나 혼란스러웠다.