🧁2019 카카오 개발자 겨울 인턴십 코딩 테스트 리뷰 - (2)

https://programmers.co.kr/learn/challenges?tab=all_challenges

프로그래머스

https://tech.kakao.com/2020/04/01/2019-internship-test/

2019 카카오 개발자 겨울 인턴십 코딩 테스트 문제 해설

---

 

2020년 3월 28일에 카카오 인턴십 코딩 테스트 실전 모의고사라는 제목으로 프로그래머스에서 모의고사가 열렸는데, 카카오 테크 블로그를 들어가 보니 이는 2019년 11월에 시행된 2019년 카카오 개발자 겨울 인턴십 채용과정에서 실제 진행되었던 코딩 테스트라고 하더라고요. 풀린 지 얼마 안 된 따끈따끈한 문제들 한번 살펴보겠습니다. 문제는 총 5문제이고 실제 코딩 테스트 시간은 4시간이었다고 하는데, 평소 꾸준히 알고리즘 문제를 푸신 분들에게는 충분한 시간입니다. 빡구현이라 불리는 삼성역 테류의 문제도 아니라 4시간 중의 절반 정도는 알고리즘을 생각을 하는데 썼어야 했을 것입니다.  본격적인 풀이에 앞서, 스포일러를 보지 않고 푸실 분은 여기서 멈추고 문제를 먼저 보시길 바랍니다. 또한 카카오 테크 블로그에 카카오 쪽에서 출제의도 등의 풀이 방법을 설명해두었으니 카카오 인턴십에 관심이 있으신 분들은 꼭 읽어 보시길 바랍니다.

 

+)코딩 테스트 문제에 대해 검색을 하니 저작권으로 문제가 될 가능성이 있어 보입니다. 해당 글은 프로그래머스 사이트에 정식으로 모두에게 배포된 문제들에 대한 풀이글이고 비영리 목적으로 코딩 테스트를 준비하시는 분들께 조그마한 도움이 되고자 작성한 글입니다. 하지만 문제가 될 시 비공개 처리 또는 수정하도록 하겠습니다. 

 

---

4. 호텔 방 배정

 

문제 설명

[본 문제는 정확성과 효율성 테스트 각각 점수가 있는 문제입니다.]

 

스노 타운에서 호텔을 운영하고 있는 스카피는 호텔에 투숙하려는 고객들에게 방을 배정하려 합니다. 호텔에는 방이 총 k개 있으며, 각각의 방은 1번부터 k번까지 번호로 구분하고 있습니다. 처음에는 모든 방이 비어 있으며 스카피는 다음과 같은 규칙에 따라 고객에게 방을 배정하려고 합니다.

1. 한 번에 한 명씩 신청한 순서대로 방을 배정합니다.
2. 고객은 투숙하기 원하는 방 번호를 제출합니다.
3. 고객이 원하는 방이 비어 있다면 즉시 배정합니다.
4. 고객이 원하는 방이 이미 배정되어 있으면 원하는 방보다 번호가 크면서 비어있는 방 중 가장 번호가 작은 방을 배정합니다.

예를 들어, 방이 총 10개이고, 고객들이 원하는 방 번호가 순서대로 [1, 3, 4, 1, 3, 1] 일 경우 다음과 같이 방을 배정받게 됩니다.

 

원하는 방 번호	배정된 방 번호
1	1
3	3
4	4
1	2
3	5
1	6

전체 방 개수 k와 고객들이 원하는 방 번호가 순서대로 들어있는 배열 room_number가 매개변수로 주어질 때, 각 고객에게 배정되는 방 번호를 순서대로 배열에 담아 return 하도록 solution 함수를 완성해주세요.

 

[제한사항]

 

• k는 1 이상 10^12 이하인 자연수입니다.
• room_number 배열의 크기는 1 이상 200,000 이하입니다.
• room_number 배열 각 원소들의 값은 1 이상 k 이하인 자연수입니다.
• room_number 배열은 모든 고객이 방을 배정받을 수 있는 경우만 입력으로 주어집니다.
  • 예를 들어, k = 5, room_number = [5, 5]와 같은 경우는 방을 배정받지 못하는 고객이 발생하므로 이런 경우는 입력으로 주어지지 않습니다.

