프로그래머스 | 풍선 터트리기

코딩테스트 연습 - 풍선 터트리기

// https://school.programmers.co.kr/learn/courses/30/lessons/68646
#include <bits/stdc++.h>
#include <string>
#include <vector>

using namespace std;

int solution(vector<int> a) {
    list<int> lst;
    map<int, int> index;

    for (int i = 0; i < a.size(); i++) {
        lst.push_back(a[i]);
    }

    for (int i = 0; i < a.size(); i++) {
        index.insert(make_pair(a[i], i));
    }

    // sort 시켜 버리기
    sort(a.begin(), a.end());
    int value = a[0];
    int left = index[value];
    int right = left;

    list<int>::iterator itl = lst.begin();
    list<int>::iterator itr = lst.begin();
    advance(itl, left);
    advance(itr, right);

    // cout << "small one is " << *(it) << endl;

    for (int j = 1; j < a.size(); j++) {
        int i = index[a[j]];
        if (left < i && i < right) {
            continue;
        } else if (i < left) {
            // left erase
            list<int>::iterator it = itl;
            while (it != lst.begin() && *(it) != a[j]) {
                it--;
            }
            list<int>::iterator temp = it;
            temp++;
            lst.erase(temp, itl);
            itl = it;
            left = i;
        } else if (right < i) {
            // right erase
            list<int>::iterator it = itr;
            while (it != lst.end() && *(it) != a[j]) {
                it++;
            }
            list<int>::iterator temp = itr;
            temp++;
            lst.erase(temp, it);
            itr = it;
            right = i;
        } 
    }
    return (lst.size());
}

int main() {
    // vector<int> ex01 = {9, -1, -5};
    // solution(ex01);

    vector<int> ex02 = {-16, 27, 65, -2, 58, -92, -71, -68, -61, -33};
    cout << solution(ex02) << endl;


    return (0);
}

• 리스트를 사용해서 풀었는데...
• 다른방식으로 푼 것들도 많아서 봐야겠다.