상경한 개발자 지망생들

문제 설명

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

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

응모자 아이디

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

불량 사용자

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

제재 아이디

제재 아이디

이벤트 응모자 아이디 목록이 담긴 배열 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;
}

문제 설명

GPS

카카오 택시 개발자 Jay-G는 다음 업데이트를 준비하기 위해 개선사항을 위한 여러 피드백을 받았다. 그중에서 손님이 자주 탑승하는 위치를 추천해주었으면 한다는 의견이 많았다.

다음 업데이트 준비를 위해 Jay-G는 택시의 승하차 및 이동 경로를 수집하여 분석하기 시작하였다. 데이터를 분석하던 Jay-G는 몇 가지 특이사항을 발견했다. 택시의 이동 경로를 GPS를 통해 수집하게 되는데, GPS 신호 불량, 통신 오류 등 다양한 원인으로 위치의 오류가 발생한 것을 알게 되었다. 다만 승차 위치와 하차 위치는 오류가 없는 것으로 확인이 되었다.

개발자 Jay-G는 수집한 이동 경로의 오류를 최소한으로 수정하여 좀 더 정확한 이동 경로를 구하고 싶어 한다.

택시는 다음과 같은 조건으로만 이동한다. 먼저 택시는 거점을 이동해 다니며, 거점 간의 이동은 해당하는 도로가 있는 경우에만 가능하다. 또한, 교통 상황에 따라 택시는 한 거점에 머무를 수 있고, 왔던 길을 되돌아갈 수 있다. 모든 도로는 방향이 별도로 없는 왕복 도로이다.

예를 들어, 위 그래프에서 택시가 다음과 같이 시간대별로 이동 경로를 보내왔다.

t위치

하지만 위의 택시가 보내온 경로에는 거점 3에서 거점 6으로 이동할 수 있는 도로가 없으므로 이동 경로에 오류가 있다.

이러한 오류를 최소한으로 수정하여 이동 가능한 경로로 만들고 싶다. 이 경우 1회의 오류를 수정하여 다음과 같이 이동 가능한 경로를 만들 수 있다. 시간 t=4의 위치를 거점 5로 한 번 수정하면 이동 가능한 경로가 된다.

t위치

이와 비슷하게 시간 t=4의 위치를 거점 4로 바꾸거나, 시간 t=5 위치를 거점 5로 바꾸면 이동 가능한 경로로 만들 수 있다. 위의 경우 수정한 오류의 개수는 1개이다.

t위치

t위치

위와 같이 택시가 보내온 경로에서 이동 가능한 경로로 만드는 최소의 오류 수정 횟수를 구하여라.

입력 형식

주어지는 입력은 총 다섯 가지로, 거점 개수 n과 도로의 개수 m, 각 거점 간의 연결된 도로 정보 edge_list, 택시가 시간대별로 보내오는 거점 정보의 총 개수 k, 그리고 머물렀던 거점의 정보 gps_log이다. 제한조건은 아래와 같다.

• 2 <= n <= 200
• 1 <= m <= 10,000
• 2 <= k <= 100
• edge_list는 m × 2 크기의 2차원 배열로, 각 행의 두 값은 도로가 잇는 두 거점의 번호를 의미한다.
• 거점의 번호는 1부터 n까지 숫자이다.
• 모든 도로는 양방향 통행이 가능하다.
• 입력되는 데이터에서 항상 모든 거점 간 경로가 있음이 보장되지 않는다.
• gps_log의 시작 거점과 도착 거점은 바뀔 수 없다.

출력 형식

이동 가능한 경로로 만들 수 있는 최소의 오류 수정 횟수를 리턴한다. 올바른 경로로 수정하는 것이 불가능할 경우 -1을 리턴한다.

예제 입출력

변수명값

변수명값

예제에 대한 설명

두 예제 모두 edge_list의 데이터는 본문의 그림과 같은 예이다.
첫 번째 테스트 케이스에서 gps_log로 주어진 경로 중 거점 3에서 거점 6으로 가는 도로가 없다. 여기서 시간 t=4의 위치를 거점 5로 한 번 수정하면 이동 가능한 경로가 된다.
두 번째 테스트 케이스는 gps_log로 주어진 경로가 모두 도로로 연결된 경우이므로 수정이 필요 없다.

접근 방법

DP를 사용해 해결하였습니다. 

저는 동적계획법을 사용할 때 재귀함수를 사용한 Top-Down방식을 선호하기 때문에 Top-Down방식으로 해결하였습니다.

dp테이블의 설계는 아래와 같습니다.

dp[시간][지점] = 최적해(마지막 시간 부터 현재 시간까지의 거점들을 이동 가능 경로로 만들 수 있는 최소 변경 횟수)

 문제를 해결하기에 앞서 필요한 데이터를 전처리 해야 합니다. 저는 아래와 같은 구조로 데이터를 전처리 하였습니다.

ArrayList <ArrayList<Integer>> info = new ArrayList();

info[현재위치] = {현재 위치로 부터 갈 수 있는 거점들의 집합}

info의 초기화 코드는 아래와 같습니다.

public void init(int n, int[][] edge_list, int[] gps_log){

	this.gps_log = gps_log;
	
    //dp를 -1로 초기화
	for(int i=0;i<=gps_log.length;i++)
		Arrays.fill(dp[i], -1);

	for(int i=0;i<=n;i++){
		info.add(new ArrayList<Integer>());
		info.get(i).add(i); //정차하는 경우
	}

	for(int i=0;i<edge_list.length;i++){
		info.get(edge_list[i][0]).add(edge_list[i][1]); //양 방향
		info.get(edge_list[i][1]).add(edge_list[i][0]); //양 방향
	}
}

