Even Idiots Can Make Game

백준 17298 G4 오큰수

Date/Lastmod
Section
PS
Title
백준 17298 G4 오큰수
Ps-Tags
Solved
03-05/25

#1 브루트 포스로?

수열의 길이 $N$이 $[1, 10^6]$ 범위이고, 시간 제한이 1초이다.

“오큰수” 라는 개념 자체는 단순해서, 처음에는 완전 탐색으로 배열을 순회하면서, 순회하는 요소의 오른쪽 범위부터 끝까지, 처음으로 발견된 그 요소보다 작은 요소를 직접 찾아보았다.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

vector<int> seq(N); // 주어진 수열
for (int &e: seq) cin >> e;
 
for (auto it = seq.cbegin(); it != seq.cend(); ++it) {
  // 무식하게 다음 요소부터 끝 요소 범위에서 오큰수를 찾아내기
  auto ocs_it = find_if(
    seq.cbegin() + 1, seq.cend(),
    [&it](int const &e) { return *it < e; }
  );

  if (ocs_it == seq.cend()) cout << -1;
  else                      cout << *ocs_it;
  cout << ' ';
}

이러면 사실상 요소별로 $N$만큼 순회하는 것이므로 복잡도는 $O(N^2)$이고, $N$의 범위를 고려했을 때 문제에서 주어진 시간 제한인 1초를 당연히 벗어난다.

#1 그럼 어떻게? - 스택 사용

예를 들어 수열 {3, 2, 7} 을 다음 처럼 순회한다고 생각하자.

  • 3이 순회 요소일 때, 아직 오큰수를 모른다. 3은, “오큰수를 모른다” 고 마킹해둔다.
  • 2가 순회 요소일 때:
    • 2는 3보다 작으므로, 가장 최근에 “오큰수를 모른다” 고 마킹해 둔 3의 오큰수는 2가 될 수 없다.
    • 2는 아직 오큰수를 모른다. 2를, “오큰수를 모른다” 고 마킹해둔다.
  • 7이 순회 요소일 때:
    • 7는 2보다 크므로:
      • 가장 최근에 “오큰수를 모른다” 고 마킹해 둔 2의 오큰수는 7이다.
      • 그 바로 이전에 “오큰수를 모른다” 고 마킹해 둔 3 또한 7보다 작으므로, 3의 오큰수도 7이다.
      • 이제 더이상 “오큰수를 모른다” 고 마킹해 둔 요소는 없다.
    • 7은 아직 오큰수를 모른다. 그런데 더이상 순회할 것이 없다.

그러면 {3, 2, 7} 오큰수 배열은 {7, 7, -1}이 된다.

로직을 보면, “오큰수를 모든다” 라는 정보를 저장해야 하는데, 이 정보를 저장하고 꺼내는 순이 반대 임을 알 수 있다. 가장 나중에 넣은 것이 가장 먼저 사용되는 후입선출(LIFO) 구조이다. 때문에 이 메모리는 스택으로 관리해야 한다.

이 방법을 사용하면 한 번의 순회로 모든 오큰수를 찾아낼 수 있지만, 순회하는 시점에 즉시 오큰수를 찾아내는 것이 아니므로 수열의 인덱스에 해당하는 오큰수를 저장하는 배열이 하나 더 필요하다. 이 배열은 처음에는 모두 오큰수를 발견하지 못한 상태이므로, -1로 초기화 해두면 된다.

#1 코드

코드는 아래와 같다.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

#include <iostream>
#include <vector>
#include <algorithm>
#include <stack>

#define NO_OCS -1

using namespace std;

int main() {
  int N; cin >> N; // N in [1, 10^6]
  vector<int> seq(N); // e in [1, 10^6]

  for (int &e: seq) cin >> e;
  vector<int> ocs(N, NO_OCS);

  stack<int> st; // 오큰수를 "아직 못 찾은" 수열 요소의 인덱스

  for (int i = 0; i < seq.size(); ++i) {

    // "오큰수를 모르는" 수를 최근 것부터 꺼내서 갱신
    while (!st.empty() && seq[st.top()] < seq[i]) {
      ocs[st.top()] = seq[i];
      st.pop();
    }

    st.push(i);
  }

  for (int const &e: ocs) cout << e << ' ';
}

#1 기타

#2 std::find 와 std::find_if

이름에 속지 말고 find 계열 함수는 모두 조건을 만족하는 요소가 첫 번째로 발견된 위치를 반환함. 1

std::find

std:find_if, std::find_if_not

#2 컨테이너가 비어 있을 때 멤버 접근

컨테이너가 비어 있을 때, 멤버 접근 메서드를 호출하는 경우에 대한 정리이다.

이런 기믹(?)들은 계속 써먹으면서 기억하는 수밖에 없다. 비어있는지 아닌지는 항상 조심하자.

시퀀스 컨테이너

스택, (우선순위)큐

연관 컨테이너

컨테이너가 비어있을 때, begin, end등을 사용하여도 완전 정상이나, begin을 역참조 하는 것은 정의되지 않은 행동.

  1. 왜 헷갈렸냐면, STL 함수 중에 std::find_first_of가 있거든. ↩︎

comments powered by Disqus