17298 : 오큰수 - stack, 짝짓기

https://solved.ac/contribute/17298

로그인

 

문제요약

오큰수(해당 요소보다 오른쪽에 있으면서 큰 가장 왼쪽의 수 찾기)

 

난이도

Gold 4

---

풀이 포인트

• stack과 짝짓기
  • 현재 인덱스들과 오큰수를 짝지어 pop하는 아이디어를 떠올려야 함.

https://machineboy0.tistory.com/149

3986 : 좋은 단어 - 스택

스택 자료 구조를 이용한 쌍 Pop의 아이디어는 이 문제가 기본

 

---

REVIEW

 

첫 골드문제.

 

처음에 2중 for문을 돌렸다가 시간초과가 떠서 역시 간단한 문제가 아니구나 깨달아

그냥 모범답안을 찾아봤다.

 

2중 for문을 돌리면, 최대 크기 100만 * 100만 이므로 계산 횟수가 100억이 넘어버린다.

1000만 혹은 1억 정도의 크기까지 어림잡아 괜찮다고 보면 된다고 한다.

 

여튼 2중 for문과 스택을 이용한 짝짓기의 시간복잡도와 로직이 어떻게 다른지 분석해보자면

• 2중 for문 O(n^2)
  • 현재 요소 vs 현재요소의 인덱스 ++해가며 오큰수 나올 때까지 비교
  • 즉, 현재 인덱스 < 비교 인덱스들
• stack을 이용한 짝짓기 O(n)
  • 현재 요소가 이전 요소들의 비교 상대가 된다.
  • 즉, 과거 요소들 < 현재 요소 = 비교 인덱스
  • 오큰수가 나올 때까지 stack에 push해주고, 오큰수가 등장하면 쌓인 요소들 pop해주고 모두에 그 값을 할당해주는 방식

코드만 보면 참 간결하지만, 풀이 아이디어가 필요한 문제.

---

CODE

#include <bits/stdc++.h>
using namespace std;
int n, a[1000004], ret[1000004];
stack<int> s;

int main(){
    cin >> n;

    memset(ret, -1, sizeof(ret));

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

        while(s.size() && a[s.top()]<a[i]){
            ret[s.top()] = a[i];
            s.pop();
        }
        s.push(i);
    }

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