dp의 핵심 풀이는 info[현 위치]의 한 요소를 next라고 할 때 가능한 모든 next에 대해 최소를 구해가는 것이고, 

next == gps_log[현재 시간 + 1]라면 거점 정보의 변경 없음,  next != gps_log[현재 시간 + 1]라면 변경횟수 1회 증가를 하여 반환을 하면 됩니다. 자세한 설명은 소스 코드에 주석 처리 하겠습니다.

여기서 중요한 점은 불가능한 경우가 2가지가 있다는 점입니다.

1. edge_list에서 마지막 거점으로 가능 경로가 없는 경우

2. 마지막 거점을 변경해야지만 조건에 만족하는 경우 

소스 코드

import java.util.*;

class Solution {
    
    ArrayList <ArrayList<Integer>> info = new ArrayList();
    int[] gps_log;
    int[][] dp = new int[101][201];
    int MAX = 54321;
    
    public void init(int n, int[][] edge_list, int[] gps_log){
        
        this.gps_log = gps_log;
        
        for(int i=0;i<=gps_log.length;i++)
            Arrays.fill(dp[i], -1);
        
        for(int i=0;i<=n;i++){
            info.add(new ArrayList<Integer>());
            info.get(i).add(i); //정차하는 경우
        }
        
        for(int i=0;i<edge_list.length;i++){
            info.get(edge_list[i][0]).add(edge_list[i][1]); //양 방향
            info.get(edge_list[i][1]).add(edge_list[i][0]); //양 방향
        }
    }
    
        
    public int solve(int time, int now){
        
       	// 마지막 지점은 변경 불가능 이므로 1이 아닌 MAX를 return 
        if(time == gps_log.length - 1)
            return dp[time][now] = (gps_log[time] == now) ? 0 : MAX;
        //이미 구해진 최적해가 있다면
        if(dp[time][now] != -1)
            return dp[time][now];
        
        //ret는 최소를 구하기 위한 변수이므로 비교적 큰 값으로 초기화
        int ret = MAX;
        dp[time][now] = 0;
        
        for(int i=0;i<info.get(now).size();i++){
            int next = info.get(now).get(i);
            ret = Math.min(solve(time+1, next), ret);
        }
        
        //변경해야 하는 경우 +1
        return dp[time][now] = (gps_log[time] == now) ? ret : ret + 1;
    }
    
    public int solution(int n, int m, int[][] edge_list, int k, int[] gps_log) {
        int answer = 0;
        init(n, edge_list, gps_log);
        answer = solve(0, gps_log[0]);
        
        //마지막 지점으로 가는 경로가 없거나, 만족하는 해가 없다면
        return answer = (dp[k-1][gps_log[k-1]] == -1 || dp[k-1][gps_log[k-1]] >= MAX) ? -1 : answer;
    }
}

문제 설명

리틀 프렌즈 사천성

언제나 맛있는 음식들이 가득한 평화로운 푸드 타운. 푸드 타운에서 행복하게 사는 리틀 프렌즈들은 마을에 있는 매직 스푼을 보물처럼 보관하고 있다. 매직 스푼은 재료만 준비해서 냄비에 넣고 휘젓기만 하면 순식간에 최고의 요리로 만들어주는 신비의 아이템. 어느 날 매직 스푼을 호시탐탐 노리는 악당들이 보물을 훔쳐간다. 매직 스푼을 되찾고 다시 마을에 평화를 가져오기 위해 프렌즈의 대모험이 시작되는데...

리틀 프렌즈 사천성은 프렌즈 사천성과 유사한 게임이다. 게임은 2차원 배열에서 진행되는데, 여러 가지 무늬로 구성된 타일이 배치되어 있으며 같은 모양의 타일은 두 개씩 배치되어 있다. 게임의 목적은 배치된 모든 타일을 제거하는 것으로, 같은 모양의 타일을 규칙에 따라 제거하면 된다. 타일을 제거할 수 있는 경우는 다음과 같다.

다음 조건을 만족하는 경로가 있을 때 두 타일을 제거할 수 있다.

• 경로의 양 끝은 제거하려는 두 타일이다.
• 경로는 두 개 이하의 수평/수직 선분으로 구성되어 있고, 이들은 모두 연결되어 있다. (즉, 경로를 한 번 이하로 꺾을 수 있다)
  • 참고: 프렌즈 사천성은 경로가 세 개 이하의 선분으로 구성되어야 한다는 점이 다르다. (즉, 경로를 두 번 이하로 꺾을 수 있다)
• 경로 상에는 다른 타일 또는 장애물이 없어야 한다.

위의 배열에서 어피치 타일은 직선의 경로로 이을 수 있으므로 제거 가능하다. 라이언 타일 역시 한 번 꺾인 경로로 연결되므로 제거 가능하다. 무지 타일의 경우 다른 타일을 지나지 않는 경로는 두 번 꺾여야 하므로 제거할 수 없는 타일이며, 튜브 타일 역시 직선의 경로 사이에 장애물이 있으므로 제거 가능하지 않다.

타일 배열이 주어졌을 때, 규칙에 따라 타일을 모두 제거할 수 있는지, 그 경우 어떤 순서로 타일을 제거하면 되는지 구하는 프로그램을 작성해보자.

입력 형식

입력은 게임판의 크기를 나타내는 m과 n, 그리고 배치된 타일의 정보를 담은 문자열 배열 board로 주어진다. 이 배열의 크기는 m이며, 각각의 원소는 n글자의 문자열로 구성되어 있다. 입력되는 값의 제한조건은 다음과 같다.

