Junnnho

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

programmers 경주로 건설 : programmers.co.kr/learn/courses/30/lessons/67259

2020 카카오 인턴십에서 출제된 경주로 건설입니다.

Level 3에 해당하며, 기법으로는 다익스트라 알고리즘에 살짝(?)의 방향까지 생각해주셔야 합니다.

방향을 일방적으로 고려하시면 틀립니다!

이 문제에서 다익스트라를 구현할 실력이 되신다면 대부분 테스트케이스 14번?이 틀리게 될 것입니다.

14번 테스트케이스를 대략적으로 만들어보면 아래와 같습니다.

{0, 0, 0, 0, 0}

{0, 1, 1, 1, 0}

{0, 0, 1, 0, 0}

{1, 0, 0, 0, 1}

{0, 1, 1, 0, 0}

0,0을 기점으로 오른쪽으로 출발했을 때는 board[3][3]에서 2300을,

0,0을 기점으로 아래쪽으로 출발했을 때는 board[3][3]에서 2100을 갖게 될 것입니다.

당장 [3][3]에서 출발했을 때 2300을 기준으로 [4][4]에 도달하면 3000이 되고

2100을 기준으로 도달하면 3300이 됩니다.

'코너'가 한번 더 발생하기 때문입니다.

만약 방향을 일방적으로 고려한 다익스트라를 구현한다면,

[3][3]에서 2300을 꺼냈을 떄

다익스트라로 갱신한 최솟값 배열을 min_dist라고 한다면

이미 min_dist[3][3] 은 2100이기 때문에 continue되면서 탐색하지 않게 되겠죠,,

이정도 설명이면 충분히 이해하셨을 거라 생각합니다.

즉, 다익스트라를 통해 '그 지점의 방향'에 대한 최솟값을 가지고 계셔야 합니다.

min_dist[y][x][방향] 이렇게 3차원배열로 해결가능합니다.

#include <string>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
struct pii {
    int dist, y, x, way;
};
struct piicmp {
    bool operator()(pii& A, pii& B) {
        return A.dist > B.dist;
    }
};

int my[4] = { -1,0,1,0 };
int mx[4] = { 0,1,0,-1 };
int arr[26][26][4];

int solution(vector<vector<int>> board) {
    int answer = 987654321;
    int bs = board.size();
    for (int i = 0; i < bs; i++) {
        for (int j = 0; j < bs; j++) {
            for(int k = 0; k<4; k++){
                arr[i][j][k] = 987654321;                
            }
        }
    }

    priority_queue<pii, vector<pii>, piicmp> pq;
    if (!board[0][1]) pq.push({ 0,0,0,1 });
    if (!board[1][0]) pq.push({ 0,0,0,2 });
    while (!pq.empty()) {
        int y = pq.top().y;
        int x = pq.top().x;
        int dist = pq.top().dist;
        int way = pq.top().way;
        pq.pop();

        if (arr[y][x][way] < dist) continue;
        if (y == bs - 1 && x == bs - 1) {
            answer = min(answer, dist);
        }

        for (int i = 0; i < 4; i++) {
            int yy = y + my[i];
            int xx = x + mx[i];
            if (yy >= 0 && yy < bs && xx >= 0 && xx < bs && board[yy][xx] != 1) {
                if (i == way) {
                    int distance = dist + 100;
                    if (distance < arr[yy][xx][i]) {
                        arr[yy][xx][i] = distance;
                        pq.push({ distance, yy, xx, way });
                    }
                }
                else if (i == (way + 1)%4 || i == (4 + way - 1)%4) {
                    int distance = dist + 600;
                    if (distance < arr[yy][xx][i]) {
                        arr[yy][xx][i] = distance;
                        pq.push({ distance, yy, xx, i });
                    }
                }
            }
        }
    }


    return answer;
}

programmers 보석 쇼핑 : programmers.co.kr/learn/courses/30/lessons/67258#

2020 카카오 인턴십에 나온 보석 쇼핑 문제입니다.

처음에는 아무생각없이 이분탐색으로 체킹할 범위를 주고 범위를 줄여나가는 식으로 코딩하였는데,

생각해보니 이 '범위'를 파악하는게 결국 순차탐색이여서 O(N^2)가 된다는걸 보고 방법을 바꿨습니다.

풀이과정

1. set 을 이용해서 보석의 종류를 파악합니다.

2. 2개의 인덱스변수(lp, rp)를 가지고 map을 사용해서 1번만 순차탐색을 합니다.

3. lp, rp를 통해서 *현재 범위의 보석 종류를 파악할 수 있습니다.

아래 코드에 보시면 gemCnt라는 변수가 있는데, 이게 lp~rp 사이의 보석의 종류입니다.

map[gems[index]] 가 만약 0이라면, gems[index]를 map에 넣어줄 때 gemCnt의 값을 증가시킵니다.

0이 아니라면, 이미 있는 보석이니 그냥 ++를 통하여 현재 범위내의 gems[index]보석의 '갯수'만 증가시킵니다.

4. 이 gemCnt의 값이 1번에서 파악한 보석의 종류와 같다면,

  4.1 lp, rp의 범위를 통하여 최솟값을 파악하고, 정답을 갱신합니다.

  4.2 lp인덱스의 보석을 map에서 제거합니다.

     map[gems[lp]]-- 를 했을 때 0이 된다면 보석의 종류인 gemCnt가 1 감소됩니다.

  4.3 lp는 +1 하여 값을 증가시켜 범위를 갱신합니다.

5. gemCnt의 값이 보석의 종류보다 작다면

  5.1 rp를 증가시킵니다.

  5.2 rp의 범위가 보석갯수를 넘어가면 더 파악할 수 없기 때문에 break 됩니다.

  5.3 rp 보석을 map에 추가시킬 때 gemCnt도 4번과 마찬가지로 계산해줍니다.

6. 반복합니다.

설명을 적고보니 '투포인터' 문제인 것 같습니다.

투포인터 문제는 풀어본 경험이 별로없어서 이 문제를 기점으로 필요성을 느낀 것 같습니다.

조만간 '투포인터'에 대한 문제를 백준을 통해서 풀어봐야할 것 같습니다.

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

set<string> gem;
map<string,int> getgem;

vector<int> solution(vector<string> gems) {
    vector<int> answer;
    for(auto i : gems) gem.insert(i);
    
    int gs = gem.size();
    
    int ans_lp, ans_rp, ans_min=987654321;
    int lp = 0, rp = 0;
    int gemCnt = 1;
    getgem[gems[0]]++;
    while(1){
        if(gemCnt == gs){
            if(rp-lp<ans_min){
                ans_min = rp-lp;
                ans_lp = lp;
                ans_rp = rp;
            }
            string lp_str = gems[lp];
            getgem[lp_str]--;
            if(getgem[lp_str] == 0) gemCnt--;
            lp++;
        }
        else{
            rp++;
            if(rp>=gems.size()) break;
            
            string rp_str = gems[rp];
            if(getgem[rp_str] == 0) gemCnt++;
            getgem[rp_str]++;
        }
    }
    
    answer.push_back(ans_lp+1);
    answer.push_back(ans_rp+1);
    
    return answer;
}