[백준] 17298번 오큰수 c++

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

17298번: 오큰수

 

오큰수

문제

크기가 N인 수열 A = A1, A2, ..., AN이 있다. 수열의 각 원소 Ai에 대해서 오큰수 NGE(i)를 구하려고 한다. Ai의 오큰수는 오른쪽에 있으면서 Ai보다 큰 수 중에서 가장 왼쪽에 있는 수를 의미한다. 그러한 수가 없는 경우에 오큰수는 -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개의 수 NGE(1), NGE(2), ..., NGE(N)을 공백으로 구분해 출력한다.

 

---

문제접근

가장 먼저 떠오른 접근법은 단순히 O(n^2)의 복잡도로 이중 for문을 이용하는 방법이였다.

하지만 n이 최대 백만의 값을 가지므로 너무 오래걸린다.

그럼에도 최적화할 방법이 생각이 나지 않아 일단구현을 해보았다.

 

알고리즘

1. 일일이 하나 하나 접근하여 반복문을 돌면서 오큰수를 찾는다.

2. 찾을 경우 오큰수를 result배열 해당 인덱스에 저장한다.

3. 못찾을 경우(i 가 n에 도달)  -1을 result배열 해당 인덱스에 저장한다.

 

#include <iostream>

using namespace std;

int main(){
  int n; cin >> n;
  int input[1000000]={0,}, result[1000000]={0,};

  for(int i=0; i<n; i++){
    cin >> input[i];
  }

  for(int i=0; i<n; i++){
    for(int j=i+1; j<=n; j++){
      if(input[j] > input[i]){
        result[i] = input[j];
        break;
      }
      if(j==n) result[i]=-1;
    }
  }

  for(int i=0; i<n; i++){
    cout << result[i] << " ";
  }

}

 

 

 

최적화할 방법이 아무리 생각이 나지 않아 구글링을 하며 스택을 이용해 최적화 할 수 있다는 사실을 알게 되었다.

스택대신 벡터를 활용해서 문제를 풀었다.

 

알고리즘

O(n)의 복잡도를 가진다. 편의상 벡터를 스택이라 칭하겠다.

1. 다음 자리의 수가 현재자리의 오큰수에 해당하지 않으면 스택에 넣는다. -> 다음 원소로 이동

2. 다음 자리의 수가 현재자리의 오큰수에 해당하면 result에 오큰수를 저장하고 , 스택의 원소를 꺼내면서 오큰수에 해당하면 그 원소 인덱스에 해당하는 자리를 찾아 result배열에 오큰수로 입력한다. -> 다음원소로 이동

이때 스택에는 항상 내림차순으로 원소들이 쌓이게 된다! 스택에 있는 원소가 찾은 오큰수 보다 크면 오큰수를 찾게 된것이기 때문이다.

3. 배열의 끝에 도달하게 되면 남은 스택에 원소들은 오큰수를 갖지 않는 원소들이므로 해당 인덱스를 꺼면서 모두 해당 result배열 자리에 -1로 채워준다.

 

 

#include <iostream>
#include <vector>

using namespace std;

int main(){
  int n; cin >> n;
  vector<int> value,index;

  int input[1000001]={0,}, result[1000001]={0,};
  for(int i=0; i<n; i++){
    cin >> input[i];
  }

  for(int i=0; i<=n; i++){
    if(n==i){
      while(!value.empty()){
        result[index.back()] = -1;
        index.pop_back();
        value.pop_back();
      }
    }

    if(input[i] >= input[i+1]){
      value.push_back(input[i]);
      index.push_back(i);
    }else if(input[i] < input[i+1]){
      result[i]=input[i+1];
      while(!value.empty() && value.back()  < input[i+1]){
        value.pop_back();
        result[index.back()] = input[i+1];
        index.pop_back();
      }
    }
  }

  for(int i=0; i<n; i++){
    cout << result[i] << " ";
  }

}

 

느낀점 / 적용

- 두 코드의 풀이 방법에 대한 큰 차이는 없는 것 같은데 왜 첫번째 코드는 반례가 존재하는지 모르겠다.

- 자료구조를 알고리즘 문제 풀때 사용한 경우는 거의 없었다. 이번 문제를 통해 자료구조(스택)를 활용해 효율적으로 해결할 수 있다는 것을 느끼게 되었다.