• 1 <= m, n <= 100
• board의 원소는 아래 나열된 문자로 구성된 문자열이다. 각 문자의 의미는 다음과 같다.
  • .: 빈칸을 나타낸다.
  • *: 막힌 칸을 나타낸다.
  • 알파벳 대문자(A-Z): 타일을 나타낸다. 이 문제에서, 같은 글자로 이루어진 타일은 한 테스트 케이스에 항상 두 개씩만 존재한다.
  • board에는 알파벳 대문자가 항상 존재한다. 즉, 타일이 없는 입력은 주어지지 않는다.

출력 형식

해가 존재하는 경우 타일을 제거하는 순서대로 한 글자씩 이루어진 문자열을, 그렇지 않은 경우 IMPOSSIBLE을 리턴한다. 해가 여러 가지인 경우, 알파벳 순으로 가장 먼저인 문자열을 리턴한다.

예제 입출력

mnboardanswer

예제에 대한 설명

첫 번째 테스트 케이스에서 처음으로 제거 가능한 타일은 A와 C이다. 그리고 모든 가능한 경우를 나열하면 ABCD, ACBD, ACDB, CABD, CADB, CDAB이다. 이 중 알파벳 순으로 가장 먼저인 ABCD가 정답이다.

네 번째 테스트 케이스는 초기 상태에서 제거할 수 있는 타일이 없으므로 타일을 모두 제거하는 것이 불가능하다. 따라서 정답은 IMPOSSIBLE이다.

접근 방법

문제 풀이를 떠올리는 것은 어렵지 않았습니다. 하지만 치명적 실수 때문에 시간을 꽤 오래 잡았고 큰 깨달음을 얻게 해준 문제였습니다.

(!!!혹시 테스트 케이스는 다 맞는데 틀리는 분들을 위해 일단 제 실수에 대해 설명드리겠습니다.)

저는 문제를 보자마자 짝을 찾는 방법에 대해 BFS를 떠올렸습니다.

BFS를 사용할 때 visited로 방문체크를 하였는데 이게 가장 치명적인 실수였습니다.

만약 아래와 같이 입력이 주어졌을 때

BFS탐색 순서에 따라 아래와 같은 경로가 가능함에도 불구하고

좌측 사진과 같은 순서로 먼저 탐색이 된다면 우측 사진의 경로로 탐색이 불가능 하다는 점이었습니다.

왜냐하면 1,2 지점에 visited[1][2] = true가 되기 때문에 1,2지점으로 갈 수 없기 때문입니다.

 즉, 탐색을 할 경우 BFS의 경우 약간의 변형을 통해 visited를 사용하지 않거나, DFS(모든 지점 방문이 목적)의 경우 backTracking(모든 경로 탐색이 목적)을 사용한다면 이러한 문제점을 극복할 수 있습니다.

문제풀이는 아래와 같습니다.

1. (A~Z) 짝의 좌표를 저장 (동시에 제거 해야할 짝의 수를 증가->나중에 모든 짝이 제거되었는지 확인하기 위한 목적)

2. A~Z까지 제거 가능한 짝이 있는지 검사

3. 2에서 제거 가능한 짝이 있다면 제거 후, A부터 다시 검사

(A부터 검사하는 이유는 가능한 경우에 대해 사전 순 정렬 목적)

4. 제거할 수 있는 짝이 없다면 완전히 제거가 되었는지 검사

자세한 내용은 소스코드에 주석 처리 하였습니다.

소스 코드

#include <string>
#include <vector>
#include <queue>

using namespace std;

typedef struct qinfo{
//행, 열, 방향, 꺾은 횟수
    int x,y,dir,cnt;
};
typedef struct ainfo{
    int x,y;
};

int pairCnt = 0;
int N = 0,M = 0;

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

bool BFS(int start_x, int start_y, int end_x, int end_y, vector<string> &boards){
    
    pair<int, int> nextdir[4] = {{1,0},{0,1},{-1,0},{0,-1}};
    
    queue<qinfo> q;
    
    //어떤 방향으로 출발해도 상관 없다는 표시로 dir = -1;
    q.push({start_x, start_y, -1, 0});
    
    while(!q.empty()){
        
        int now_x = q.front().x; int now_y = q.front().y;
        int cnt = q.front().cnt; int dir = q.front().dir;
        q.pop();
        
        for(int i=0;i<4;i++){
            
            //dir이 -1이 아닐 때 역 방향이라면 continue
            if(dir != -1 && abs(dir - i) == 2)
                continue;
            
            int next_x = now_x + nextdir[i].first;
            int next_y = now_y + nextdir[i].second;
            int next_cnt = (dir == i || dir == -1) ? cnt:cnt+1; //방향이 다르다면 꺾어야만 함
            
            if(inRange(next_x, next_y)){
                //어디로 가던지 꺾은 횟수가 1번 이하여야 함
                if(next_cnt <= 1){
                    if(boards[next_x][next_y] == '*'){
                        continue;
                    }
                    else if(boards[next_x][next_y] == '.'){
                        q.push({next_x, next_y, i, next_cnt});
                    }
                    else {
                        //제거 할 수 있는 패를 찾았다면
                        if(next_x == end_x && next_y == end_y)
                            return true;
                    }    
                }
            }
        }
    }
    return false;
}

