상경한 개발자 지망생들

문제 설명

개발팀 내에서 이벤트 개발을 담당하고 있는 "무지"는 최근 진행된 카카오이모티콘 이벤트에 비정상적인 방법으로 당첨을 시도한 응모자들을 발견하였습니다. 이런 응모자들을 따로 모아 불량 사용자라는 이름으로 목록을 만들어서 당첨 처리 시 제외하도록 이벤트 당첨자 담당자인 "프로도" 에게 전달하려고 합니다. 이 때 개인정보 보호을 위해 사용자 아이디 중 일부 문자를 '*' 문자로 가려서 전달했습니다. 가리고자 하는 문자 하나에 '*' 문자 하나를 사용하였고 아이디 당 최소 하나 이상의 '*' 문자를 사용하였습니다.
"무지"와 "프로도"는 불량 사용자 목록에 매핑된 응모자 아이디를 제재 아이디 라고 부르기로 하였습니다.

예를 들어, 이벤트에 응모한 전체 사용자 아이디 목록이 다음과 같다면

응모자 아이디

다음과 같이 불량 사용자 아이디 목록이 전달된 경우,

불량 사용자

불량 사용자에 매핑되어 당첨에서 제외되어야 야 할 제재 아이디 목록은 다음과 같이 두 가지 경우가 있을 수 있습니다.

제재 아이디

제재 아이디

이벤트 응모자 아이디 목록이 담긴 배열 user_id와 불량 사용자 아이디 목록이 담긴 배열 banned_id가 매개변수로 주어질 때, 당첨에서 제외되어야 할 제재 아이디 목록은 몇가지 경우의 수가 가능한 지 return 하도록 solution 함수를 완성해주세요.

[제한사항]

• user_id 배열의 크기는 1 이상 8 이하입니다.
• user_id 배열 각 원소들의 값은 길이가 1 이상 8 이하인 문자열입니다.
  • 응모한 사용자 아이디들은 서로 중복되지 않습니다.
  • 응모한 사용자 아이디는 알파벳 소문자와 숫자로만으로 구성되어 있습니다.
• banned_id 배열의 크기는 1 이상 user_id 배열의 크기 이하입니다.
• banned_id 배열 각 원소들의 값은 길이가 1 이상 8 이하인 문자열입니다.
  • 불량 사용자 아이디는 알파벳 소문자와 숫자, 가리기 위한 문자 '*' 로만 이루어져 있습니다.
  • 불량 사용자 아이디는 '*' 문자를 하나 이상 포함하고 있습니다.
  • 불량 사용자 아이디 하나는 응모자 아이디 중 하나에 해당하고 같은 응모자 아이디가 중복해서 제재 아이디 목록에 들어가는 경우는 없습니다.
• 제재 아이디 목록들을 구했을 때 아이디들이 나열된 순서와 관계없이 아이디 목록의 내용이 동일하다면 같은 것으로 처리하여 하나로 세면 됩니다.

[입출력 예]

user_id banned_idresult

접근 방법

1.  user_id는 모두 각각 다른 문자열이므로 idx로 표현가능합니다. 

2.  2차원 벡터 vector<vector<int>> possible에 전처리를 하여 정리합니다.

3.  possible의 의미는 possible[banned_id의 idx] = { 가능한 user_id의 idx들} 과 같습니다. 

4.  모든 i에 대해 possible[i]의 한 가지 값은 포함이 되어야하며, 중복이 없어야 합니다.

5.  집합을 bitmask로 표현하면 조금 더 시간복잡도를 줄일 수 있습니다.(요소 하나하나를 비교하지 않아도 되기 때문)

소스 코드

#include <string>
#include <vector>
#include <set>

using namespace std;

set<int> bitmask;
vector<vector<int>> possible; //possible[banned_id idx] = {user_id idx....};

void backTracking(int cnt, int n, int bit){
    
    //bitmask는 set 자료구조이므로 이미 기존에 완성된 조합이 있어도 자동 처리
    if(cnt == n){
        bitmask.insert(bit);
        return;
    }
    
    for(int i=0;i<possible[cnt].size();i++){
    	//중복 검사
        if((bit & (1 << possible[cnt][i])) != (1 << possible[cnt][i])){
            bit |= (1 << possible[cnt][i]);
            backTracking(cnt+1, n, bit);
            bit &= ~(1 << possible[cnt][i]);    
        }
    }
}