---

[입출력 예]

K	room_number	result
10	[1,3,4,1,3,1]	[1,3,4,2,5,6]

입출력 예에 대한 설명

 

입출력 예 #1

문제의 예시와 같습니다.

첫 번째 ~ 세 번째 고객까지는 원하는 방이 비어 있으므로 즉시 배정받을 수 있습니다. 네 번째 고객의 경우 1번 방을 배정받기를 원했는데, 1번 방은 빈 방이 아니므로, 1번 보다 번호가 크고 비어 있는 방 중에서 가장 번호가 작은 방을 배정해야 합니다. 1번 보다 번호가 크면서 비어있는 방은 [2번, 5번, 6번...] 방이며, 이중 가장 번호가 작은 방은 2번 방입니다. 따라서 네 번째 고객은 2번 방을 배정받습니다. 마찬가지로 5, 6번째 고객은 각각 5번, 6번 방을 배정받게 됩니다.

 

---

메모리 제한, 시간제한이 없다면 문제 풀기 얼마나 좋을까요? 모든 문제를 구현만 해도 되니..

이 문제는 구현만 한다면 이보다 쉬울 수는 없습니다.  원하는 방 번호가 주어지면 방문한 적 있는지 체크해주고 없으면 1씩 증가시켜 방문 여부를 체크하면 됩니다. 그런데 k는 무려 최대 10^12이고, 배열의 크기도 200000입니다.

시간 복잡도가 N^2인 풀이는 택도 없죠. 이 문제는 유니온 파인드(disjoint-set)를 사용하는 문제입니다. 하지만 이 알고리즘은 일반 그래프 알고리즘(dfs, bfs, dijkstra)나 dp, 이분 탐색보다 중요도가 떨어져 얕게 공부하신 분들은 모를 가능성이 많습니다. 또한 그냥 개념만 어렴풋이 알고 문제를 많이 안 풀어보신 분은 이 문제가 유니온 파인드로 풀린다는 것을 알지 못할 가능성이 높습니다. 그래서 이번 2019 카카오 개발자 겨울 인턴십 문제 중에서는 가장 난도가 높았던 문제라고 봅니다. 거기다 해쉬로 좌표 압축까지 해주어야 하죠. gif파일로 설명하겠습니다. 

먼저 처음 3번은 원하는 방에 모두 배정할 수 있습니다. 여기에 추가로 우리는 작업을 하나 할건데, 양 옆으로 인접한 방을 체크하여 그 방이 차있다면 한 그룹으로 묶어주면서 가장 오른쪽 방의 번호를 그 그룹별로 갱신할겁니다.

첫째로 1번방을 원해 1번방에 배정을하는데, 여기서 1번방의 양옆에는 2번방이있는데, 아직 배정된 방이 아니므로 1번방은 따로 그룹으로 묶지않고 다음으로 넘어갑니다. 3번방 배정도 마찬가지로 양옆의 2,4번 방이 비어있으므로 넘어갑시다. 4번방에 배정할때는 3번방과 함께 묶여질 수 있습니다. 3번방과 4번방을 그룹으로 묶어주고, 가장 오른쪽 방이 4번방이라고 갱신해줍시다.

 

여기서 방문된 방에 들어가려는 손님이 있을때의 경우입니다. 4번손님이 1번방을 원하지만 이미 차있다는것을 확인하면, 1번방 그룹의 가장 오른쪽 방 의 그다음 오른쪽 방은 무조건 비어있음이 보장되면서 이 방은 손님이 갈 수 있는 가장 작은 방임이 자명합니다. 그렇게 4번손님을 2번방에 넣고나서 위와 동일하게 양 옆의 방을 살펴봅시다. 1번방과 3번방 둘다 방이 차있으므로 1번방 그룹과 3번방 그룹과 2번방이 모두 합쳐집니다. 그룹이 합쳐지면 동시에 가장 오른쪽 방도 갱신해줘야합니다. 그 방은 4번이 되겠네요.

 

