Junnnho

programmers 호텔 방 배정 : programmers.co.kr/learn/courses/30/lessons/64063

2019 카카오 개발자 겨울 인턴십, level4의 호텔 방 배정 문제입니다.

처음에는 set을 이용해서 방이 비어있는지 확인하고 없으면 +1씩 체크하는 방식으로 코딩하였습니다.

결과는 역시 정확도만 만점이고 효율성에서 나락되었습니다.

이걸 어떻게 해야할지 오래 고민해보았는데, 

+1씩 확인해야 하는 탐색과정을 줄이는게 가장 중요할 것 같았습니다.

그래서 만약 현재 사람이 원하는 방이 비어있다면

'그 방에 배정시키고,

만약 이 방을 다른 사람이 또 원하게 된다면 현재방의 +1 방에 바로 배정시키자' 로 접근했습니다.

여기서 중요한 것은 현재방의 +1 방이 또 배정되어있는 상태인가? 입니다.

결국 현재 배정한 방의 그 다음방이 '어디까지 배정되어 있는지'를 알아야 합니다.

+1씩 탐색하는 것은 첫 코딩때 set을 이용한 것과 같지만, 이를 계산해서 미리 알아둔다면

그 다음에는 또 같은 방에 대해서는 +1씩 탐색할 필요가 없으니 탐색시간을 줄일 수 있습니다.

map을 통해서 <현재 배정한 방, 그 다음방의 연결된 마지막 방> 의 형식으로 문제를 해결하였습니다.

#include <string>
#include <vector>
#include <map>
using namespace std;
using ll = long long;

map<ll, ll> visit;

ll findNextRoom(ll room){
    if(visit[room] == 0) return room; // 배정되어 있지 않은 room 방에 배정시킬 수 있습니다
    visit[room] = findNextRoom(visit[room]); // room 방이 어디까지 연결되어 있는지 탐색하는 동시에 연결시킵니다
    return visit[room];
}

vector<long long> solution(long long k, vector<long long> room_number) {
    vector<long long> answer;
    
    for(auto room : room_number){
        if(visit[room] == 0){ // 배정되어있지 않다면
            answer.push_back(room); // 배정시키고
            visit[room] = findNextRoom(room+1); // +1 방이 어디까지 연결되어있는지 탐색합니다
        }
        else{ // 배정되어있다면
            ll nextRoom = findNextRoom(room+1); // +1 방이 어디까지 연결되어있는지 탐색합니다
            answer.push_back(nextRoom); // 찾아낸 방에 배정합니다
            visit[nextRoom] = findNextRoom(nextRoom+1); // 찾아낸 방의 +1 방이 어디까지 연결되어 있는지 탐색합니다
        }
    }
    
    return answer;
}

programmers 징검다리 건너기 : programmers.co.kr/learn/courses/30/lessons/64062

2019 카카오 개발자 겨울 인턴십 level3의 징검다리 건너기 문제입니다.

정확도와 효율성을 동시에 따지는 문제라는 것은 뭔가 알고리즘이 존재한다는 의미입니다.

정확성만 따지자면 2중 포문으로 k개에 대해서 모든 경우를 구하는 것인데,

징검다리의 수가 20만개에 원소의 값들은 2억이라서 효율성 점수를 얻는데는 실패할 것입니다.

저는 건널 수 있는 최대 값이 k라는 것에서 힌트를 얻어 이분탐색에 접근하였습니다.

현재 예시를 보겠습니다.

stones                                           k                                                 result

만약 친구 3명이 징검다리를 건넌다면? 

0 1 2 0 0 0 1 0 2 0 이라는 값이 됩니다.

0 0 0 이 3번 반복됩니다.

한번에 건너뛸 수 있는 k의 값이 3이라고 주어져 있습니다.

이는 인덱스2 부터는 3칸을 한번에 뛰어넘을 수 없다는 소리가 됩니다.

즉 => 3명까지는 징검다리를 건넜고, 4번째 친구부터는 징검다리를 못건넌다는 얘기입니다.

만약 친구 4명이 징검다리를 건넜다고 해도

3명이 건넜을 때 처럼

0 1 2 0 0 0.. 에서 0이 3번 반복되는 구간을 찾을 수 있습니다.

즉 0 이 k번 반복되는 구간이 있다는 것으로부터 저는 아래와 같은 생각을 하였습니다.

'현재 인원보다 많은 인원이 징검다리를 건널 수는 없다' 는 것이고

'현재 인원도 사실은! 징검다리를 건널 수 있는지 없는지는 모른다' 는 것이기 때문에 

'현재 인원이 일단 정답이라고 생각하고, 혹시 못 건널수도 있으니까 인원을 줄여보자!' 입니다.

코드는 아래와 같습니다.

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

bool checkCross(vector<int> stones, int k, int mid){
    
    int zero = 0;
    for(int i = 0; i<stones.size(); i++){
        int sub = stones[i] - mid;
        if(sub <= 0) zero++;
        else zero = 0;
        
        if(zero == k) return false;
    }
    
    return true;
}

