프로그래머스 - 뒤에 있는 큰 수 찾기(multiset, stack)

https://school.programmers.co.kr/learn/courses/30/lessons/154539

프로그래머스

multiset으로 풀었는데, 다른 풀이를 보니 stack으로 더 깔끔하게 풀 수 있다.

 

1. 특징

1) stack or multiset

 

2. 구현 방법 - multiset

• 배열의 첫번째 값을 multiset에 삽입한다
• 인덱스 1부터 n-1까지 순회하면서,
  • 현재 값이 multiset의 최솟값이 아니라면, multiset의 첫번째 원소의 가장 큰 뒤 큰수를 현재값으로 저장하고, 해당 원소를 제거한다
  • 이를 현재 값이 multiset의 첫번째 원소가 될때까지 반복한다
  • 최솟값이라면 multiset에 삽입한다
• 순회가 끝나고 multiset에 남아있는 원소들의 뒷 큰수를 -1로 저장한다

ex) [9, 5, 1, 2, 8, 6] 

• 배열의 첫번째 값을 multiset에 삽입: multiset(9)
• i == 1 (값 5). 현재값이 multiset의 최솟값이므로 삽입: multiset(5, 9)
• i == 2 (값 1). 현재값이 multiset의 최솟값이므로 삽입: multiset(1, 5, 9)
• i == 3 (값 2).
  • 현재값이 multiset의 최솟값이 아니므로 multiset의 첫번째 원소의 뒷 큰수를 현재 값으로 저장하고 multiset에서 해당 원소 제거 : arr[1] = 2, multiset(5, 9)
  • 현재값이 multiset의 최솟값이므로 삽입: multiset(2, 5, 9)

• i == 4 (값 8).
  • 현재값이 multiset의 최솟값이 아니므로 multiset의 첫번째 원소의 뒷 큰수를 현재 값으로 저장하고 multiset에서 해당 원소 제거 : arr[2] = 8, multiset(5, 9)
  • 현재값이 multiset의 최솟값이 아니므로 multiset의 첫번째 원소의 뒷 큰수를 현재 값으로 저장하고 multiset에서 해당 원소 제거 : arr[5] = 8, multiset(9)
  • 현재값이 multiset의 최솟값이므로 삽입: multiset(8, 9)
• i == 5 (값 6).
  • 현재값이 multiset의 최솟값이므로 삽입: multiset(6, 8, 9)
• 순회가 끝나고 multiset에 남아있는 원소들의 뒷 큰수를 -1로 저장
  • arr[6] = -1, arr[8] = -1, arr[9] = -1 

 

3. 코드 - multiset

#include <bits/stdc++.h>

using namespace std;

queue<int> arr[1000002];
multiset<int> s;
vector<int> solution(vector<int> numbers) {
    vector<int> answer;
    
    s.insert(numbers[0]); 
    for(int i = 1; i < numbers.size(); i++)
    {
        while(s.lower_bound(numbers[i]) != s.begin())
        {
            int mn = *s.begin();
            arr[mn].push(numbers[i]);
            s.erase(s.find(mn));
        }
        s.insert(numbers[i]);
    }
    
    for(auto itr = s.begin(); itr != s.end(); itr++)
    {
        arr[*itr].push(-1);
    }
    
    for(int i = 0; i < numbers.size(); i++)
    {
        int cur = arr[numbers[i]].front();
        arr[numbers[i]].pop();
        answer.push_back(cur);
    }
    
    return answer;
}

 

 

3. 코드 - stack (multiset을 stack으로 바꿔서 생각하면 된다)

#include <bits/stdc++.h>

using namespace std;

stack<int> s;
queue<int> arr[1000002];
vector<int> solution(vector<int> numbers) {
    vector<int> answer;
    
    s.push(numbers[0]);
    
    for(int i = 1; i < numbers.size(); i++)
    {
        int cur = numbers[i];
        while(!s.empty() && s.top() < cur)
        {
            arr[s.top()].push(cur);
            s.pop();
        }
        s.push(cur);
    }
    
    while(!s.empty())
    {

        arr[s.top()].push(-1);
        s.pop();
    }
    
    for(int i = 0; i < numbers.size(); i++)
    {
        answer.push_back(arr[numbers[i]].front());
        arr[numbers[i]].pop();
    }
    
    
    return answer;
}