프로그래머스 - 후보키

김준영·2024년 7월 15일

자바 코테 프로그래머스

프로그래머스

목록 보기

11/19

문제 링크 ▶︎ 프로그래머스 후보키

문제 파악

relation 배열의 예시를 보면 모든 데이터가 String으로 받아져있기 때문에 만약 후보키가 두개의 컬럼으로 합쳐진다면 그냥 두개 String 합쳐서 유일성을 보장해주는지 체크하면 될 것 같다고 생각했다.

기본적인 구현 틀은 한개의 키를 쓸건지, 두개의 키를 쓸건지 즉, 몇개의 키를 쓸건지에 대한 반복문 안에 키를 합쳐서 모든 행을 검사해서 유일성을 보장해주냐를 체크하고 그렇다면 이 키가 최소성을 보장해주냐 를 체크해야할 것 같다.

그리고 어떠한 열의 조합으로 유일성과 최소성을 만족할 수 있는지를 찾기위해서 이차원 리스트에 매 순간 일차원 리스트를 추가하고 만약에 중복이면 추가안하는 식으로 구현해야 할 것같다.

유일성을 보장해주는 지를 찾는 함수와 최소성을 보장해주는 지를 찾는 두가지 함수를 모두 가지고있어야 할듯 하다.

문제 이해는 잘되지만 구현에는 어려움을 겪을 것 같다. 구현이 복잡할듯..

접근 방법

후보키를 모두 모은 이차원배열 keys를 만든다. 만약 0번째 열이 키, 1번째+2번째 열이 키라면 [[0],[1,2]] 이렇게 저장되는 형태이다. 또한 몇개의 키를 사용해서 후보키를 찾을거냐가 관건이므로 cnt=1부터 반복문을 수행해주고, 현재의 cnt로 만드는 후보키들을 담을 now 일차원 리스트와 방문 배열 visit도 매번 생성해준 후 dfs를 호출한다.
dfs에서는 키의 갯수인 cnt, 시작과 끝인 start, end 그리고 now, kwys, relation,visit을 인자로 받는다. 좀 더 깔끔하게 몇개는 전역변수로 선언해서 하려다가 일단 다 인자로 받아서 해결해보고 다시 수정하자는 식으로 풀었다.
dfs내부에서는 종료조건은 현재 열들의 조합으로 만들어진 now 리스트의 길이가 cnt가 만족되고 그것들이 유일성을 보장하면, 또한 기존의 후보키들 중에서 현재 키 조합보다 더 적은 수로 만든게 없는지 즉 최소성을 만족하는지 까지 체크해서 모두 만족하면 정답인 keys 이차원 리스트에 추가하고 리턴한다. 여기에서 최소성을 검사하는 것은 기존의 keys에 들어있는 일차원 리스트 중 현재 now에 포함되는 리스트인지를 검사해야하는데 이때 containsAll 을 쓰는 것이 중요하다. 왜냐면 오브젝트를 검사하는 것이기 때문이다.
구현 내부에서는 start~end까지 돌면서 방문하지 않은 인덱스를 방문해주고 now에 해당 인덱스를 추가하고, 다음 인덱스를 검사하고 돌아오면 다시 now에서 지워준다. 그리고 재귀가 돌아오면 원상복구시킨다.
isKey 라는 현재 키 조합이 유일성을 보장해주는지를 검사하는 함수는 HashSet을 만들어두고 릴레이션의 전체 행을 모두 검사할 것인데, now에 담긴 index의 열 데이터들을 StringBuilder로 문자열을 합쳐서 볼 것이다. 그렇다면 아무리 여러개의 열이 합쳐져도 하나의 요소로 볼 수 있고 유일성 체크도 가능하기 때문이다.
sb에다가 합쳐서 담아넣고 Set에 집어넣을 것이다. 그렇다면 이때 릴레이션의 행 길이와 set.size()가 같다면 이 키들의 조합은 유일성을 보장해준다.

코드 구현

import java.util.*;
class Solution {
    public int solution(String[][] relation) {
        int answer = 0;
        int col = relation[0].length;
        int row = relation.length;
        List<List<Integer>> keys = new ArrayList<>(); //열의 조합들을 다 모은 이차원배열
        for(int cnt=1; cnt<=col; cnt++) { //몇개의 속성(열)의 조합
            List<Integer> now = new ArrayList<>(); //이번턴의 열 조합
            boolean[] visit = new boolean[col]; //방문체크
            dfs(cnt,0,col,now,keys,relation,visit);
        }
        answer = keys.size();
        return answer;
    }
    
    public void dfs(int cnt, int start, int end, List<Integer> now, List<List<Integer>> keys, String[][] relation, boolean[] visit) {
        if(now.size() == cnt && isKey(now, relation)) {
            for (List<Integer> one : keys) {
                if(now.containsAll(one)){
                    return;
                }
            }
            keys.add(new ArrayList<>(now));
            return;
        }
        for (int i=start; i<end; i++) {
		        if(!visit[i]){
				        visit[i] = true;
		            now.add(i);
		            dfs(cnt,i+1,end,now,keys,relation,visit);
		            visit[i] = false;
		            now.remove(now.size()-1);
            }
        }
    }
    public boolean isKey(List<Integer> now, String[][] relation) {
        Set<String> set = new HashSet<>();
        for (String[] row : relation) {
            StringBuilder sb = new StringBuilder();
            for (int idx : now) {
                sb.append(row[idx]);
            }
            set.add(sb.toString());
        }
        return relation.length == set.size();
       
        }
    }
}

개선 사항

구현이 굉장히 어려운 문제인 것 같다. 머릿속으로 이렇게 저렇게 풀어야겠다 생각할 수 는 있었으나 구현에 있어서 복잡함이 많은 코드를 짠 것 같다. 최소성을 보장하는지 체크하는 부분에서 처음에는 constainsAll 이 아니라 constains를 사용했었는데 이 부분에 대해서 constains 와 containsAll의 차이를 배운 것 같다.

그리고 dfs의 base case를 만드는 과정에서의 조건이 너무 복잡해서 이 부분을 구현하고 정리하는 데에 시간이 꽤 많이 걸렸다. 제일 어려웠던 것 같다.

김준영

junyoun9dev@gmail.com

이전 포스트

프로그래머스 - 소수 찾기

다음 포스트

프로그래머스 - 후보키