string solve(vector<vector<ainfo>> &arr, vector<string> &boards){
    
    string ans = "";
    bool flag = true;
    
    while(flag){
        
        flag = false;
        
        //2번 과정, A~Z까지 검사
        for(int i=0;i<arr.size();i++){
            //해결 해야할 요소가 있다면
            if(arr[i].size() > 1){
            	//BFS를 통해 제거 가능한 짝이 있는지 검사
                if(BFS(arr[i][0].x, arr[i][0].y, arr[i][1].x, arr[i][1].y, boards)){
                	//3번 과정, 제거한 부분을 빈 공간으로 변경
                    boards[arr[i][0].x][arr[i][0].y] = boards[arr[i][1].x][arr[i][1].y] = '.'; //빈칸으로 만듬
                    arr[i].clear(); //배열 정보 삭제
                    pairCnt -= 2; //제거 해야할 짝의 수 감소
                    ans += char(i + int('A')); 
                    flag = true;
                    break;
                }    
            }
        }   
    }
    
    //4번 과정
    if(pairCnt == 0) //모든 짝을 제거한 경우
        return ans;
    else //더 이상 해결을 못하는 경우
        return "IMPOSSIBLE";
}

// 전역 변수를 정의할 경우 함수 내에 초기화 코드를 꼭 작성해주세요.
string solution(int m, int n, vector<string> board) {
    
    string answer = "";
    vector<vector<ainfo>> arr(26, vector<ainfo>());
    
    //전역 변수 초기화
    pairCnt = 0;
    M=m; N=n;
    
    //1번 과정, 모든 짝의 위치를 저장
    for(int i=0;i<m;i++){
        for(int j=0;j<n;j++){
            if('A' <= board[i][j] && board[i][j] <= 'Z'){
            	//alphabet을 int로 변환 후 위치 저장
                arr[int(board[i][j]) - int('A')].push_back({i,j});
                pairCnt++; //제거 해야 할 짝의 수 증가
            }
        }
    }
                
    return answer = solve(arr,board);
}

문제 설명

단체사진 찍기

가을을 맞아 카카오프렌즈는 단체로 소풍을 떠났다. 즐거운 시간을 보내고 마지막에 단체사진을 찍기 위해 카메라 앞에 일렬로 나란히 섰다. 그런데 각자가 원하는 배치가 모두 달라 어떤 순서로 설지 정하는데 시간이 오래 걸렸다. 네오는 프로도와 나란히 서기를 원했고, 튜브가 뿜은 불을 맞은 적이 있던 라이언은 튜브에게서 적어도 세 칸 이상 떨어져서 서기를 원했다. 사진을 찍고 나서 돌아오는 길에, 무지는 모두가 원하는 조건을 만족하면서도 다르게 서는 방법이 있지 않았을까 생각해보게 되었다. 각 프렌즈가 원하는 조건을 입력으로 받았을 때 모든 조건을 만족할 수 있도록 서는 경우의 수를 계산하는 프로그램을 작성해보자.

입력 형식

입력은 조건의 개수를 나타내는 정수 n과 n개의 원소로 구성된 문자열 배열 data로 주어진다. data의 원소는 각 프렌즈가 원하는 조건이 N~F=0과 같은 형태의 문자열로 구성되어 있다. 제한조건은 아래와 같다.

• 1 <= n <= 100
• data의 원소는 다섯 글자로 구성된 문자열이다. 각 원소의 조건은 다음과 같다.
  • 첫 번째 글자와 세 번째 글자는 다음 8개 중 하나이다. {A, C, F, J, M, N, R, T} 각각 어피치, 콘, 프로도, 제이지, 무지, 네오, 라이언, 튜브를 의미한다. 첫 번째 글자는 조건을 제시한 프렌즈, 세 번째 글자는 상대방이다. 첫 번째 글자와 세 번째 글자는 항상 다르다.
  • 두 번째 글자는 항상 ~이다.
  • 네 번째 글자는 다음 3개 중 하나이다. {=, <, >} 각각 같음, 미만, 초과를 의미한다.
  • 다섯 번째 글자는 0 이상 6 이하의 정수의 문자형이며, 조건에 제시되는 간격을 의미한다. 이때 간격은 두 프렌즈 사이에 있는 다른 프렌즈의 수이다.

출력 형식

모든 조건을 만족하는 경우의 수를 리턴한다.

예제 입출력

ndataanswer

예제에 대한 설명

첫 번째 예제는 문제에 설명된 바와 같이, 네오는 프로도와의 간격이 0이기를 원하고 라이언은 튜브와의 간격이 2보다 크기를 원하는 상황이다.

두 번째 예제는 무지가 콘과의 간격이 2보다 작기를 원하고, 반대로 콘은 무지와의 간격이 1보다 크기를 원하는 상황이다. 이는 동시에 만족할 수 없는 조건이므로 경우의 수는 0이다.

접근 방법

백트래킹 기법을 사용하여 해결할 수 있었습니다.

1. 백트래킹을 사용하여 8명이 서있을 수 있는 모든 경우의 수에 대한 순열을 구합니다. (이 문제의 경우 8!개)

2. 구해진 한 조합에 대해 각각의 프렌즈 들이 원하는 조건(data)가 전부 만족하는지 확인합니다.

3. 한 조건에 대해 검사를 하는 방법은 아래와 같습니다.

3-1. 조건의 0번째 인덱스와 2번째 인덱스인 두 명과, 3번째 인덱스인 오퍼레이션(<, >, =) 마지막으로 4번째 인덱스인  오퍼레이션에 대한 수를 parsing합니다.

3-2. 아래와 같은 코드로 각 조건이 만족하는지 검사합니다.

if(operation == '='){
	if(Math.abs(first - second) == num + 1)
		return true;
}
else if(operation == '>'){
	if(Math.abs(first-second) > num + 1)
		return true;
}
else{
	if(Math.abs(first-second) < num + 1)
		return true;
}
return false;

