[알고리즘 스터디] 4주차 활동 기록

GDCS 알고리즘 스터디 4주차(05/01) 활동 기록입니다.
4주차에는 스택을 이용한 문제인 백준 17298번 오큰수 문제에 대한 풀이를 공유하였습니다.

 

문제

 

예제

//예제 입력
4
3 5 2 7

//예제 출력
5 7 7 -1

 

문제 정리

해당 숫자의 오른쪽에 위치한 수들 중 해당 숫자와 위치가 가까우면서 해당 숫자보다 큰 수 찾아야함.   

 

문제 접근

초기 접근 방법

• lower_bound 함수 활용
• 틀린 이유 : lower_bound 혹은 upper_bound 함수는 이분탐색이기 때문에 정렬을 한 후 사용해야하는데 오큰수는 원래 가지고 있는 수열에서 오른쪽에 위치한 숫자들이 대상이 되므로 (원래의 위치가 중요함) 정렬해서 해결 불가능
• 순차적으로 단순 탐색 
• 틀린 이유 : 수열 A의 크기 N (1 ≤ N ≤ 1,000,000), 시간제한 1초, 단순탐색시 시간복잡도 O(n^2) 이므로 이중 for문 사용하면 시간초과

새로운 접근 방법

• 수열을 선형으로 탐색해서 해결할 수 있는 방법이 필요함
• 해당 숫자보다 오른쪽에 위치한 숫자가 대상이므로 왼->오로 탐색하면 선형 시간복잡도로 해결이 어려움 👉 가장 오른쪽에 위치한 숫자부터 접근하기 (오->왼)
• 오->왼 이동하면서 해당 숫자의 오른쪽에 위치한 수 중 가까운 것(탐색에서 더 최근 것)이 우선순위를 가짐, LAST IN, FIRST OUT 필요 👉 오른쪽에 위치한 수 저장할 자료구조로 stack 활용
• 문제해결 방향은 오->왼인데 출력은 입력 순으로 해야함, LAST IN, FIRST OUT 필요 👉 결과 stack에 저장
• 수열의 가장 오른쪽부터 방문하면서 stack에 저장된 숫자들을 확인해서 방문한 숫자보다 작으면 pop함
• 오큰수 스택(오큰수 탐색 대상 스택)에 존재하는 원소가 방문한 숫자보다 작을때 pop해도 되는 이유 👉 방문한 숫자보다 오른쪽에 위치하면서 방문한 숫자보다 작다는 건 POP할 대상이 방문한 숫자 왼쪽에 있는 어떤 숫자의 NGE(오큰수)도 될 수 없기 때문 (방문한 숫자가 pop한 숫자들보다 크고 방문할 숫자들과 위치가 가까움)
•  방문한 숫자는 앞으로 방문할 숫자의 오른쪽에 위치하므로 오큰수 stack에 넣어줌 

3 5 2 7

7 방문 -> 오큰수 스택 empty -> 오큰수 존재 x -> NGE(7) = -1
[오큰수 스택](top) 7

2 방문 -> 오큰수 스택 top() 7 -> (2 < 7) -> NGE(2) = 7 
[오큰수 스택] (top) 2 7

5 방문 -> 오큰수 스택 top() 2 -> (5 > 2) -> pop 
       -> 오큰수 스택 top() 7 -> (5 < 7) -> NGE(5) = 7
[오큰수 스택] (top) 5 7

3 방문 -> 오큰수 스택 top() 5 -> (3 < 5) -> NGE(3) = 5
[오큰수 스택] (top) 3 5 7

결과 출력
5 7 7 -1

 

17298번 코드

#include <bits/stdc++.h>
using namespace std;

int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    
    int seqSize;
    cin >> seqSize;
    vector<int> tmp(seqSize);
    
    for(int i =0; i<seqSize; i++)
        cin >> tmp[i];
        
    stack<int> s;
    stack<int> result;
    
    for(int i = seqSize-1; i>=0; i--)
    {
        int num = tmp[i];
        if(s.empty()) result.push(-1);
        else
        {
            while(!s.empty() && s.top() <= num)
                s.pop();
            if(s.empty()) result.push(-1);
            else result.push(s.top());
        }
        s.push(num);
    }
    
    while(!result.empty())
    {    
        cout << result.top() << " ";
        result.pop();
    }
    
    
}

 

+) 17298 유사 문제 추천 : 백준 2493번 문제