코딩테스트 -- 풍선 터트리기 - (프로그래머스 / C++)

 

프로그래머스

문제!

---

 

일렬로 나열된 n개의 풍선이 있습니다. 모든 풍선에는 서로 다른 숫자가 써져 있습니다. 당신은 다음 과정을 반복하면서 풍선들을 단 1개만 남을 때까지 계속 터트리려고 합니다.

1. 임의의 인접한 두 풍선을 고른 뒤, 두 풍선 중 하나를 터트립니다.
2. 터진 풍선으로 인해 풍선들 사이에 빈 공간이 생겼다면, 빈 공간이 없도록 풍선들을 중앙으로 밀착시킵니다.

여기서 조건이 있습니다. 인접한 두 풍선 중에서 번호가 더 작은 풍선을 터트리는 행위는 최대 1번만 할 수 있습니다. 즉, 어떤 시점에서 인접한 두 풍선 중 번호가 더 작은 풍선을 터트렸다면, 그 이후에는 인접한 두 풍선을 고른 뒤 번호가 더 큰 풍선만을 터트릴 수 있습니다.

당신은 어떤 풍선이 최후까지 남을 수 있는지 알아보고 싶습니다. 위에 서술된 조건대로 풍선을 터트리다 보면, 어떤 풍선은 최후까지 남을 수도 있지만, 어떤 풍선은 무슨 수를 쓰더라도 마지막까지 남기는 것이 불가능할 수도 있습니다.

일렬로 나열된 풍선들의 번호가 담긴 배열 a가 주어집니다. 위에 서술된 규칙대로 풍선들을 1개만 남을 때까지 터트렸을 때 최후까지 남기는 것이 가능한 풍선들의 개수를 return 하도록 solution 함수를 완성해주세요.

 

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

---

요약하면 인접한 풍선을 계속하여 터트려 1개가 남을 때까지 반복하는 작업을 할 때

- 번호가 더 작은 풍선을 터트리는 행위는 최대 1번

- 나머지는 모두 큰수를 터트림

 

위의 2가지 조건을 지키며 마지막까지 남길 수 있는 번호 풍선의 개수를 구하는 문제!

 

 

여기서 집중해야 할 부분은

번호가 더 작은 풍선을 터트리는 행위는 최대 1번!

 

잘 생각 해보면 현재 숫자를 기준으로 양쪽에 작은 수가 있다면? 

 

 

1 1  9  1  1  에서 

 

9는 남길 수가 없다..!

 

한쪽만 처리할수있기에 양쪽 다 현 숫자보다 작은 수가 있으면 남길 수가 없다는 점을 이용해야 될 것 같네요

 

바로 시작!

 

먼저 숫자 기준으로 2계의 구역으로 나누어 최솟값을 관리해 줍시다.

int answer = a.size();
    
    int section1_min=a[0];
    int section2_min=987654321;
    
    for(int i=2;i<a.size();i++){
        section2_min=min(section2_min,a[i]);
    }

 

 

그다음 한 칸씩 이동하며 최솟값을 최신화해주는데

구역 1은 숫자 하나씩 추가해주며 비교하고

구역 2는 다음 숫자가 최솟값일 때 다시 한번 찾아주는 방법으로 진행!

for(int i=1;i<a.size()-1;i++){ // 1번째 숫자 기준부터 n-1까지
        if(a[i]>section1_min and a[i]>section2_min){
            answer-=1;
        }
        
        section1_min=min(section1_min,a[i]);
        
        if(a[i+1]==section2_min){
            section2_min=987654321;
            for(int j=i+2;j<a.size();j++){
                section2_min=min(section2_min,a[j]);
            }
        }
    }

 

끝!인 줄 알았는데...   11번부터 시간 초과 나네요 좀 더 줄여 봅시다!

 

 

 

 

 

여러 방법을 생각해본 끝에.... 모든 숫자에 대한 최솟값 배열들을 미리 생성하는 게 제일 빠르네요!

 

 

다시 시작!

 

모든 부분을 계산을 해주고 들어가 줍시다.

int section1_min[1000000]={0};
int section2_min[1000000]={0};


int solution(vector<int> a) {// 현재숫자 기준 양쪽에 현재숫자보다 작은 숫자가 있으면 미션실패
                                //양쪽끝은 무조건 가능
    int answer = a.size();
    
    
    section1_min[0]=a[0];//1구역
    for(int i=1; i<a.size()-1;i++){
        section1_min[i] = min(section1_min[i-1],a[i]); 
    }
    
    section2_min[a.size()-1]=a[a.size()-1];//2구역
    for(int i=a.size()-2;i>0;i--){
        section2_min[i] = min(section2_min[i+1],a[i]); 
    }

 

 

이렇게 간단해지네요;;

for(int i=1;i<a.size()-1;i++){ // 1번째 숫자 기준부터 n-1까지
        
        if(a[i]>section1_min[i] and a[i]>section2_min[i]){
            answer-=1;
        }

    }

 

 

 

 

ALL

#include <string>
#include <vector>

#include <algorithm>
#include <iostream>
using namespace std;

int section1_min[1000000]={0};
int section2_min[1000000]={0};

int solution(vector<int> a) {// 현재숫자 기준 양쪽에 현재숫자보다 작은 숫자가 있으면 미션실패
                                //양쪽끝은 무조건 가능
    int answer = a.size();
    
    
    section1_min[0]=a[0];//1구역
    for(int i=1; i<a.size()-1;i++){
        section1_min[i] = min(section1_min[i-1],a[i]); 
    }
    
    section2_min[a.size()-1]=a[a.size()-1];//2구역
    for(int i=a.size()-2;i>0;i--){
        section2_min[i] = min(section2_min[i+1],a[i]); 
    }
   
    for(int i=1;i<a.size()-1;i++){ // 1번째 숫자 기준부터 n-1까지
        if(a[i]>section1_min[i] and a[i]>section2_min[i]){
            answer-=1;
        }
    }
    
    return answer;
}

 

 

 

 

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