이번엔 5번손님이 3번방에 가고싶다합니다. 3번방은 차있으니 3번그룹의 가장 오른쪽방의 다음 오른쪽방인 5번 방을 배정해주면됩니다. 그다음엔 역시 동일하게 양 옆의 방을 체크하고 방이 차있다면 합치면서 가장 오른쪽 방을 5번으로 갱신해줍니다.

 

마지막 손님도 위와 동일한 로직으로 정해주면 끝입니다.  이제 코드로 옮겨봅시다! 양 옆의 방을 합치는 로직이 유니온파인드 자료구조와 완벽히 들어맞습니다. 다만 주의해야 할 점이 앞서말한 좌표압축 비슷하게 hashMap으로 관리해주어야합니다. k의최댓값이 10^12이라 k의 값만큼 배열을 선언한다면 메모리초과가 날겁니다.

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

struct UNION_FIND
{
    int n;
public:
    vector<int>parent,height;
    vector<long long> right;
    UNION_FIND(int len)
    {
        n=len+1;
        parent.resize(n,0),height.resize(n,0),right.resize(n,0);
        for(int i=0;i<n;i++)parent[i]=i;
    }
    void init(int idx,long long r)
    {
        right[idx]=r;
    }
    int find(int u)
    {
        if(u==parent[u])return u;
        return find(parent[u]);
    }
    void merge(int u,int v)
    {
        u=find(u),v=find(v);
        if(u==v)return;
        
        if(height[u]>height[v])swap(u,v);
        parent[u]=v;
        //가장 오른쪽 방을 갱신
        right[v]=max(right[u],right[v]);
        if(height[u]==height[v])height[v]++;
    }
    long long  getRight(int idx)
    {
        return right[find(idx)];
    }
};

vector<long long> solution(long long k, vector<long long> room_number) {
    vector<long long> answer;
    map<long long,int>cache;
    UNION_FIND uf(room_number.size());
    int cnt=0;
    for(auto i:room_number)
    {
    	//이미 i번 방이 차있다면 i번 방 그룹의 가장 오른쪽 방+1이 배정되어야 할 방
        if(cache.find(i)!=cache.end())
           i=uf.getRight(cache[i])+1;
           
        answer.push_back(i);
        cache.insert({i,cnt++});
        uf.init(cache[i],i);
        
        if(cache.find(i-1)!=cache.end())
               uf.merge(cache[i-1],cache[i]);
        if(cache.find(i+1)!=cache.end())
               uf.merge(cache[i],cache[i+1]);
    }
    return answer;
}

접근방식이 쉽지않은 만큼 조금은 장황하게 설명을 첨부했는데 이해에 조금이라도 도움이 되었으면 좋겠습니다. 

해쉬값과 기본값을 구분해서 uf에 넣고 하는것이 꽤 헷갈리고 코드를 작성하는데 힘들 수 있습니다. 꼭 직접 코딩을 하면서 감을 익히시는게 좋습니다.

 

---

5. 징검다리 건너기

 

문제 설명

[본 문제는 정확성과 효율성 테스트 각각 점수가 있는 문제입니다.]

 

카카오 초등학교의 니니즈 친구들이 라이언 선생님과 함께 가을 소풍을 가는 중에 징검다리가 있는 개울을 만나서 건너편으로 건너려고 합니다. 라이언 선생님은 니니즈 친구들이 무사히 징검다리를 건널 수 있도록 다음과 같이 규칙을 만들었습니다.

• 징검다리는 일렬로 놓여 있고 각 징검다리의 디딤돌에는 모두 숫자가 적혀 있으며 디딤돌의 숫자는 한 번 밟을 때마다 1씩 줄어듭니다.
• 디딤돌의 숫자가 0이 되면 더 이상 밟을 수 없으며 이때는 그다음 디딤돌로 한 번에 여러 칸을 건너뛸 수 있습니다.
• 단, 다음으로 밟을 수 있는 디딤돌이 여러 개인 경우 무조건 가장 가까운 디딤돌로만 건너뛸 수 있습니다.

니니즈 친구들은 개울의 왼쪽에 있으며, 개울의 오른쪽 건너편에 도착해야 징검다리를 건넌 것으로 인정합니다.
니니즈 친구들은 한 번에 한 명씩 징검다리를 건너야 하며, 한 친구가 징검다리를 모두 건넌 후에 그다음 친구가 건너기 시작합니다.