int solve(vector<string> user_id, vector<string> banned_id){
    
    possible.resize(banned_id.size());
    
    //make possible 1,2,3번 과정
    for(int i=0;i<banned_id.size();i++){
        
        string ban = banned_id[i];
        int cnt = 0;
        
        //ban_id에 대해 표현 가능한 user_id를 찾아냄
        for(int j=0;j<user_id.size();j++){
            string id = user_id[j];
            
            if(id.size() == ban.size()){
                bool flag = true;
                for(int k=0;k<id.size();k++){
                    if(ban[k] != '*'){
                        if(ban[k] != id[k]){
                            flag = false;
                            break;
                        }
                    }
                }
                if(flag)
                    possible[i].push_back(j);
            }
        }
    }
    
    //possible의 모든 요소에서 하나씩 골라내야 하므로 backTracking 
    backTracking(0, banned_id.size(), 0);
    return bitmask.size();
}

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

문제 설명

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

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

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

원하는 방 번호배정된 방 번호

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

[제한사항]

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

[입출력 예]

kroom_numberresult

입출력 예에 대한 설명

입출력 예 #1

문제의 예시와 같습니다.

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

접근 방법

 효율성 검사가 있는 문제이기에 heuristic하게 접근하면 안된다고 생각을 하였습니다. 그렇기에 방 번호를 배정하면서 다른 방들까지도 한 번에 다음 배치 될 방이 어딘지 update를 해줘야 한다는 생각을 해보며 union find를 떠올렸습니다. 집합의 root를 집합내에 가장 큰 값으로 지정하면 해결할 수 있다고 생각을 하였습니다. 그리고 k(방 번호)가 매우 큰 수가 될 수 있기 때문에 배열보다는 Map을 사용해 해결할 수 있다는 확신을 가지게 되었습니다.

1. 현재 방이 사용 가능한지 확인합니다.

2. 사용 가능하다면 현재 방을 배치시켜줍니다.

3. 사용 가능하지 않다면 find함수를 통해 그 다음 방을 알아냅니다.

4. 2,3번 동작 이후 양 옆이 비어있는 방인지 확인 후 비어있지 않다면 union시켜줍니다. 이 때 집합의 root는 가장 큰 방의 번호로 갱신합니다.

자세한 내용은 코드에 주석으로 달아놓겠습니다.

소스 코드

#include <string>
#include <vector>
#include <unordered_map>

using namespace std;

unordered_map <long long, long long> parent;

long long find(long long node){
    
    if(node == parent[node])
        return node;
    long long root = find(parent[node]);
    return parent[node] = root;
}

//더 큰 값이 root가 되어야 함
void Union(long long small, long long big){
    
    small = find(small);
    big = find(big);
    parent[small] = big;
}

vector<long long> solve(long long k, vector<long long> room_number){
    
    vector<long long> ans;
    
    for(int i=0;i< room_number.size();i++){
        
        //손님이 들어가길 원하는 방 번호
        long long n = room_number[i];
        
        //현재 방이 비어있다면
        if(parent.count(n) == 0){
            
            //손님을 방에 배치
            parent[n] = n;
            ans.push_back(n);
            
            //좌우에 손님이 있는 방이 있다면 union
            if(parent.count(n - 1) > 0)
                Union(n - 1, n);
            if(parent.count(n + 1) > 0)
                Union(n, n + 1);
        }
        else{
            
            //손님이 들어있는 연속된 방 번호 중 가장 큰 값 root에 +1(빈 방)
            long long pos = find(n) + 1;
            
            //손님을 방에 배치
            parent[pos] = pos;
            ans.push_back(pos);
            
            //좌우에 손님이 있는 방이 있다면 union
            if(parent.count(pos - 1) > 0)
                Union(pos - 1, pos);
            if(parent.count(pos + 1) > 0)
                Union(pos, pos + 1);
        }
    }
    return ans;
}

vector<long long> solution(long long k, vector<long long> room_number) {
    vector<long long> answer;
    return answer = solve(k, room_number);
}

문제 설명

튜브의 소개팅

얼마 전 소개팅에 실패해 낙담한 튜브를 안타깝게 여긴 친구들은 튜브에게 새로운 사람을 소개해주기로 했다. 좀 더 자연스러운 자리를 만들기 위해, 튜브와 소개팅녀를 파티에 초대하기로 했다.

친구들은 튜브에게 파티에 초대된 모든 사람의 위치를 알려주었다. 사각형 모양의 파티장 입구는 왼쪽 맨 위였고, 만나야 하는 상대의 좌석은 파티장의 오른쪽 맨 아래였다. 파티장의 가로 길이가 n이라고 하고, 세로 길이를 m이라 할 때, 튜브와 소개팅 상대의 위치는 각각, (0, 0), (m - 1, n - 1)이 된다.

튜브는 (0, 0)에서 (m - 1, n - 1)까지 가는 가장 짧은 길을 알고 싶다. 이동은 좌/우/상/하로만 가능하다. 또한, 조금이라도 더 빠르게 이동하고 싶은 튜브는 이동하는 중에 가능한 덜 수다스러운 친구들만 만나고 싶다. 다시 말해, 목표 지점까지 길이가 같은 여러 개의 경로가 존재할 경우, 경로상에 위치한 친구들과 나눠야 하는 대화 시간의 합이 적은 것을 더 선호한다.

