프로그래머스 42588 - 탑 (c++)

프로그래머스 42588 - 탑

문제 링크

생각과 접근

• 문제의 분야는 스택/큐에 있었지만, 굳이 사용하지 않고 for문 두 개를 쓰면 간단히 풀 수 있는 문제였습니다.
• 신호는 오른쪽에서 왼쪽으로 흐르니 heights를 탐색할 때 거꾸로 탐색합니다. (i-for문)
• 두 번째 j-for문에서 i보다 제일 가깝고 heights[i]보다 큰 값을 찾습니다.
  • 큰 값이 있다면, 그 타워의 인덱스를 push_back
  • 큰 값이 없다면, 0을 push_back
• 탐색은 거꾸로 하여 값 또한 거꾸로 push_back되어 있으므로, vector answer에 다시 거꾸로 넣어줍니다.

코드

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

vector<int> solution(vector<int> heights) {
    vector<int> answer;
    vector<int> temp;

    for(int i = heights.size() - 1; i >= 0; i--) {
        for(int j = i - 1; j >= 0; j--) {
            if(heights[j] > heights[i]){
                temp.push_back(j + 1);
                break;
            }
            if(j == 0) temp.push_back(0);
        }
        if(i == 0) temp.push_back(0);
    }

    for(int i = temp.size() - 1; i >= 0; i--){
        answer.push_back(temp[i]);
    }
    return answer;
}

채점 결과