디딤돌에 적힌 숫자가 순서대로 담긴 배열 stones와 한 번에 건너뛸 수 있는 디딤돌의 최대 칸수 k가 매개변수로 주어질 때, 최대 몇 명까지 징검다리를 건널 수 있는지 return 하도록 solution 함수를 완성해주세요.

 

[제한사항]

• 징검다리를 건너야 하는 니니즈 친구들의 수는 무제한이라고 간주합니다.
• stones 배열의 크기는 1 이상 200,000 이하입니다.
• stones 배열 각 원소들의 값은 1 이상 200,000,000 이하인 자연수입니다.
• k는 1 이상 stones의 길이 이하인 자연수입니다.

---

[입출력 예]

 

stones	k	result
[2, 4, 5, 3, 2, 1, 4, 2, 5, 1]	3	3

입출력 예에 대한 설명

---

입출력 예 #1

첫 번째 친구는 다음과 같이 징검다리를 건널 수 있습니다.

첫 번째 친구가 징검다리를 건넌 후 디딤돌에 적힌 숫자는 아래 그림과 같습니다.
두 번째 친구도 아래 그림과 같이 징검다리를 건널 수 있습니다.

두 번째 친구가 징검다리를 건넌 후 디딤돌에 적힌 숫자는 아래 그림과 같습니다.
세 번째 친구도 아래 그림과 같이 징검다리를 건널 수 있습니다.

세 번째 친구가 징검다리를 건넌 후 디딤돌에 적힌 숫자는 아래 그림과 같습니다.
네 번째 친구가 징검다리를 건너려면, 세 번째 디딤돌에서 일곱 번째 디딤돌로 네 칸을 건너뛰어야 합니다. 하지만 k = 3 이므로 건너뛸 수 없습니다.

따라서 최대 3명이 디딤돌을 모두 건널 수 있습니다.

 

 

---

접근하기 꽤 까다로웠던 4번과 달리, 5번 문제는 접근법이 비교적 명확합니다. stones배열의 크기가 최대 20만에, 각 배열의 원소들은 2억이어서 어떤 알고리즘을 써야 하나 막막할 수 있지만, 다행히 우리는 로그의 마법을 쓰게 해 주는 이분 탐색을 사용할 수 있습니다. 시간 복잡도는 O(NlogK) (*배열의 크기 N, 각 원소의 최댓값 K) 이 자명합니다. mid명의 사람이 건너갈 수 있는지를 bool값으로 반환하는 is_possible함수를 작성하여 이분 탐색 알고리즘의 코드를 작성해주면 됩니다.

 

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

bool is_possible(int mid,const vector<int>&stones,int k)
{
    int now=-1;
    for(int i=0;i<stones.size();i++)
    {
           if(stones[i]-mid+1>0)
           {
                if(i-now>k)return false;
               now=i;
           }
	 }
   	if(stones.size()-now>k)return false;
    else return true;
}

int solution(vector<int> stones, int k) {
   	int answer = 0;
    
    int left=0,right=(int)2e8;
    while(left<=right)
    {
        int mid=(left+right)/2;
        if(is_possible(mid,stones,k))
        {
            answer=mid;
            left=mid+1;
        }
        else right=mid-1;
    }
    return answer;
}

 

---

 

모든 문제의 풀이가 끝났습니다. 꽤 까다로운 문제들도 있었지만 4시간에 5문제이면 생각할 시간을 충분히 준 것이라고 생각합니다. 개인적인 난이도 순서는

 

4. 호텔 방 배정 > 5. 징검다리 건너기 > 3. 불량 사용자 > 2. 튜플 > 1. 크레인 인형 뽑기 게임

 

인 것 같습니다. 모든 문제가 boj의 solved.ac난이도 기준 실버 3~골드 2 수준인 것 같으니 골드 문제만 골라서

알고리즘 종류 편식 없이 여러 개 푼다면 이러한 코딩 테스트 준비에 많은 도움이 될 것 같습니다.

문제 푸느라 수고하셨습니다. 😌