코딩테스트 -- 뒤에 있는 큰 수 찾기 - (프로그래머스 / C++)

 

프로그래머스

문제!

---

정수로 이루어진 배열 numbers가 있습니다. 배열 의 각 원소들에 대해 자신보다 뒤에 있는 숫자 중에서 자신보다 크면서 가장 가까이 있는 수를 뒷 큰수라고 합니다.

정수 배열 numbers가 매개변수로 주어질 때, 모든 원소에 대한 뒷 큰수들을 차례로 담은 배열을 return 하도록 solution 함수를 완성해주세요. 단, 뒷 큰수가 존재하지 않는 원소는 -1을 담습니다.

 

---

문제에서 배열을 제시해주면 현재수보다 큰 뒷수의 인덱스를 출력해주는 문제였습니다!

 

문제는 실행시간이네요... numbers의 길이가 100만... 일반적인 탐색으로는 불가능할것같네요

 

 

조금 생각을 해봅시다

저는 한 숫자를 받아 앞의 숫자와 비교해주는 방법을 간단하게 만들어 보기로 했습니다!

 

[9 1 5 3 6 2]를 받아올때 앞에서부터 생각해보면

 

9는 변동없음, 1도  9보다 작으므로 변동없음

5는 [9 x 5 3 6 2]  1을 삭제가능 9와 비교해야함

3은 5보다 작으므로 변동없음

6은 [9 x 5 x 6 2] 3보다 크고 / [9 x x x 6 2] 5보다 크므로 삭제해주고 9와 비교까지

2는 6보다 작으므로 변동없음...

 

여기까지가 예제 리스트를 풀어보았는데 이 부분에서 알수있는점이 있었습니다.

1. 바로 전 숫자보다 작으면 비교를 멈춰도된다

2. 전 숫자보다 크면 계속 비교를 이어줘야한다

 

저는 이 2가지를 이용해서 문제를 풀어보았습니다!

 

 

 

int use[1000001]={0,};

vector<int> answer(numbers.size(), -1);

int pre_ind=1;

먼저 사용된 숫자라는것을 확인해줄 use리스트와 

answer 리스트를 -1로 초기화 / pre_ind(전 숫자 인덱스)

설정후

 

 

다음 for문을 실행 해 보았습니다.

 for(int i=1;i<numbers.size();i++){ // 전꺼랑 비교하면서 기준을 잡아 이동
        pre_ind=i-1;
        while(pre_ind+1){
            if(use[pre_ind]==0){ //사용 안된거
                if(numbers[i]>numbers[pre_ind]){
                    answer[pre_ind]=numbers[i];
                    use[pre_ind]=1;
                    pre_ind-=1;
                }
                else{
                    break;
                }
            }
            else{ // 된거는 뛰어넘고
                pre_ind-=1;
            }
        }

사용 안된 것들을 비교해주면서 위의 1,2번 규칙을 사용하여 불필요한 반복을 제거해주었습니다.

 

 

성공!

 

 

 

하고 다른 사람들의 풀이를 보니 stack으로 풀어놓은 분들이 많이 계시네요....

 

Stack으로 푼 방법과 풀이 시간은 그렇게 차이 나지 않지만 코드를 보면 

for(int i=0; i<numbers.size(); i++) {
        while(!stk.empty() && numbers[stk.top()] < numbers[i]) {
            answer[stk.top()] = numbers[i];
            stk.pop();
        }
        stk.push(i);
    }

스택에 계속 인덱스를 넣어주며 비교하고, 꺼내주는 작업을 반복하네요

 

저는 사용되었음을 use 배열로 해결한 케이스고 이부분을 제외하고 해결하려고

stack으로 제거해주면서 해결한 그런 방법인 것 같습니다!

 

 

ALL

#include <string>
#include <vector>
#include <iostream>
using namespace std;

int use[1000001]={0,};

vector<int> solution(vector<int> numbers) {
   vector<int> answer(numbers.size(), -1);
    
    int pre_ind=1;
    
    for(int i=1;i<numbers.size();i++){ // 전꺼랑 비교하면서 기준을 잡아 이동
        pre_ind=i-1;
        while(pre_ind+1){
            if(use[pre_ind]==0){ //사용 안된거
                if(numbers[i]>numbers[pre_ind]){
                    answer[pre_ind]=numbers[i];
                    use[pre_ind]=1;
                    pre_ind-=1;
                }
                else{
                    break;
                }
            }
            else{ // 된거는 뛰어넘고
                pre_ind-=1;
            }
        }
        
        

    }
    
    return answer;
}

 

 

 

 

틀린점이 있다면 댓 달아주세요!