[Programmers - lv02] 탑 (cpp / python)

탑

코딩테스트 연습 - 탑

문제 설명

인덱스가 0인 경우에는 왼쪽에 더 이상 송전탑이 없으므로 answer에 0을 넣어주고 주어진 heights를 1부터 size까지 탐색한다.

해당 인덱스를 i라고 할 때 그 이전에 heights[i]보다 큰 높이를 찾으면 answer에 넣어주고 break를 건다.

heights[i]보다 큰 송전탑이 없으면 0을 넣어준다.

문제 풀이

소스코드 : C++

#include<iostream>
#include <vector>

using namespace std;

vector<int> solution(vector<int> heights) {
    vector<int> answer = {0};

    for(int i=1; i<heights.size(); i++){
        bool chk = false;
        for(int j = i-1; j>=0; j--){
            if( heights[j]> heights[i]){
                chk = true;
                answer.push_back(j+1);
                break;
            }
        }
        if(!chk)answer.push_back(0);
    }
    return answer;
}

예전 풀이

v라는 스택을 하나 만들어 뒤에서부터 탐색하였다.

#include<iostream>
#include<algorithm>
#include <string>
#include <vector>

using namespace std;

vector<int> solution(vector<int> heights) {
    vector<int> answer;
    vector<int> v = heights;    //  stack
    while (!v.empty()) {
        int cur = v.back();
        v.pop_back();
        int pos = v.size();
        bool chk = false;
        for (int i = pos - 1; i >= 0; i--) {
            if (heights[i] > cur) {
                answer.push_back(i + 1);
                chk = true;
                break;
            }
        }
        if (!chk)answer.push_back(0);
    }
    reverse(answer.begin(), answer.end());
    return answer;
}

소스코드 : Python

def solution(heights):
    answer =[0]
    for i in range(1,len(heights)):
        chk = False
        for j in range(len(heights[:i])-1,-1,-1):
            if(heights[j] > heights[i]):
                chk = True
                answer.append(j+1)
                break
        if chk==False : answer.append(0)
    return answer