[BOJ/백준] 17298 오큰수

● [문제번호 17298] 오큰수

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

17298번: 오큰수

 

● 알아야 할 것

: stack, vector 자료구조와 메소드

 

● 풀이 과정

: vector로 구현해도 시간 초과라 시간 단축할 방법을 고민하였다.

: 문제 페이지 내에 '알고리즘 분류'에서 '스택' 이란 걸 보고 더 고민했지만 끝내 구글링을 하였다.

: 입력된 vector v 의 index 값을 stack 에 저장하여 NGE 함수의 while문에서 활용한다.

: 구글링에는 vector v의 배열을 뒤에서 앞으로 순회하며 result를 만드는 글도 있었지만 나는 앞에서 뒤로 순회 하였다.

: 글로 읽어보면 머리 속으로 시뮬레이션을 돌리기 어려워서 직접 그렸더니 확실히 이해되었다.

: 수열의 내리막 부분은 stack에 쌓이고 오르막 부분이 나타날 때 마다 result에 입력하게 된다.

 

 

 

● 주의 할 것

: vector만을 이용하여 만든 O(N^2)의 시간복잡도는 '시간 초과' 라는 결과를 가져온다.

: stack을 이용하여 O(N)의 시간복잡도로 만들어야 한다.

 

● 참고 할 것

: (참고한 링크) https://it-and-life.tistory.com/252

 

● 풀이 코드

#include <bits/stdc++.h>

using namespace std;

// 자신보다 큰 수를 구하기 위한 stack
// 값이 아닌 vector의 index를 저장
stack<int> s;
// 입력 저장을 위한 v / 결과 저장을 위한 result
vector<int> v, result;
int N;

// 오큰수를 구하기 위한 작업
void NGE(int index)
{
    // 헷갈릴 수 있는 부분 ★
    // stack의 값은 vector의 index이다
    // 반복문 조건 : stack에 비어 있으면 안됨 && v[stack에 있는 index] < v[현재 index]
    // 만족 시 : v[stack에 있는 index] 의 오큰수 = v[현재 index]
    while(!s.empty() && v[s.top()] < v[index])
    {
        result[s.top()] = v[index];
        s.pop();
    }
    
    // 현재 index 쌓기
    s.push(index);
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    cin >> N;
    
    v.assign(N, 0);
    // 결과값 vector의 초깃값을 -1로 한다.
    result.assign(N, -1);
    
    // 입력
    for(int n = 0; n < N; n++)
        cin >> v[n];
    
    // 오큰수 함수 호출
    for(int n = 0; n < N; n++)
        NGE(n);
    
    // 결과값 vector 전체 출력
    for(int n = 0; n < N; n++)
        cout << result[n] << " ";
    
    return 0;
}

 

 

● [백준] - [알고리즘 기초 1/2] - [201 - 자료구조 1 (연습)] 문제집

번호	문제 번호	문제 이름	풀이 링크
1	17413	단어 뒤집기 2	https://pirateturtle.tistory.com/165
2	10799	쇠막대기	https://pirateturtle.tistory.com/166
3	17298	오큰수	https://pirateturtle.tistory.com/167
4	17299	오등큰수	https://pirateturtle.tistory.com/168