소스 코드

import java.util.*;
import java.lang.*;

class Solution {
    
    boolean visited[] = new boolean[8];
    String friends = "ACFJMNRT";
    String batch = "";
    String[] data;
    int ans = 0;
    
    public boolean checkOne(String condition){
        
        // 2명의 위치, 연산자, 숫자
        int first = batch.indexOf(condition.substring(0, 1)); 
        int second = batch.indexOf(condition.substring(2, 3));
        char operation = condition.charAt(3);
        Integer num = Integer.parseInt(condition.substring(condition.length() - 1));
        
        if(operation == '='){
            if(Math.abs(first - second) == num + 1)
                return true;
        }
        else if(operation == '>'){
            if(Math.abs(first-second) > num + 1)
                return true;
        }
        else{
            if(Math.abs(first-second) < num + 1)
                return true;
        }
        return false;
    }
    
    //전체 데이터에 대한 검사
    public boolean check(){
        
        for(int i=0;i<data.length;i++){
            if(!checkOne(data[i])) //하나라도 만족하지 않는다면
                return false;
        }
        return true;
    } 
    
    public void backTracking(int cnt){
        
        //8명의 순열이 완성되었을 때
        if(cnt == 8){
            if(check()) //전체 조건을 검사
                ans++;  //만족한다면 ans++
            return;
        }
        
        for(int i=0;i<8;i++){
            if(visited[i] == false){
                visited[i] = true;
                batch += friends.substring(i,i+1);
                backTracking(cnt + 1);
                batch = batch.substring(0, batch.length() - 1);
                visited[i] = false;
            }    
        }
    }
    
    public int solve(int n, String[] data){
        
        this.data = data;
        backTracking(0);
        return ans;
    }
    
    public int solution(int n, String[] data) {
        int answer = 0;
        return answer = solve(n, data);
    }
}

문제 설명

후보키

프렌즈대학교 컴퓨터공학과 조교인 제이지는 네오 학과장님의 지시로, 학생들의 인적사항을 정리하는 업무를 담당하게 되었다.

그의 학부 시절 프로그래밍 경험을 되살려, 모든 인적사항을 데이터베이스에 넣기로 하였고, 이를 위해 정리를 하던 중에 후보키(Candidate Key)에 대한 고민이 필요하게 되었다.

후보키에 대한 내용이 잘 기억나지 않던 제이지는, 정확한 내용을 파악하기 위해 데이터베이스 관련 서적을 확인하여 아래와 같은 내용을 확인하였다.

• 관계 데이터베이스에서 릴레이션(Relation)의 튜플(Tuple)을 유일하게 식별할 수 있는 속성(Attribute) 또는 속성의 집합 중, 다음 두 성질을 만족하는 것을 후보 키(Candidate Key)라고 한다.
  • 유일성(uniqueness) : 릴레이션에 있는 모든 튜플에 대해 유일하게 식별되어야 한다.
  • 최소성(minimality) : 유일성을 가진 키를 구성하는 속성(Attribute) 중 하나라도 제외하는 경우 유일성이 깨지는 것을 의미한다. 즉, 릴레이션의 모든 튜플을 유일하게 식별하는 데 꼭 필요한 속성들로만 구성되어야 한다.

제이지를 위해, 아래와 같은 학생들의 인적사항이 주어졌을 때, 후보 키의 최대 개수를 구하라.

위의 예를 설명하면, 학생의 인적사항 릴레이션에서 모든 학생은 각자 유일한 "학번"을 가지고 있다. 따라서 "학번"은 릴레이션의 후보 키가 될 수 있다.
그다음 "이름"에 대해서는 같은 이름("apeach")을 사용하는 학생이 있기 때문에, "이름"은 후보 키가 될 수 없다. 그러나, 만약 ["이름", "전공"]을 함께 사용한다면 릴레이션의 모든 튜플을 유일하게 식별 가능하므로 후보 키가 될 수 있게 된다.
물론 ["이름", "전공", "학년"]을 함께 사용해도 릴레이션의 모든 튜플을 유일하게 식별할 수 있지만, 최소성을 만족하지 못하기 때문에 후보 키가 될 수 없다.
따라서, 위의 학생 인적사항의 후보키는 "학번", ["이름", "전공"] 두 개가 된다.

릴레이션을 나타내는 문자열 배열 relation이 매개변수로 주어질 때, 이 릴레이션에서 후보 키의 개수를 return 하도록 solution 함수를 완성하라.

제한사항

• relation은 2차원 문자열 배열이다.
• relation의 컬럼(column)의 길이는 1 이상 8 이하이며, 각각의 컬럼은 릴레이션의 속성을 나타낸다.
• relation의 로우(row)의 길이는 1 이상 20 이하이며, 각각의 로우는 릴레이션의 튜플을 나타낸다.
• relation의 모든 문자열의 길이는 1 이상 8 이하이며, 알파벳 소문자와 숫자로만 이루어져 있다.
• relation의 모든 튜플은 유일하게 식별 가능하다.(즉, 중복되는 튜플은 없다.)

입출력 예

relationresult

입출력 예 설명

입출력 예 #1
문제에 주어진 릴레이션과 같으며, 후보 키는 2개이다.

접근 방법

문제 풀이 순서

1. 크기가 1인 조합부터 ~ n인 조합까지 순차적으로 진행

2. backTracking을 통해 크기가 i인 한 조합이 완성될 때, 최소성과 유일성을 검사한다.

3. 최소성을 보장하려면 자신보다 크기가 작은 후보키 중 자신의 부분집합이 존재하면 안된다.