int solution(vector<int> stones, int k) {
    
    int left = 1;
    int right = 200000000;
    int mid;
    while(left < right){
        mid = (left+right)/2;
        
        if(checkCross(stones, k, mid)){
            left = mid + 1;
        }
        else{
            right = mid; // 이 인원까지는 뛸 수 있을지 모른다. 줄여나가보자!
        }
    }
    
    return right;
}

programmers 불량 사용자 : programmers.co.kr/learn/courses/30/lessons/64064

2019 카카오 개발자 겨울 인턴십에 나온 불량 사용자 입니다.

dfs(backtraking)의 대표적인 문제입니다.

현재 어떤 userId가 banId될 수 있는지 유지하면서 dfs로 모든 userId를 banId와 비교하였습니다.

중요한 것은 답이 될 수 있는 banId가 모인 banList가 중복되면 안된다는 것입니다.

dfs를 인덱스 순으로 돌리기 때문에, banList에 push되는 userId는 '순서'가 유지될 것입니다.

이를 이용해서 banList의 사이즈가 ban 사이즈와 같아졌을 때 banList에 푸쉬된 스트링값들을 '따로 처리'해주면

쉽게 중복을 확인할 수 있습니다.

저는 '따로 처리'를 그냥 string 변수에 ' ' 간격으로 덧붙여서 문자열로 만든 후에

set을 이용해서 찾아낸 답이였는지 중복을 확인해주는 방법으로 문제를 해결하였습니다.

이는 현재 문제의 범위가 작아서 가능한 것이고

범위가 큰 문제에서는 스트링을 임의의 숫자같은 것으로 변경해주거나 등등의 방법으로 '따로 처리'를 할 수 있습니다.

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

vector<string> user;
vector<string> ban;
vector<string> banlist;
bool usingban[9];
int answer;
set<string> visit;

void dfs(int idx){
    if(banlist.size() == ban.size()){
        
        string visitid = "";
        for(auto i : banlist){
            visitid += i;
            visitid += ' ';
        }
        
        if(visit.find(visitid) == visit.end()){
            answer++;
            visit.insert(visitid);
        }
        
        return;
    }
    
    if(idx < user.size()){
        string user_id = user[idx];
        for(int i = 0; i<ban.size(); i++){
            if(usingban[i]) continue;
            string ban_id = ban[i];
            if(user_id.size() == ban_id.size()){
                bool checkban = true;
                for(int j = 0; j<ban_id.size(); j++){
                    if(ban_id[j] != '*' && (ban_id[j] != user_id[j])){
                        checkban = false;
                        break;
                    }
                }
                if(checkban){
                    usingban[i] = true;
                    banlist.push_back(user_id);
                    dfs(idx+1);
                    usingban[i] = false;
                    banlist.pop_back();
                }
            }
        }
        dfs(idx+1);
    }
}

int solution(vector<string> user_id, vector<string> banned_id) {
    
    user = user_id;
    ban = banned_id;
    
    dfs(0);
    
    return answer;
}

programmers 튜플 : programmers.co.kr/learn/courses/30/lessons/64065#qna

2019 카카오 개발자 겨울 인턴십에 출제된 튜플 문제입니다.

솔직히 문제를 어떻게 푸는건지 이해가 되지 않아서,, 접근 방법을 따로 검색해보았습니다.

주어진 문자열 내부의 집합을 원소의 갯수 기준으로 정렬한 후에,

각 집합의 원소에 접근하여 처음 나온 원소이면 기존 튜플의 순서가 되는 것입니다.

문제가 이해가 안되서 좀 당황스러운데,.. 왠지 이런 문제가 나오면 못풀것만 같은 느낌..

접근방법을 알고 코드만 작성해보았습니다.

파이썬같은 스플릿이나 문자열 처리하는 방법을 따로 공부하지 않아서

직접 원소의 갯수를 파악하고 정렬한 후 set을 이용하여 처리하였습니다.

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

vector<pair<string,int> > v;
set<int> visit;

bool cmp(pair<string,int>& a, pair<string,int>& b){
    return a.second < b.second;
}

vector<int> solution(string s) {
    vector<int> answer;
    
    for(int i = 2; i<s.size()-1; i++){
        string str = "";
        str += s[i];
        int cnt = 0;
        while(s[i+1] != '}'){
            str += s[++i];
            if(s[i] == ',') cnt++;
        }
        i += 3;
        v.push_back({str, cnt});
    }
    
    sort(v.begin(), v.end(), cmp);
    
    for(int i = 0; i<v.size(); i++){
        string str = v[i].first;
        for(int j = 0; j<str.size(); j++){
            int num = str[j]-'0';
            while(j+1<str.size() && str[j+1] != ','){
                num = num*10 + (str[++j]-'0');
            }
            j++;
            if(visit.find(num) == visit.end()){
                visit.insert(num);
                answer.push_back(num);
            }
        }
    }
    
    return answer;
}