프로그래머스] C++ 풍선 터트리기(Level 3)

 

 

 

 

 

 

해당 문제는 프로그래머스에서 푸실 수 있습니다.

programmers.co.kr/learn/courses/30/lessons/68646

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

 

 

1. 문제

과자를 바구니 단위로 파는 가게가 있습니다.

이 가게는 1번부터 N번까지 차례로 번호가 붙은 바구니 N개가 일렬로 나열해 놨습니다.

철수는 두 아들에게 줄 과자를 사려합니다.

첫째 아들에게는 l번 바구니부터 m번 바구니까지,

둘째 아들에게는 m+1번 바구니부터 r번 바구니까지를 주려합니다.

단, 두 아들이 받을 과자 수는 같아야 합니다(1 <= l <= m, m+1 <= r <= N).

즉, A[i] 를 i번 바구니에 들어있는 과자 수라고 했을 때, A[l]+..+A[m] = A[m+1]+..+A[r] 를 만족해야 합니다.

각 바구니 안에 들은 과자 수가 차례로 들은 배열 cookie가 주어질 때,

조건에 맞게 과자를 살 경우 한 명의 아들에게 줄 수 있는 가장 많은 과자 수를

return 하는 solution 함수를 완성해주세요. (단, 조건에 맞게 과자를 구매할 수 없다면 0을 return 합니다)

 

제한사항

• a의 길이는 1 이상 1,000,000 이하입니다.
• a[i]는 i+1 번째 풍선에 써진 숫자를 의미합니다.
• a의 모든 수는 -1,000,000,000 이상 1,000,000,000 이하인 정수입니다.
• a의 모든 수는 서로 다릅니다.

 

 

 

입출력 예

a	result
[9,-1,-5]	3
[-16,27,65,-2,58,-92,-71,-68,-61,-33]	6

 

입출력 예 설명

 

입출력 예 #1

• 첫 번째 풍선(9가 써진 풍선)을 최후까지 남기는 방법은 다음과 같습니다.
  1. [9, -1, -5] 에서 -1, -5가 써진 풍선을 고른 뒤, -1이 써진 풍선(번호가 더 큰 것)을 터트립니다.
  2. [9, -5] 에서 9, -5가 써진 풍선을 고른 뒤, -5가 써진 풍선(번호가 더 작은 것)을 터트립니다.
• 두 번째 풍선(-1이 써진 풍선)을 최후까지 남기는 방법은 다음과 같습니다.
  1. [9, -1, -5] 에서 9, -1이 써진 풍선을 고른 뒤, 9가 써진 풍선(번호가 더 큰 것)을 터트립니다.
  2. [-1, -5] 에서 -1, -5가 써진 풍선을 고른 뒤, -5가 써진 풍선(번호가 더 작은 것)을 터트립니다.
• 세 번째 풍선(-5가 써진 풍선)을 최후까지 남기는 방법은 다음과 같습니다.
  1. [9, -1, -5] 에서 9, -1이 써진 풍선을 고른 뒤, 9가 써진 풍선(번호가 더 큰 것)을 터트립니다.
  2. [-1, -5] 에서 -1, -5가 써진 풍선을 고른 뒤, -1이 써진 풍선(번호가 더 큰 것)을 터트립니다.
• 3개의 풍선이 최후까지 남을 수 있으므로, 3을 return 해야 합니다.

입출력 예 #2

• 최후까지 남을 수 있는 풍선은 -16, -92, -71, -68, -61, -33이 써진 풍선으로 모두 6개입니다.

 

 

2. 풀이

풀이법은 아래 블로그에서 상세히 다루고 있으므로 보시면 좋을 것 같습니다.

 

yabmoons.tistory.com/576

[ 프로그래머스 [ 월간코드챌린지 ] 풍선 터트리기 ] (C++)

 

위 블로그에서 최소 인덱스 값과 최대 인덱스 값을 갱신하는 부분에 대해 보충설명을 하자면,

 

a 값을 기준으로 오름차순 정렬을 했을 때, 맨 앞 2개의 인덱스 값이 

가장 작은 숫자의 풍선이되고 두번째 인덱스 값이 두번째로 작은 풍선이 됩니다.

 

여기서 A < C < B라고 했을 때 C안에 들어오는 값을 제외시켜주면 되죠.

 

그럼 최소 인덱스 값과 최대 인덱스 값을 갱신하는 이유는, 

C에 해당되는 인덱스 값이 조건에 충족이 되면 C < A < B 또는 A < B < C 이런 형태로 들어가게 될텐데,

C 다음 값에 해당되는 4번째 값, 즉 D는 A, B, C값보다 커야합니다. C 값보다 작아도 B값이 더 작으면 상관 없죠.

단, 이렇게 되려면 A와 B범위 안에 있는 인덱스 값에 포함이 되어야 합니다.

때문에 조건에 만족한 경우에는 인덱스 값을 갱신해주면서 해당 인덱스 값이 범위에 포함 되는지 안되는지 판단하는 것입니다.

 

3. 코드

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

using namespace std;

struct Balloon{
    int num;
    int idx;
};

int solution(vector<int> a) {
    int answer = 0;
    vector<Balloon> v(a.size());

    for(int i = 0; i < a.size(); i++){
        v[i].idx = i;
        v[i].num = a[i];
    }

    sort(v.begin(), v.end(), [](auto a, auto b){
       return a.num < b.num; 
    });

    int fmin_idx = min(v[0].idx, v[1].idx);
    int tmin_idx = max(v[0].idx, v[1].idx);

    for(int i = 2; i < v.size(); i++){

        int current_idx = v[i].idx;
        if(fmin_idx < current_idx && current_idx < tmin_idx) continue;

        answer++;
        fmin_idx = min(fmin_idx, current_idx);
        tmin_idx = max(tmin_idx, current_idx);
    }
    return answer + 2;
}

 

 

다른 사람 풀이도 봤는데 기가막힌 코드가 하나 있어서 포함 합니다.

 

#include <string>
#include <vector>
#include <stack>
#include <iostream>

using namespace std;
int solution(vector<int> a) {
    int answer = a.size();
    stack<int> stack;
    for(int comp : a){
        while(!stack.empty() && comp < stack.top()){
            stack.pop();
            if(!stack.empty())
                answer--;
        }

        stack.push(comp);
    }
    return answer;
}