4. 유일성을 보장하려면 중복되는 tuple이 존재해선 안된다.

5. 3,4번을 모두 만족한다면 후보키 목록에 현재 조합을 추가한다. 동시에 return할 값을 1증가 시킴문제 설명

후보키

프렌즈대학교 컴퓨터공학과 조교인 제이지는 네오 학과장님의 지시로, 학생들의 인적사항을 정리하는 업무를 담당하게 되었다.

그의 학부 시절 프로그래밍 경험을 되살려, 모든 인적사항을 데이터베이스에 넣기로 하였고, 이를 위해 정리를 하던 중에 후보키(Candidate Key)에 대한 고민이 필요하게 되었다.

후보키에 대한 내용이 잘 기억나지 않던 제이지는, 정확한 내용을 파악하기 위해 데이터베이스 관련 서적을 확인하여 아래와 같은 내용을 확인하였다.

관계 데이터베이스에서 릴레이션(Relation)의 튜플(Tuple)을 유일하게 식별할 수 있는 속성(Attribute) 또는 속성의 집합 중, 다음 두 성질을 만족하는 것을 후보 키(Candidate Key)라고 한다.

유일성(uniqueness) : 릴레이션에 있는 모든 튜플에 대해 유일하게 식별되어야 한다.

최소성(minimality) : 유일성을 가진 키를 구성하는 속성(Attribute) 중 하나라도 제외하는 경우 유일성이 깨지는 것을 의미한다. 즉, 릴레이션의 모든 튜플을 유일하게 식별하는 데 꼭 필요한 속성들로만 구성되어야 한다.

제이지를 위해, 아래와 같은 학생들의 인적사항이 주어졌을 때, 후보 키의 최대 개수를 구하라.



위의 예를 설명하면, 학생의 인적사항 릴레이션에서 모든 학생은 각자 유일한 "학번"을 가지고 있다. 따라서 "학번"은 릴레이션의 후보 키가 될 수 있다.

그다음 "이름"에 대해서는 같은 이름("apeach")을 사용하는 학생이 있기 때문에, "이름"은 후보 키가 될 수 없다. 그러나, 만약 ["이름", "전공"]을 함께 사용한다면 릴레이션의 모든 튜플을 유일하게 식별 가능하므로 후보 키가 될 수 있게 된다.

물론 ["이름", "전공", "학년"]을 함께 사용해도 릴레이션의 모든 튜플을 유일하게 식별할 수 있지만, 최소성을 만족하지 못하기 때문에 후보 키가 될 수 없다.

따라서, 위의 학생 인적사항의 후보키는 "학번", ["이름", "전공"] 두 개가 된다.

릴레이션을 나타내는 문자열 배열 relation이 매개변수로 주어질 때, 이 릴레이션에서 후보 키의 개수를 return 하도록 solution 함수를 완성하라.

제한사항

relation은 2차원 문자열 배열이다.

relation의 컬럼(column)의 길이는 1 이상 8 이하이며, 각각의 컬럼은 릴레이션의 속성을 나타낸다.

relation의 로우(row)의 길이는 1 이상 20 이하이며, 각각의 로우는 릴레이션의 튜플을 나타낸다.

relation의 모든 문자열의 길이는 1 이상 8 이하이며, 알파벳 소문자와 숫자로만 이루어져 있다.

relation의 모든 튜플은 유일하게 식별 가능하다.(즉, 중복되는 튜플은 없다.)

입출력 예

relationresult

[["100","ryan","music","2"],["200","apeach","math","2"],["300","tube","computer","3"],["400","con","computer","4"],["500","muzi","music","3"],["600","apeach","music","2"]] 2

입출력 예 설명

입출력 예 #1

문제에 주어진 릴레이션과 같으며, 후보 키는 2개이다.

접근 방법

문제 풀이 순서

1. 크기가 1인 조합부터 ~ n인 조합까지 순차적으로 진행

2. backTracking을 통해 크기가 i인 한 조합이 완성될 때, 최소성과 유일성을 검사한다.

3. 최소성을 보장하려면 자신보다 크기가 작은 후보키 중 자신의 부분집합이 존재하면 안된다.

4. 유일성을 보장하려면 중복되는 tuple이 존재해선 안된다.

5. 3,4번을 모두 만족한다면 후보키 목록에 현재 조합을 추가한다. 동시에 return할 값을 1증가 시킴

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

소스 코드

Java

import java.util.*;

class Solution {
    
    int ans = 0;
    String relation[][];
    HashMap <String, Boolean> visited = new HashMap<String, Boolean>(); //후보키 목록
    
    // 최소성을 만족하는지 검사
    public boolean checkMin(String seqstr){
        
        for(String elem : visited.keySet()){
            boolean flag = false;
            for(int i=0;i<elem.length();i++){
                if(seqstr.indexOf(elem.substring(i, i+1)) == -1)
                    flag = true;
            }
            if(flag == false) // 현재 조합이 후보키를 부분집합으로 가진다면
                return false;
        }
        return true;
    }
    
    // 유일성을 만족하는지 검사
    public boolean checkOnly(ArrayList<Integer> seq){
        
        HashMap <String, Boolean> map = new HashMap<String, Boolean>(); //튜플 목록
    
        for(int i=0;i<relation.length;i++){
            String key = "";
            
            for(int j=0;j<seq.size();j++)
                key += (relation[i][seq.get(j)] + ","); //i번째 튜플에, seq[j]번째 속성
            
            if(map.containsKey(key) == false) //해당 값이 없다면
                map.put(key, new Boolean(true));
            else  //중복되는 값이 있다면
                return false;
        }
        return true;
    }
    
