Junnnho

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

이분탐색 l4 문제인 징검다리 입니다.

이분탐색에 해당하는 문제를 풀 때는

이분탐색의 구간에 해당하는 것이 무엇인지, 이를 판단하는 조건은 무엇인지 파악하는 것이 중요합니다.

문제에서 주어졌듯이 이분탐색의 '구간'에 해당하는 것, 즉 원하는 값은

각 돌 사이의 간격이며 이 간격들 중의 최솟값을 최대로 하는 것입니다.

이를 판단하는 조건은 n개의 돌을 제거하는 것!

여기서 아래와 같이 생각해볼 수 있습니다.

나열된 여러 개의 돌 중에서 n개를 제거하면서 돌 사이 간격의 최솟값을 최대로 하고 싶다

=> n개의 돌을 제거한 이분탐색의 결과값인 '간격'을 알고 싶다

=> 임의의 '간격'을 기준으로 돌을 제거할 수 있을까

=> 임의의 '간격'보다 작은 '간격'에 해당하는 돌을 제거하면서 몆개를 제거할 수 있는지 확인한다

==> 만약 제거한 돌의 갯수가 n개보다 작다면?

===> 이것은 괜찮다. 일단 모든 돌의 간격을 '간격' 이상으로 유지했다는 뜻이니까

         n개가 될 수 있게 더 제거해도 된다는 의미가 된다.

==> 만약 제거한 돌의 갯수가 n개보다 크다면?

====> 이것은 안된다. 모든 돌의 간격을 원하는 '간격' 기준만큼 유지할 수 없다는 뜻이니까

=> 제거한 돌의 갯수가 n개이하라면 모든 돌의 간격은 원하는 기준값인 '간격' 보다 크거나 같아진다.

=> 최솟값의 최댓값을 찾기 위해 제거한 돌의 갯수가 n개 이하라면 기준값을 늘려보고

=> 제거한 돌의 갯수가 n개를 초과한다면 기준값을 줄여본다.

#include <string>
#include <vector>
#include <algorithm>
using namespace std;

bool canDelete(vector<int> v, int mid, int n){
    int deleteRock = 0;
    int leftIdx = 0;
    int rightIdx = 1;
    while(rightIdx < v.size()){
        if(deleteRock > n) break;
        int dist = v[rightIdx] - v[leftIdx];
        if(dist < mid){
            deleteRock++;
            rightIdx++;
        }
        else{
            leftIdx = rightIdx++;
        }
    }
    
    if(deleteRock <= n) return true;
    else return false;
}

int solution(int distance, vector<int> rocks, int n) {
    rocks.push_back(0);
    rocks.push_back(distance);
    sort(rocks.begin(), rocks.end());
    
    int left = 1, right = 1000000000, mid;
    int answer = left;
    
    while(left<=right){
        mid = (left+right)/2;
        if(canDelete(rocks, mid, n)) {
            left = mid+1;
            answer = max(answer, mid);
        }else right = mid-1;
    }
    
    return answer;
}

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

level3 입국심사 문제입니다.

이분탐색을 이용하는 대표적인 문제라길래 풀어봤습니다.

이분탐색은 기본적으로 어떤 값을 기준으로 이분탐색을 할 것인지 파악하는게 중요합니다.

그걸 찾기가 정말 어려운데,

이번 문제는 애초에 '시간의 최솟값을 반환' 이라는 말에서 시간을 기준으로 이분탐색을 진행하라는게 주어져있습니다.

이분탐색의 조건을 찾았으면, 이 탐색간의 범위를 지정하는 기준이 무엇인지 파악해야하는데,

이 문제에서는 '현재 시간'으로 모든 사람들을 심사할 수 있는지 파악해야 합니다.

간단하게, 모든 심사위원의 심사시간을 '현재 시간'으로 나누어서 심사할 수 있는 모든 사람을 찾은 후에,

주어진 n과 비교해서 탐색을 진행해주시면 됩니다.

이분탐색 연습하기에는 좋은 문제인 것 같습니다.

#include <string>
#include <vector>

using namespace std;
using ll = long long;

long long solution(int n, vector<int> times) {
    long long answer = 0;
    long long s = 1;
    long long e = (ll)100000000*n;
    long long m;
    while(s<=e){
        m = (s+e)/2;
        ll person = 0;
        for(auto time : times) person += m/time;
        
        if(person >= n) e = m-1, answer = m;
        else s = m+1;
    }
    
    return answer;
}

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

2018 카카오 블라인드에서 출제된 다트 게임입니다.

