22.05.15. 풀었던 문제들

1. 110 옮기기

어려워 보이는 문제였는데 해답은 간단하다.

1) 110을 제거하고, 110을 제거함으로써 생기는 모든 110도 제거한다.

2) 그렇게 남은 문자열에서 제일 뒤에 있는 0 바로 뒤에 모든 110을 넣는다.

이렇게 되는 이유는 '110'은 1보다는 앞에 와야 하고(1101보다 1110이 더 느리다) 0보다는 느리게 와야 한다(0110보다 1100이 더 느리다) 즉슨 모든 0보다 110이 뒤에 와야 한다는 말이다. 한편 110을 삽입함으로써 0의 위치는 삽입한 110의 0이 된다.

 

// 110 옮기기

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

using namespace std;

string solve(string s){
    int cnt= 0;
    for(int i = 0; i<s.length()-2; i++){
        if(s.length() < 3) break;
        if(s.length() >= i+3){
            string temp = s.substr(i, 3);
            if(temp == "110"){
                cnt++;
                s.replace(i, 3, "");
                i = max(-1, i-3);
            }
        }
    }
    int zero_idx = -1;
    for(zero_idx = s.length()-1; zero_idx >= 0; zero_idx--){
        if(s[zero_idx] == '0') break;
    }
    string target = "";
    while(cnt--) target += "110";
    s.insert(zero_idx+1, target);
    
    return s;
}

vector<string> solution(vector<string> s) {
    vector<string> answer;
    for(string& each_s : s){
        answer.push_back(solve(each_s));
    }
    return answer;
}

 

 

2. 풍선 터트리기

조건이 1백만이다. nlogn도 안되니까 DP이거나 규칙을 찾아야 한다고 생각했다. 이것도 머리 터지는 줄 알았는데.. 알고 보니 쉬운 조건이 있었다.

"어떤 풍선 기준, 양 옆(바로 옆이 아니라 끝까지)을 봤을 때 해당 풍선보다 작은 수가 양 옆에 있다면 해당 풍선은 남길 수 없다"이다.

이를 조금 설명해 보자면, 특이 규칙(단 1번만은 작은 풍선을 터트릴 수 있다)가 아니라면 i번째 풍선을 봤을 때 0~i-1의 풍선과 i+1~size-1번째 풍선 모두 i보다 값이 커야 한다. 그래야만 더 큰 값들을 사라지게 하면서 i번째 풍선이 남기 때문. 그러나 특이규칙 때문에 한 그룹의 풍선은 i보다 작아도 된다.(커도 되고, 작아도 된다는 말) 그러나 양쪽 그룹의 풍선 중 최솟값이 모두 i보다 작다면 안된다.

예를 들어보자. 편의상 0~i-1번째의 풍선을 L그룹, i+1~size-1번째 풍선을 R그룹이라 두겠다.

1) L그룹, R그룹 모두 i보다 값이 클 경우 -> 큰 값을 사라지게 하면서 i는 항상 남을 수 있다

2) L그룹의 최솟값 l, R그룹의 최솟값 r이 보드 i보다 작은 경우 -> i는 항상 남을 수 없다. 특이규칙을 사용하지 않을 경우 l과 r은 항상 남게 되는데, 그렇게 되면 l < i, r < i이므로 특이규칙을 쓰더라도 i는 항상 골라질 수 없다.

만약 특이규칙을 사용해서 한쪽 그룹에서 다른 값을 찾았다고 하자. 편의상 R그룹에서 특이규칙을 사용해서 다른 값 r'이 도출되었다고 하자. 그러면 l, i, r'을 비교하는데 만약 l과 i를 비교한다면 l<i이므로 항상 l이 골라져야 하므로 i는 남지 못한다. i과 r'을 비교한다면 i가 더 큰 경우, i는 사라지고, i가 더 작은 경우 i가 남지만 여전히 l<i이므로 i는 사라진다.

3) l < i < r 또는 r < i < l인 경우 -> 특이규칙을 사용하지 않고 L그룹에서 l, R그룹에서 r을 뽑을 수 있다. 그러면 여기서 l < i < r이면 r을 없애고 특이규칙을 사용해 l을 없애면 된다. 반대도 마찬가지.

​

정리하면, i번째 풍선을 봤을 때 L그룹의 최솟값, R그룹의 최솟값을 알아내야 한다는 게 이 문제의 요점이다.

// 풍선 터트리기

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

using namespace std;
int MAX = 1000000001;

int solution(vector<int> a) {
    int size = a.size();
    vector<int> l(size), r(size); 
    
    l[0] = MAX; // l[i] : i 왼쪽에 있는 값들의 최솟값
    for(int i = 1; i<size; i++){
        l[i] = min(a[i-1], l[i-1]);
    } 
    
    r[size-1] = MAX;  // r[i] : i 오른쪽에 있는 값들의 최솟값
    for(int i = size-2; i>=0; i--){
        r[i] = min(a[i+1], r[i+1]);
    }
    
    
    int cnt = 0;
    for(int i = 0; i<size; i++){
        //cout<<"l : "<<l[i]<<", r : "<<r[i]<<", c : "<<a[i]<<endl;
        if(l[i] < a[i] && r[i] < a[i]) continue;
        cnt++;
    }
    
    return cnt;
}

// i번째 index에 대해 왼쪽 그룹의 최솟값, 오른쪽 그룹의 최솟값을 알아내는 게 이 문제의 요점 O(n) 안에.

 

2. 입국심사

푸는 중이다. 이분탐색 내일은 진짜 정리해야징