    public void search(int n, int cnt, int now, int attr, ArrayList<Integer> seq){
        
        if(n == cnt){
        //indexOf 메소드로 포함여부를 검사하기 위해 String으로 변환
        //set이나 map 구조를 사용해도 상관없음
            String seqstr = "";
            for(int i=0; i<seq.size();i++)
                seqstr += seq.get(i).toString();
            
            if(checkMin(seqstr) && checkOnly(seq)){
                visited.put(seqstr, new Boolean(true));
                ans++;
            }
            return;
        }
        for(int i = now; i<attr; i++){
            seq.add(i);
            search(n, cnt+1, i+1, attr, seq);
            seq.remove(seq.size() - 1);
        }
    }
    
    public void solve(){
        
        ArrayList<Integer> seq = new ArrayList<Integer>();
        int attr = relation[0].length;
        int tup = relation.length;
        
        //속성의 수를 증가시킴, 작은 수 부터 확인해야 최소성을 확인하기 편함
        for(int i=1;i<=attr;i++){ 
            search(i,0,0,attr, seq);
        }
    }
    
    public int solution(String[][] relation) {
        int answer = 0;
        this.relation = relation;
        solve();
        return answer = ans;
    }
}

C++

과거에 c++로 풀었던 풀이입니다. Java와 풀이가 살짝 다릅니다.

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

using namespace std;

bool visited[8] = { false };
vector<vector<int>> combination;
int result = 0;

bool isCandidate(string &list, vector<vector<string>> &relation) {

	map<string, bool> duplicateCheck;
	for (int i = 0; i < relation.size(); i++) {
		vector<string> row = relation[i];
		string elem;
		for (int j = 0; j < list.size(); j++) {
			elem += (row[int(list[j]) - int('0')]+" ");
		}
		if (duplicateCheck.count(elem) == 0) {
			duplicateCheck.insert({elem, true});
		}
		else { //중복되는 값이 있다면
			return false;
		}
	}
	return true;
}

bool comp(vector<int> list1, vector<int> list2) {
	if (list1.size() < list2.size())
		return true;
	return false;
}

void solve(int size, int cnt, vector<int> &list, vector<vector<string>> &relation, int start) {
	if (size == cnt) {
		return;
	}
	for (int i = start; i < size; i++) {
		if (!visited[i]) {
			visited[i] = true;
			list.push_back(i);
			solve(size, cnt + 1, list, relation, i);
			combination.push_back(list);
			list.pop_back();
			visited[i] = false;
		}
	}
}

int solution(vector<vector<string>> relation) {
	
	int answer = 0;
	int col = relation[0].size();
	vector<int> list;

	result = 0;
	memset(visited, 0, sizeof(visited));
	
    //combination은 크기가 1~n까지 모든 조합이며, 크기가 작은 순부터 큰 순서로 정렬
	solve(col, 0, list, relation, 0);
	sort(combination.begin(), combination.end(), comp);

	vector<string> comb(combination.size());
	for (int i = 0; i < combination.size(); i++) {
		for (int j = 0; j < combination[i].size(); j++) {
			comb[i].push_back(char(int('0') + combination[i][j]));
		}
	}
	
	for (int i = 0; i < comb.size(); i++) {
		if (isCandidate(comb[i], relation)) {
			string tmp = comb[i];
			for (int j = 0; j < comb.size(); j++) {
				bool find = true;
				for (auto t : tmp) {
					if (comb[j].find(t) == string::npos) { // 모든요소가포함되는지 = 모두 찾는다면 = 하나라도 못찾는다면
						find = false;
						break;
					}
				}
				if (find) {
					comb.erase(comb.begin() + j);
                    j--;
				}
			}
			i--; //자기 자신도 삭제가 되므로
			result++;
		}
	}
	answer = result;
	return answer;
}

문제 설명

데이터 처리 전문가가 되고 싶은 "어피치"는 문자열을 압축하는 방법에 대해 공부를 하고 있습니다. 최근에 대량의 데이터 처리를 위한 간단한 비손실 압축 방법에 대해 공부를 하고 있는데, 문자열에서 같은 값이 연속해서 나타나는 것을 그 문자의 개수와 반복되는 값으로 표현하여 더 짧은 문자열로 줄여서 표현하는 알고리즘을 공부하고 있습니다.
간단한 예로 "aabbaccc"의 경우 "2a2ba3c"(문자가 반복되지 않아 한번만 나타난 경우 1은 생략함)와 같이 표현할 수 있는데, 이러한 방식은 반복되는 문자가 적은 경우 압축률이 낮다는 단점이 있습니다. 예를 들면, "abcabcdede"와 같은 문자열은 전혀 압축되지 않습니다. "어피치"는 이러한 단점을 해결하기 위해 문자열을 1개 이상의 단위로 잘라서 압축하여 더 짧은 문자열로 표현할 수 있는지 방법을 찾아보려고 합니다.

예를 들어, "ababcdcdababcdcd"의 경우 문자를 1개 단위로 자르면 전혀 압축되지 않지만, 2개 단위로 잘라서 압축한다면 "2ab2cd2ab2cd"로 표현할 수 있습니다. 다른 방법으로 8개 단위로 잘라서 압축한다면 "2ababcdcd"로 표현할 수 있으며, 이때가 가장 짧게 압축하여 표현할 수 있는 방법입니다.

