[백준] 24523번 : 내 뒤에 나와 다른 수 (C++)

24523번 : 내 뒤에 나와 다른 수 

---

문제)

길이가 N인 수열 1 2 ⋯ A_1 , A_2 , ..., A_N이 주어진다. 1 ≤ i ≤ N인 정수 i마다 i < j  ≤ N이고 A_i ≠ A_j인 정수 j중 최솟값을 출력하라. 만약 이러한 j가 없다면 −1을 출력하라.

 

 

 

입력 :

첫째 줄에 수열 A의 크기 N이 주어진다. 둘째 줄에는 1 2 ⋯ A_1  A_2  A_N이 공백으로 구분되어 주어진다. 

(1≤ N ≤10^6, −10^9≤ A_i ≤10^9) 입력으로 주어지는 모든 수는 정수이다.

 

 

 

출력 :

각 i마다 조건을 만족하는 최솟값 j를 출력하라. 만약 이러한 j가 없다면 −1을 출력하라.

 

 

 

 

 

풀이)

// 24523. 내 뒤에 나와 다른 수
#include <iostream>
#include <vector>
#include <stack>
 
using namespace std;
 
int n;
vector<long long> vec;
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    cin >> n;
    vec.resize(n);
    for (long long& ele : vec) cin >> ele;
 
    
    long long cur = vec[n - 1];
    int prev = -1;
 
    stack<int> s;
 
    for (int i = n - 1; i > -1; i--)
    {
        if (vec[i] == cur)
        {
            s.push(prev);
        }
        else
        {
            s.push(i + 2);
            prev = i + 2;
            cur = vec[i];
        }
    }
 
    while (!s.empty())
    {
        cout << s.top() << " ";
        s.pop();
    }
 
    return 0;
}
 
 

---

출처 : https://www.acmicpc.net/problem/24523 

24523번: 내 뒤에 나와 다른 수