17298 - 오큰수

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

17298번: 오큰수

 

랭크 : 골드 4

 

---

 

1. 문제 이해

 

 

=> 크기가 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이다.

 

시간제한 : 1초

 

입력 : 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다.

-> N의 범위가 1000000이면, 이중 for문으로는 시간 안에 돌지 못하겠네.

 

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

 

 

 

---

 

2. 재정의 & 추상화

각 원소에서, 오른쪽 숫자 중 원소보다 큰 첫번째 숫자를 얘기하는 것이군!

 

입력이 9, 5, 4, 8이면,

1. 9보다 큰 첫번째 수: 없음 = -1

2. 5보다 큰 첫번째 수: 8

3. 4보다 큰 첫번째 수: 8

4. 8보다 큰 첫번째 수 : 없음 = -1

 

---

3. 설계

문제 해결 전략 5. 도식화 (그림 그리기)

 

 

 

stack과, 결과를 리턴할 result 배열을 하나 생성한다.

1번 차례에선, stack이 비었으니, 1을 stack에다 넣는다. result는 -1로 초기화해준다.

 

 

 

while문을 돌면서, 1번에 이어 2번 차례이다.

2번은 stack의 맨 위(바로 이전)과 비교하여, 1번 보다 크기가 작다면 stack에 넣는다.

result또한 -1로 초기화 해준다.

 

 

3번 차례다.

3번 또한 2번과 동일하다. stack의 제일 위 수(2번)보다 작기 때문에, 3번을 stack에다가 넣어준다. result는 -1이다.

 

 

 

4번을 보자. 4번은 stack의 제일 위 수(3번)보다 크다. 그러므로 stack에서 pop을 해 주고, result를 4번의 길이로 바꿔준다. 4번의 길이를 10이라 하면, result의 세번째 값은 10이 된다. 그리고 while을 돌면서, stack에 쌓인 숫자들과 4번의 길이를 계속 비교한다.

 

 

 

계속 진행하면

 

 

stack이 없거나 맨 위의 숫자가 4번보다 길면 while문을 빠져나온 후, stack에 4번을 놓고 result에다 -1(4번)을 넣어준다.

 

이하 반복이다.

 

---

4. 검증

내부적으로 while을 돌기는 하지만, 전체적으로 한 번의 순회로 계산할 수 있다. O(n * m)시간이 걸리긴 해도, 배열을 다 입력 받고 계산을 하는 것이 아닌, 입력과 동시에 계산할 수 있다. 즉, for문 한번에 작동하는 방식으로 구현 가능하다.(결과를 프린트할 시 for문 도는거 제외)

 

 

---

 

5. 구현

 

#include <iostream>
#include <vector>
#include <utility>

using namespace std;

int main(void)
{
  int n, num, idx = 0;
  cin >> n;
  cin.ignore();
  cin >> num;

  vector<pair<int, int>> stack = {make_pair(idx, num)};
  vector<int> result = {-1};

  n--;

  while (n-- > 0)
  {
    cin >> num;
    idx++;
    while (stack.size() > 0 && stack.back().second < num)
    {
      result[stack.back().first] = num;
      stack.pop_back();
    }

    stack.push_back(make_pair(idx, num));
    result.push_back(-1);
  }

  for (auto item : result)
    cout << item << ' ';
  return 0;
}

 

pair을 써서 인덱스를 같이 넣는 방식으로 구현했다.(난 pair가 사랑스럽다)

 

 

---

6. 회고 & 피드백

 

 

pair을 쓰지 않고, 인덱싱과 원본 배열을 수정하는 하는 방법이 있다.

Stack<Integer> stack;
int[] seq; // 원본 배열
 
for(int i = 0; i < seq.length; i++) {
	while(!stack.empty() && seq[stack.peek()] < seq[i]) {
		seq[stack.pop()] = seq[i];
	}
	stack.push(i);	
}
 
while(!stack.emtpy()) {
	seq[stack.pop()] = -1;
}

 

지금까지는 stack에는 값이 필수적으로 들어가야 한다고 생각을 했는데, 그럴 필요가 없고 인덱스를 넣으면 많은 것들을 할 수 있다는 것을 깨달았다. stack에 인덱스를 넣는 방식도 연습해야겠다.