튜브에게는 스트레스를 심하게 받을 경우 미친 오리로 변하는 비밀이 있다. 경로 상에 위치한 친구들과 나눠야 하는 대화 시간의 합이 s를 초과한다면 미친 오리로 변하고 소개팅에 실패하고 말 것이다! 그러므로 아무리 짧은 경로라도 친구들과 나눠야 하는 대화 시간의 합이 s를 초과한다면 그 경로를 진행할 수는 없다.

튜브가 소개팅 상대에게 무사히 갈 수 있는 경로를 알려주자.

입력 형식

입력은 파티장의 크기 m과 n 그리고 튜브가 참을 수 있는 대화 시간의 총합 s, 친구와의 대화에 필요한 시간 t가 담긴 2차원 배열 time_map으로 주어진다. t가 -1인 경우는 파티 테이블이 위치한 경우라 지나갈 수 없다. 그리고 시작 지점과 도착 지점에서는 수다에 필요한 시간이 없다, 즉 t = 0이다.
추가 제한조건은 아래와 같다.

• 2 <= n, m <= 50
• 1 <= s <= 2^31-1
• -1 <= t <= 2^31-1
• 모든 입력에는 문제의 조건을 만족하는 경로가 하나 이상 존재한다.

출력 형식

리턴 타입은 원소가 두 개인 정수 배열이다. 튜브가 이동해야 하는 경로의 길이와 해당 경로를 지나갈 때 친구와 나눠야 하는 대화 시간의 총합을 리턴한다.

예제 입출력

mnstime_mapanswer

접근 방법

 dp[x좌표][y좌표][목적지로부터 현재지점까지의 거리]로 3차원 dp를 사용하여 해결할 수 있었습니다.

보통 bottom up을 사용한 풀이가 대부분이지만 저는 top-down 성애자여서 top-down방식으로 해결하였습니다. 

 문제를 해결하기 위해서는 0,0부터 m-1,n-1까지 갈 수 있는 가능한 모든 dist에 대해 검사해 봐야 합니다.

dist의 범위는 m+n-2 ~ m*n정도로 잡을 수 있습니다. 즉 for문을 통해 작은 dist부터 검사하게 되며 이 때 가능한 케이스가 있다면 그 때의 dp값이 정답이 될 것 입니다.

 한 케이스(dist)에서는 최소 대화시간을 기준으로 최소가 되는 최적해를 찾아나가면 됩니다. 

자세한 설명은 소스코드에 주석처리 하겠습니다.

소스 코드

#include <vector>
#include <algorithm>
#include <iostream>
#include <string.h>

using namespace std;

pair<int, int> direction[4] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
vector<vector<int>> map;
long long dp[50][50][2501];
int M, N, S;
long long MAX = 0x7FFFFFFF;

bool inRange(int x, int y){
    return (0 <= x && x < M && 0 <= y && y < N);
}

long long solve(int x, int y, int dist){
    
    long long &ref = dp[x][y][dist];
    
    //목적지에 정상적으로 도착한 경우
    if(x == M - 1 && y == N - 1 && dist == 0) 
        return ref = 0;
    if(ref != -1)
        return ref;
    
    ref = MAX; //방문 표시
    
    for(int i=0;i<4;i++){
        
        int next_x = x + direction[i].first;
        int next_y = y + direction[i].second;
        
        //범위를 벗어나거나, 더 이상 이동할 수 없는 경우, continue
        if(!inRange(next_x, next_y) || map[next_x][next_y] == -1 || dist < 1)
            continue;
        long long ret = solve(next_x, next_y, dist - 1) + map[x][y];
        if(ret <= S)
            ref = min(ref, ret); //같은 dist일때 대화시간이 짧은 것이 우선순위
    }
    
    return ref;
}

// 전역 변수를 정의할 경우 함수 내에 초기화 코드를 꼭 작성해주세요.
vector<int> solution(int m, int n, int s, vector<vector<int>> time_map) {
    
    //전역 변수 초기화
    memset(dp, -1, sizeof(dp));
    map = time_map;
    M = m; N = n; S = s;
    
    int move_distance = MAX;
    int sum_of_talk_time = MAX;
    
    //최대한 짧은 거리로 이동하는 것을 구해야 하기 때문에 작은 dist 부터 검사
    for(int i= M+N-2; i <= M*N; i++){
        long long ret = solve(0,0,i); 
        //만약 만족하는 해가 존재한다면
        if(ret < MAX){
            move_distance = i;
            sum_of_talk_time = ret;
            break;
        }
    }
    
    vector<int> answer(2);
    answer[0] = move_distance;
    answer[1] = sum_of_talk_time;
    
    return answer;
}