문제에서 요구하는대로 '구현'할 수 있는지 묻는 문제였습니다.

요구하는 그대로 따라가주시면 됩니다.

#include <string>
#include <vector>
#include <cmath>
using namespace std;

int solution(string str) {
    vector<int> v;
    int answer = 0;
    
    for(int i = 0; i<str.size(); i+=2){
        int num = str[i]-'0';
        if (str[i + 1] == '0') {
            num = 10; i++;
        }
        char ch = str[i+1];
        int p = ch == 'S' ? 1 : (ch == 'D' ? 2 : 3);
        num = pow(num, p);
        
        if(i+2 < str.size() && (str[i+2] == '*' || str[i+2] == '#')){
            if(str[i+2] == '*') {
                num *= 2;
                if(v.size()>0) v[v.size()-1] *= 2;
            }
            else if(str[i+2] == '#'){
                num *= -1;
            }
            i++;
        }
        v.push_back(num);
    }
    
    for(int i = 0; i<v.size(); i++) answer += v[i];
    
    return answer;
}

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

2018 카카오 블라인드 리쿠르먼트에서 출제된 level2 뉴스 클러스터링 입니다.

문제에서 요구하는대로 '구현'할 수 있는지 묻는 문제였습니다.

범위가 작긴 하지만 마구잡이로 순차검색하는 것 보다는

평소 익숙해지기 위해 이분탐색을 사용하여 문자열을 검색하였습니다.

순차로 검색하셔도 효율성을 따지지 않기 때문에 문제되지는 않을 것 같습니다.

교집합, 합집합을 만들 때에는 set을 사용해서 이미 탐색한 단어인지 확인했습니다.

#include <string>
#include <vector>
#include <algorithm>
#include <set>
using namespace std;

int lowerbound(vector<string> v, string str){
    int s = 0, e = v.size();
    int m;
    while(s<e){
        m = (s+e)/2;
        if(v[m] >= str) e = m;
        else s = m+1;
    }
    return e;
}

int upperbound(vector<string> v, string str){
    int s = 0, e = v.size();
    int m;
    while(s<e){
        m = (s+e)/2;
        if(v[m]>str) e = m;
        else s = m+1;
    }
    return e;
}

vector<string> getString(string str){
    vector<string> res;
    string temp;
    for(int i = 0; i<str.size()-1; i++){
        char ch1 = str[i];
        char ch2 = str[i+1];
        if(!((ch1>='a'&&ch1<='z')||(ch1>='A'&&ch1<='Z'))) continue;
        if(!((ch2>='a'&&ch2<='z')||(ch2>='A'&&ch2<='Z'))) continue;
        ch1 = tolower(ch1);
        ch2 = tolower(ch2);
        temp = ""; temp += ch1; temp += ch2;
        res.push_back(temp);
    }
    return res;
}

int solution(string str1, string str2) {
    
    vector<string> f = getString(str1);
    vector<string> s = getString(str2);
    
    if(f.size() == 0 && s.size() == 0) return 65536;
    
    // make union, difference
    
    sort(f.begin(), f.end());
    sort(s.begin(), s.end());
    int uni = 0;
    int diff = 0;
    set<string> visit;
    
    for(int i = 0; i<f.size(); i++){
        if(visit.find(f[i]) == visit.end()){
            visit.insert(f[i]);
            int fleft = lowerbound(f, f[i]);
            int fright = upperbound(f, f[i]);
            int sleft = lowerbound(s, f[i]);
            int sright = upperbound(s, f[i]);
            if(sright == sleft){ // difference
                diff += fright-fleft;
            }
            else{ // union & difference
                int uniSize = min(fright-fleft, sright-sleft);
                int diffSize = max(fright-fleft, sright-sleft);
                uni += uniSize;
                diff += diffSize;
            }
        }
    }
    
    for(int i = 0; i<s.size(); i++){
        if(visit.find(s[i]) == visit.end()){
            visit.insert(s[i]);
            int fleft = lowerbound(f, s[i]);
            int fright = upperbound(f, s[i]);
            int sleft = lowerbound(s, s[i]);
            int sright = upperbound(s, s[i]);
            if(fright == fleft){ // difference
                diff += sright-sleft;
            }
            else{ // union & difference
                int uniSize = min(fright-fleft, sright-sleft);
                int diffSize = max(fright-fleft, sright-sleft);
                uni += uniSize;
                diff += diffSize;
            }
        }
    }
    
    int answer = ((double)uni/diff)*65536;
    
    return answer;
}