다른 예로, "abcabcdede"와 같은 경우, 문자를 2개 단위로 잘라서 압축하면 "abcabc2de"가 되지만, 3개 단위로 자른다면 "2abcdede"가 되어 3개 단위가 가장 짧은 압축 방법이 됩니다. 이때 3개 단위로 자르고 마지막에 남는 문자열은 그대로 붙여주면 됩니다.

압축할 문자열 s가 매개변수로 주어질 때, 위에 설명한 방법으로 1개 이상 단위로 문자열을 잘라 압축하여 표현한 문자열 중 가장 짧은 것의 길이를 return 하도록 solution 함수를 완성해주세요.

제한사항

• s의 길이는 1 이상 1,000 이하입니다.
• s는 알파벳 소문자로만 이루어져 있습니다.

입출력 예

sresult

입출력 예에 대한 설명

입출력 예 #1

문자열을 1개 단위로 잘라 압축했을 때 가장 짧습니다.

입출력 예 #2

문자열을 8개 단위로 잘라 압축했을 때 가장 짧습니다.

입출력 예 #3

문자열을 3개 단위로 잘라 압축했을 때 가장 짧습니다.

입출력 예 #4

문자열을 2개 단위로 자르면 "abcabcabcabc6de" 가 됩니다.
문자열을 3개 단위로 자르면 "4abcdededededede" 가 됩니다.
문자열을 4개 단위로 자르면 "abcabcabcabc3dede" 가 됩니다.
문자열을 6개 단위로 자를 경우 "2abcabc2dedede"가 되며, 이때의 길이가 14로 가장 짧습니다.

입출력 예 #5

문자열은 제일 앞부터 정해진 길이만큼 잘라야 합니다.
따라서 주어진 문자열을 x / ababcdcd / ababcdcd 로 자르는 것은 불가능 합니다.
이 경우 어떻게 문자열을 잘라도 압축되지 않으므로 가장 짧은 길이는 17이 됩니다.

접근 방법

1. 일단 몇개의 문자열로 잘라야 최소가 되는지 모르므로 (1개~ [문자열길이/2]개)만큼 잘라보며 비교를 해야된다.

(문자열의 길이의 절반보다 큰 수로 자르게 되는 것은 압축을 할 수 없기 때문에 의미가 없다.)

int answer = s.length();
        
for(int i=1;i <= s.length()/2; i++)
	answer = Math.min(answer, findLength(s, i));

2. 문자열을 i개로 자른 단위를 s라고 한다면, 문자열  s와 s가 연속적으로 반복된 수 cnt를 저장할 수 있는 구조가 필요하다. 

  class Info{
        String s;
        Integer cnt;
        
        public Info(String s, int cnt){
            this.s = s;
            this.cnt = cnt;
        }
    }

3-1. ArrayList<Info> arr형태의 자료구조에 전체 문자열을 i개 단위로 잘라가며 저장을한다.

3-2. 만약 arr의 가장 마지막에 저장된 문자열과 현재 잘려진 문자열이 동일하다면 arr의 가장 마지막 요소의 cnt를 증가

3-3. 만약 arr의 가장 마지막 저장된 문자열과 다르다면, arr에 add 메소드로 삽입을 한다.

4. 완성된 arr의 정보를 토대로 문자열의 길이를 계산한다.

소스 코드

Java

import java.util.*;

class Solution {
    
    class Info{
        String s;
        Integer cnt;
        
        public Info(String s, int cnt){
            this.s = s;
            this.cnt = cnt;
        }
    }
    
    public int findLength(String s, int n){
        
        ArrayList<Info> arr = new ArrayList<Info>();
        
        int idx = 0;
        
        //n개 단위 문자열 처리
        while(idx + n <= s.length()){
            
            String sub = s.substring(idx, idx + n);
            
            if(arr == null || arr.size() == 0)
                arr.add(new Info(sub, 1));
            else{
                
                Info back = arr.get(arr.size() - 1);
                
                if(back.s.equals(sub))
                    back.cnt++;
                else
                    arr.add(new Info(sub, 1));
            }
            
            idx += n;
        }
        
        //압축된 문자열 길이 구하기
        int result = 0;
        
        for(int i=0;i<arr.size();i++){
            Info info = arr.get(i);
            result += info.s.length();
            if(info.cnt > 1)
                result += info.cnt.toString().length();
        }
        return result + (s.length() - idx);
    }
    
    public int solution(String s) {
        int answer = s.length();
        
        for(int i=1;i <= s.length()/2; i++)
            answer = Math.min(answer, findLength(s, i));
        
        return answer;
    }
}

C++

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int strLength(string s, int psize) {
	
	vector <pair<int, string>> patterns;
	int result = 0;
	int nonepattern = s.size();

	int i = 0;
	while (i < s.size() - psize){
		if (s.substr(i, psize).compare(s.substr(i + psize, psize)) == 0) {
			if (patterns.empty() || patterns.back().second.compare(s.substr(i, psize)) != 0)
				patterns.push_back({ 2, s.substr(i, psize) });
			else
				patterns.back().first += 1;

			if (s.substr(i + psize, psize).compare(s.substr(i + 2 * psize, psize)) == 0)
				i += psize;
			else
				i += 2 * psize;
		}
		else
			i+= psize;
	}
	
	for (int i = 0; i < patterns.size(); i++) {
		pair<int, string> pattern = patterns[i];
		int cnt = to_string(pattern.first).size();
		result += (cnt + psize);
		nonepattern -= (pattern.first*psize);
	}
	return result + nonepattern;
}

int solution(string s) {
	int answer = 0;
	int minimum = s.size();
	for (int i = 1; i < s.size()/2 + 1; i++) {
		minimum = min(minimum, strLength(s, i));
	}
	return answer = minimum;
}