Junnnho

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;
}

programmers 무지의 먹방 라이브 : programmers.co.kr/learn/courses/30/lessons/42891#qna

level3에 해당하는 문제였지만 저는 푸는데 되게 오래 걸린 문제입니다..

풀고나니 어렵지 않은 문제같은 느낌이 ㅠㅠ;

저는 정렬을 이용해서 문제를 해결했습니다.

새로운 벡터에 <음식의 양, 인덱스> 로 초기화하고

음식의 양을 기준으로 정렬을 합니다.

예시를 들어 설명하겠습니다.

[8,4,6], 15 일때

정렬을 하면 [4,6,8]가 됩니다.

가장 작은 값인 4라는 음식을 통해서 아래와 같은 값을 구할 수 있습니다.

(먹을 수 있는 음식의 갯수)*(현재 음식의 양 - 마지막으로 먹은 음식의 양)

이를 canK 라고 할 때, canK는 결국 순회가능한 횟수를 말합니다. 

처음에 4를 통해 canK는 3*(4-0) = 12라는 값을 얻을 수 있고, 

주어진 k는 15이기 때문에 순회가 가능하게 됩니다.

그 다음 작은 값 6에서 canK는 2*(6-4) = 4가 됩니다.

원래 k=16에서 정상적으로 다 먹어지는 음식인 6은 현재 k가 15이기 때문에 다 먹지 못하게 됩니다.

여기서 답을 구하기 위한 계산에 들어갑니다.

현재 먹을 수 있는 음식은 2개[8,6]

현재까지 순회한 횟수 cntk = 12

2개의 음식을 (15-12)=3번 먹는다 => 3%2 = 1

즉 1번째 음식까지는 먹을 수 있고 그 다음 음식이 무엇인지만 알면 됩니다.

주석을 통해 나머지 설명을 하겠습니다.

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

int solution(vector<int> food_times, long long k) {
    int answer = -1;
    
    // 정렬과 인덱스 값을 알기 위해 새로운 벡터를 만듬
    vector<pair<int, int> > food;
    for (int i = 0; i < food_times.size(); i++) {
        food.push_back({ food_times[i], i });
    }

    // 정렬해줌
    sort(food.begin(), food.end());

    // 순회한 횟수 cntK
    long long cntk = 0;
    // 마지막으로 먹은 음식인 lastFood
    int lastFood = 0;
    for (int f = 0; f < food.size(); f++) {
        // 당장 먹어야하는 음식의 양 => 음식의 양 - 마지막으로 먹은 음식의 양
        int eatFood = food[f].first - lastFood;
        // food의 인덱스
        int food_idx = food[f].second;
        
        // 순회할 수 있는 횟수 canK는
        // 현재 음식의 양에 남은 음식의 size를 곱한 것!
        long long cank = (food.size()-f) * eatFood;
        
        // k초 안으로 순회가 가능하다면
        if(cntk + cank <= k){
            cntk += cank;
            lastFood = food[f].first;
            food[f].first = 0;
            food_times[food_idx] = 0;
        }
        // 순회가 불가능하다면
        else{
            // temp는 최종적으로 순회할 음식에 대한 나머지 값
            int temp = (k - cntk) % (food.size() - f);
            // 나머지 값에 대한 카운트 변수 check
            int check = 0;
            for(int i = 0; i<food_times.size(); i++){
                // 없는 음식은 먹지 않아도 된다
                if(food_times[i] == 0) continue;
                // 나머지 값과 같다면 이 음식이 현재 먹어야하는 음식!
                if(check == temp){
                    answer = i;
                    return answer+1;
                }
                check++;
            }
        }
    }

    return answer;
}