데이터 집합에서 특정 값을 가진 요소를 찾아내는 작업이 검색인데 기본적인 검색 법으로 선형검색, 이진검색, 해시법에 대해 정리해본다. 검색 작업은 결국 비용이 들어가기 때문에 가능한 저렴한 비용의 검색법을 적용해야 하는데 어떤 검색법이 적절할지는 자료구조에 따라 다를 수 있다.
각 검색법의 적절한 활용법은 아래와 같다.
선형 검색 - 무작위의 데이터 집합에서 검색을 수행할 경우
이진 검색 - 일정한 규칙으로 정렬되어 있는 데이터 집합에서 검색을 수행할 경우
해시법 - 추가, 삭제가 자주일어나는 경우
선형 검색
모든 데이터를 하나씩 확인하는 가장 기본적인 검색 방법. 원하는 데이터를 찾을때까지 검색을 수행하기 때문에 최대 n의 복잡도를 같는다. 성능향상을 위해 보초법을 적용하면 비용을 절약할 수 있다.
기본적으로 선형 검색에서는 모든 데이터를 처음부터 마지막 데이터까지 하나씩 선택하며 검색하며 아래 과정으로 실행한다.
1. 데이터집합에서 마지막 데이터까지 검색을 다 해봤는지 확인한다.
2. 현재 선택된 데이터가 찾는 데이터인지 확인한다.
3. 1,2를 반복하며 마지막까지 찾는 데이터가 없다면 데이터 집합에 해당 데이터가 없으므로 검색을 종료한다.
위 방법으로 선형검색을 실행하면 데이터의 1,2 과정에서 매번 if문을 호출해야하기 때문에 최대 데이터갯수*2 번의 if문을 실행해야 한다. 이 비용을 줄이기 위한것이 보초법인데, 보초법은 아래와 같이 실행한다.
1. 데이터 집합 마지막에 찾는 데이터를 삽입한다.
2. 매번 현제 데이터가 찾는 데이터인지 확인한다.
3. 찾는 데이터가 발견되면 해당 데이터의 인덱스를 확인하고, 해당 인덱스가 마지막이라면 찾는 데이터가 없는 것으로 검색을 종료한다.
(마지막 인덱스에 존재하는 데이터는 데이터 집합에 존재하던 것이 아니라 1. 과정에서 삽입한 데이터이다.)
선형 검색 예제
import java.util.Scanner;
public class SeqSearchSen {
static int seqSearchSen(int[] arr, int num, int key) {
int i=0;
while(true) {
if(i==num) {
return -1;
}
if(arr[i] == key) {
return i;
}
i++;
}
/* 보초법을 활용한 경우
for(; i<arr.length; i++) {
if(arr[i]==key) {
break;
}
}*/
return (i==num)? -1 : i;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.print("배열의 길이를 입력하세요 : ");
int num = Integer.parseInt(sc.nextLine());
int[] arr = new int[num+1];
for(int i=0; i<arr.length-1; i++) {
System.out.print((i+1)+"번째 값 : ");
arr[i] = Integer.parseInt(sc.nextLine());
}
System.out.print("검색할 값 : ");
int key = Integer.parseInt(sc.nextLine());
arr[num] = key;
int result = seqSearchSen(arr,num,key);
if(result==-1) {
System.out.println("찾는 값이 없습니다.");
} else {
System.out.println(key+"은(는) "+(result+1)+"번째에 있습니다.");
}
sc.close();
}
}
이진 검색
이진검색의 전제조건은 상술한대로 정렬이 되어 있다는 점인데, log n의 복잡도를 갖기 때문에 비용이 훨씬 저렴하다.
검색 방법은 아래와 같다.
1. 정렬이 되어있기 때문에 최소, 최대값은 index 0와 끝번호이다. 이 두 값과 중앙값 = (최소+최대)/ 2 을 저장한다.
2. 찾는 값과 중앙값을 비교해서
2-1. 찾는 값이 중앙값 보다 크다면 최소값 인덱스를 중앙값+1로 갱신한다.
2-2. 찾는 값이 중앙값보다 작다면 최대값 인덱스를 중앙값-1로 갱신한다.
3. 1,2 과정을 반복하다가 최소값>최대값의 상황이 발생하면 데이터 집합에 찾는 데이터가 없는 경우로 검색을 종료한다.
이진 검색 예제 코드
import java.util.Scanner;
public class BinSearch {
static int binSearch(int[] arr, int num, int key) {
int pl = 0;
int pr = num-1;
int pc;
while(pl<=pr) {
pc = (pr+pl)/2;
if(arr[pc]==key) {
return pc;
} else if(arr[pc]>key) {
pr = pc-1;
} else {
pl = pc+1;
}
}
return -1;
}
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner sc = new Scanner(System.in);
System.out.print("배열의 길이를 입력하세요 : ");
int num = Integer.parseInt(sc.nextLine());
int[] arr = new int[num];
System.out.println("값을 오름차순으로 입력하세요.");
System.out.print("1번째 값 : ");
arr[0] = Integer.parseInt(sc.nextLine());
for(int i=1; i<arr.length; i++) {
System.out.print((i+1)+"번째 값 : ");
arr[i] = Integer.parseInt(sc.nextLine());
while(arr[i]<arr[i-1]) {
System.out.println("이전 보다 큰 값을 입력하세요.");
System.out.print((i+1)+"번째 값 : ");
arr[i] = Integer.parseInt(sc.nextLine());
}
}
System.out.print("검색할 값을 입력하세요 : ");
int key = Integer.parseInt(sc.nextLine());
int result = binSearch(arr, num, key);
if(result==-1) {
System.out.println("찾는 값이 업습니다.");
} else {
System.out.println(key+ "은(는) "+ (result+1) + "번째에 있습니다.");
}
sc.close();
}
}
프렌즈 블록이라는 신규 게임이 출시되었고, 어마어마한 상금이 걸린 이벤트 대회가 개최 되었다.
이 대회는 사람을 대신해서 플레이할 프로그램으로 참가해도 된다는 규정이 있어서, 게임 실력이 형편없는 프로도는 프로그램을 만들어서 참가하기로 결심하고 개발을 시작하였다.
프로도가 우승할 수 있도록 도와서 빠르고 정확한 프로그램을 작성해 보자.
게임규칙
아래 그림과 같이 1×1 크기의 블록을 이어 붙여 만든 3 종류의 블록을 회전해서 총 12가지 모양의 블록을 만들 수 있다.
1 x 1 크기의 정사각형으로 이루어진 N x N 크기의 보드 위에 이 블록들이 배치된 채로 게임이 시작된다. (보드 위에 놓인 블록은 회전할 수 없다). 모든 블록은 블록을 구성하는 사각형들이 정확히 보드 위의 사각형에 맞도록 놓여있으며, 선 위에 걸치거나 보드를 벗어나게 놓여있는 경우는 없다.
플레이어는 위쪽에서 1 x 1 크기의 검은 블록을 떨어뜨려 쌓을 수 있다. 검은 블록은 항상 맵의 한 칸에 꽉 차게 떨어뜨려야 하며, 줄에 걸치면 안된다. 이때, 검은 블록과 기존에 놓인 블록을 합해속이 꽉 채워진직사각형을 만들 수 있다면 그 블록을 없앨 수 있다.
예를 들어 검은 블록을 떨어뜨려 아래와 같이 만들 경우 주황색 블록을 없앨 수 있다.
빨간 블록을 가로막던 주황색 블록이 없어졌으므로 다음과 같이 빨간 블록도 없앨 수 있다.
그러나 다른 블록들은 검은 블록을 떨어뜨려 직사각형으로 만들 수 없기 때문에 없앨 수 없다.
따라서 위 예시에서 없앨 수 있는 블록은 최대 2개이다.
보드 위에 놓인 블록의 상태가 담긴 2차원 배열 board가 주어질 때, 검은 블록을 떨어뜨려 없앨 수 있는 블록 개수의 최댓값을 구하라.
제한사항
board는 블록의 상태가 들어있는 N x N 크기 2차원 배열이다.
N은4이상50이하다.
board의 각 행의 원소는0이상200이하의 자연수이다.
0 은 빈 칸을 나타낸다.
board에 놓여있는 각 블록은 숫자를 이용해 표현한다.
잘못된 블록 모양이 주어지는 경우는 없다.
모양에 관계 없이 서로 다른 블록은 서로 다른 숫자로 표현된다.
예를 들어 문제에 주어진 예시의 경우 다음과 같이 주어진다.
나의 풀이
문제 풀이의 핵심은, 2*3박스 or 3*2박스 안에서 없앨 수 있는 모형(4개의 블럭으로 이루어진 모양을 모형이라 칭하기로)이 있느냐를 체크하는 것이었다. 순서를 나열해보면
1. 매번 2*3, 3*2 박스에서 좌상단 블럭을 기준으로 해당 박스 안에서 없앨 수 있는 모형이 있는지 체크한다.
2. 모형을 하나 제거할 경우 다른 모형이 제거가 가능해졌을 수 도 있으므로, 전체 보드를 다시 스캔한다.
이 두 가지가 핵심 방법이다.
1번 제거할 수 있는 모형인지 체크는 find() 메서드로 블럭의 크기를 지정해 준 후에 h*w = 6칸의 박스에서 4개는 같은 수가 있고 나머지 2개는 0의 값인지(=공백인지) 체크한다. 그리고 0의 블럭(=공백)은 체울 수 있는지 canFill() 메서드로 체크한다.
공백 블럭을 체울 수 있는지는 보드에서 해당 블럭의 상단이 모두 공백일 경우만 가능하다 보고, 공백 블럭의 위치를 파라미터로 canFill() 메서드로 상단이 비어있는지만 확인해준다.
2번 모형을 하나 제거할 경우 다른 모형이 제거가 가능해졌을 수 도 있으니 다시 전체 스캔은 do while문으로 반복한다. 만약 전체 보드를 끝까지 스캔했는데 제거된 모형이 없는 경우, 전체 보드에서 추가적으로 제거할 수 있게된 모형도 없으므로 종료한다.
//코드에 주석으로 풀이를 추가했다.
전체 코드
class Solution {
int N;
int[][] Board;
//채울수 있는지 확인. 해당 블럭 위가 모두 비어있으면 가능하다.
boolean canFill(int row, int col) {
for(int i=0; i<row; i++) {
if(Board[i][col] != 0) return false;
}
return true;
}
//현재 블럭을 기준으로 h*w 만큼 박스 안에서 모형을 지울 수 있는지 검사
boolean find(int row, int col, int h, int w) {
int emptyCnt = 0;
int lastVal = -1;
for(int r = row; r < row+h; r++) {
for(int c = col; c<col+w; c++) {
if(Board[r][c] == 0) {
//(r,c) 블럭이 0이면서 지울 수 있는지 체크, 지울 수 없다면 리턴 false
if(!canFill(r,c)) return false;
//현재 w*h 크기 박스에서 빈공간이 2개를 초과한다면 리턴 false;
if(++emptyCnt > 2) return false;
} else {
//(r,c) 블럭이 0이 아닌 경우,
// w*h 블럭 안에서 다른 숫자가 2개 이상 나온 경우 리턴 false;
if((lastVal!= -1) && (lastVal!=Board[r][c]))
return false;
lastVal = Board[r][c];
}
}
}
//박스가 모두 체워지면 모형이 없어지기 때문에 0으로 값을 변경한다.
for(int r = row; r < row+h; r++) {
for(int c = col; c < col+w; c++) {
Board[r][c] = 0;
}
}
return true;
}
public int solution(int[][] board) {
Board = board;
N = board.length;
int cnt;
int answer = 0;
//하나의 모형이 삭제되었을때, 삭제가 불가능하던 모형이 삭제가 가능해질 수 있다.
//따라서 모형이 하나라도 삭제될 경우 보드 전체 범위를 다시 스캔한다.
do{
cnt = 0;
for(int i=0; i<N; i++) {
for(int j = 0; j<N; j++) {
//세로(row수)2, 가로(col수)3 의 박스를 검사
if(i<=N-2 && j<=N-3 && find(i,j, 2, 3)) {
cnt++;
}
//세로(row수)3, 가로(col수)2 의 박스를 검사
else if(i<=N-3 && j<=N-2 && find(i,j,3,2)) {
cnt++;
}
}
}
answer += cnt;
} while(cnt != 0);
return answer;
}
}
이번 문제는 개인적으로 2019 카카오 코딩 테스트 문제중에 제일 어려웠다... Level 4 문제보다 어렵게 느껴졌는데, 처음 접근은 맞게 했는데 도중에 문자열 처리에서 애를 먹었다. 처음 보는 메서드로 쉽게 해결이 가능한 부분이었는데 이 부분은 다른 사람의 코드를 풀어보면서 알게 된 부분.
문제 설명
매칭 점수
프렌즈 대학교 조교였던 제이지는 허드렛일만 시키는 네오 학과장님의 마수에서 벗어나, 카카오에 입사하게 되었다. 평소에 관심있어하던 검색에 마침 결원이 발생하여, 검색개발팀에 편입될 수 있었고, 대망의 첫 프로젝트를 맡게 되었다. 그 프로젝트는 검색어에 가장 잘 맞는 웹페이지를 보여주기 위해 아래와 같은 규칙으로 검색어에 대한 웹페이지의 매칭점수를 계산 하는 것이었다.
한 웹페이지에 대해서 기본점수, 외부 링크 수, 링크점수, 그리고 매칭점수를 구할 수 있다.
한 웹페이지의 기본점수는 해당 웹페이지의 텍스트 중, 검색어가 등장하는 횟수이다. (대소문자 무시)
한 웹페이지의 외부 링크 수는 해당 웹페이지에서 다른 외부 페이지로 연결된 링크의 개수이다.
한 웹페이지의 링크점수는 해당 웹페이지로 링크가 걸린 다른 웹페이지의 기본점수 ÷ 외부 링크 수의 총합이다.
한 웹페이지의 매칭점수는 기본점수와 링크점수의 합으로 계산한다.
예를 들어, 다음과 같이 A, B, C 세 개의 웹페이지가 있고, 검색어가 hi라고 하자.
이때 A 웹페이지의 매칭점수는 다음과 같이 계산할 수 있다.
기본 점수는 각 웹페이지에서 hi가 등장한 횟수이다.
A,B,C 웹페이지의 기본점수는 각각 1점, 4점, 9점이다.
외부 링크수는 다른 웹페이지로 링크가 걸린 개수이다.
A,B,C 웹페이지의 외부 링크 수는 각각 1점, 2점, 3점이다.
A 웹페이지로 링크가 걸린 페이지는 B와 C가 있다.
A 웹페이지의 링크점수는 B의 링크점수 2점(4 ÷ 2)과 C의 링크점수 3점(9 ÷ 3)을 더한 5점이 된다.
그러므로, A 웹페이지의 매칭점수는 기본점수 1점 + 링크점수 5점 = 6점이 된다.
검색어 word와 웹페이지의 HTML 목록인 pages가 주어졌을 때, 매칭점수가 가장 높은 웹페이지의 index를 구하라. 만약 그런 웹페이지가 여러 개라면 그중 번호가 가장 작은 것을 구하라.
제한사항
pages는 HTML 형식의 웹페이지가 문자열 형태로 들어있는 배열이고, 길이는1이상20이하이다.
한 웹페이지 문자열의 길이는1이상1,500이하이다.
웹페이지의 index는 pages 배열의 index와 같으며 0부터 시작한다.
한 웹페이지의 url은 HTML의 <head> 태그 내에 <meta> 태그의 값으로 주어진다.
검색어 word는 하나의 영어 단어로만 주어지며 알파벳 소문자와 대문자로만 이루어져 있다.
word의 길이는1이상12이하이다.
검색어를 찾을 때, 대소문자 구분은 무시하고 찾는다.
예를들어 검색어가 blind일 때, HTML 내에 Blind라는 단어가 있거나, BLIND라는 단어가 있으면 두 경우 모두 해당된다.
검색어는 단어 단위로 비교하며, 단어와 완전히 일치하는 경우에만 기본 점수에 반영한다.
단어는 알파벳을 제외한 다른 모든 문자로 구분한다.
예를들어 검색어가aba일 때,abab abababa는 단어 단위로 일치하는게 없으니, 기본 점수는 0점이 된다.
만약 검색어가aba라면,aba@aba aba는 단어 단위로 세개가 일치하므로, 기본 점수는 3점이다.
결과를 돌려줄때, 동일한 매칭점수를 가진 웹페이지가 여러 개라면 그중 index 번호가 가장 작은 것를 리턴한다
즉, 웹페이지가 세개이고, 각각 매칭점수가 3,1,3 이라면 제일 적은 index 번호인 0을 리턴하면 된다.
나의 풀이
주어진 배열에서 각 문자열이 html 페이지이기 때문에, 각 문자열로 page라는 객체를 만들자 생각하고 접근하였다.
문제는 페이지 객체가 가져야 할 속성으로 자체점수, 링크 수는 처음부터 고정적인데 링크점수와 링크점수를 포함한 매칭 점수는 다른 페이지 객체에게 영향을 받는 다는 점이었다. 내가 헤맸던 부분이 바로 한 페이지가 링크된 다른 페이지에 전달하는 링크 점수는 연쇄적이지 않기 때문에 링크되지 않은 다른페이지에는 전혀 영향을 주진 않는다. 라는 부분을 빠르게 캐치하지 못한 부분이다.
결과적으론
1. 모든 페이지 객체를 생성한 후,
2. 각 페이지 객체를 가지고 기본점수/링크수 로 다른 페이지에 점수를 더해주기만 하면 되었다.
여기까지가 구조적인 접근이었고, 다음은 문자열 처리가 문제였다.
url 자체를 구하는 건 String 객체의 indexOf() 메서드로 쉽게 생각했는데 기본 점수를 어떻게 계산해야 할지가 문제였다. 주어진 단어의 앞뒤가 공백이나 특문 등이 와야 했는데 처음에는 주어진 단어가 찾아지면 바로 앞, 뒤 문자(char)를 int형으로 변형해 아스킷 값으로 a~Z사이의 범위에 들어오는지 확인해야 겠다 생각하고 코드를 구현하려다가 너무 지저분한 코드가 되는데? 싶었다. 그리고 다른 사람 코드에서 Character 클래스에 isLetter() 라는 메서드가 그 기능을 이미 제공하고 있는 걸 발견하고 해당 메서드를 사용했다.
전무로 승진한 라이언은 기분이 너무 좋아 프렌즈를 이끌고 특별 휴가를 가기로 했다. 내친김에 여행 계획까지 구상하던 라이언은 재미있는 게임을 생각해냈고 역시 전무로 승진할만한 인재라고 스스로에게 감탄했다.
라이언이 구상한(그리고 아마도 라이언만 즐거울만한) 게임은, 카카오 프렌즈를 두 팀으로 나누고, 각 팀이 같은 곳을 다른 순서로 방문하도록 해서 먼저 순회를 마친 팀이 승리하는 것이다.
그냥 지도를 주고 게임을 시작하면 재미가 덜해지므로, 라이언은 방문할 곳의 2차원 좌표 값을 구하고 각 장소를 이진트리의 노드가 되도록 구성한 후, 순회 방법을 힌트로 주어 각 팀이 스스로 경로를 찾도록 할 계획이다.
라이언은 아래와 같은 특별한 규칙으로 트리 노드들을 구성한다.
트리를 구성하는 모든 노드의 x, y 좌표 값은 정수이다.
모든 노드는 서로 다른 x값을 가진다.
같은 레벨(level)에 있는 노드는 같은 y 좌표를 가진다.
자식 노드의 y 값은 항상 부모 노드보다 작다.
임의의 노드 V의 왼쪽 서브 트리(left subtree)에 있는 모든 노드의 x값은 V의 x값보다 작다.
임의의 노드 V의 오른쪽 서브 트리(right subtree)에 있는 모든 노드의 x값은 V의 x값보다 크다.
아래 예시를 확인해보자.
라이언의 규칙에 맞게 이진트리의 노드만 좌표 평면에 그리면 다음과 같다. (이진트리의 각 노드에는 1부터 N까지 순서대로 번호가 붙어있다.)
이제, 노드를 잇는 간선(edge)을 모두 그리면 아래와 같은 모양이 된다.
위 이진트리에서 전위 순회(preorder), 후위 순회(postorder)를 한 결과는 다음과 같고, 이것은 각 팀이 방문해야 할 순서를 의미한다.
전위 순회 : 7, 4, 6, 9, 1, 8, 5, 2, 3
후위 순회 : 9, 6, 5, 8, 1, 4, 3, 2, 7
다행히 두 팀 모두 머리를 모아 분석한 끝에 라이언의 의도를 간신히 알아차렸다.
그러나 여전히 문제는 남아있다. 노드의 수가 예시처럼 적다면 쉽게 해결할 수 있겠지만, 예상대로 라이언은 그렇게 할 생각이 전혀 없었다.
이제 당신이 나설 때가 되었다.
곤경에 빠진 카카오 프렌즈를 위해 이진트리를 구성하는 노드들의 좌표가 담긴 배열 nodeinfo가 매개변수로 주어질 때, 노드들로 구성된 이진트리를 전위 순회, 후위 순회한 결과를 2차원 배열에 순서대로 담아 return 하도록 solution 함수를 완성하자.
제한사항
nodeinfo는 이진트리를 구성하는 각 노드의 좌표가 1번 노드부터 순서대로 들어있는 2차원 배열이다.
nodeinfo의 길이는1이상10,000이하이다.
nodeinfo[i] 는 i + 1번 노드의 좌표이며, [x축 좌표, y축 좌표] 순으로 들어있다.
모든 노드의 좌표 값은0이상100,000이하인 정수이다.
트리의 깊이가1,000이하인 경우만 입력으로 주어진다.
모든 노드의 좌표는 문제에 주어진 규칙을 따르며, 잘못된 노드 위치가 주어지는 경우는 없다.
나의 풀이
문제를 보고 바로 이진 트리 구조, 깊이 우선 검색 두 가지가 딱 보였다. 주어지는 지점들을 노트 객체로 생성하고, 부모 자식 간 관계를 연결해주면 되는 문제였다. 노트와 트리 구조를 만드는건 오히려 간단했고, 전위/후위 결과를 어떻게 저장해야 하는지 제대로 공부가 안되어있어서 고민을 좀 했다. Level3 문제인데 이진트리나 dfs 기법 등 연습했었던 접근법으로 쉽게 풀려서 오히려 쉽게 느껴졌다.
아쉬운 점은 재귀함수가 아니라 스택과 반복문을 이용한 방법으로도 문제를 풀어봤는데 답이 틀려서 다시 풀어봐야 할듯하다ㅠ
전체 코드
import java.util.*;
class Solution {
class Node {
int num;
int x;
int y;
Node left;
Node right;
Node(int num, int x, int y) {
this.num = num;
this.x = x;
this.y = y;
}
}
void insert_In_Tree(Node parent, Node n) {
if(n.x < parent.x) {
if(parent.left != null)
insert_In_Tree(parent.left, n);
else
parent.left = n;
} else {
if(parent.right != null)
insert_In_Tree(parent.right, n);
else
parent.right = n;
}
}
void preorder(int[][] answer, Node n) {
if(n == null) return;
answer[0][idx++] = n.num;
preorder(answer, n.left);
preorder(answer, n.right);
}
void postorder(int[][] answer, Node n) {
if(n==null) return;
postorder(answer, n.left);
postorder(answer, n.right);
answer[1][idx++] = n.num;
}
int idx;
public int[][] solution(int[][] nodeinfo) {
List<Node> list = new ArrayList<>();
//Node를 생성해서 list에 저장
for(int i=0; i< nodeinfo.length; i++) {
list.add(new Node(i+1, nodeinfo[i][0], nodeinfo[i][1]));
}
//Node list를 y가 크고, x가 작은 순으로 정렬
list.sort(new Comparator<Node>(){
public int compare(Node n1, Node n2) {
if(n1.y == n2.y)
return n1.x - n2.x;
return n2.y - n1.y;
}
});
//이진 트리 구성
Node root = list.get(0);
for(int i=1; i<list.size(); i++) {
insert_In_Tree(root, list.get(i));
}
int[][] answer = new int[2][list.size()];
//전위 순회 결과 answer[0]에 대입
idx = 0;
preorder(answer, root);
//후위 순회 결과 answer[1]에 대입
idx = 0;
postorder(answer,root);
return answer;
}
}
프렌즈대학교 컴퓨터공학과 조교인 제이지는 네오 학과장님의 지시로, 학생들의 인적사항을 정리하는 업무를 담당하게 되었다.
그의 학부 시절 프로그래밍 경험을 되살려, 모든 인적사항을 데이터베이스에 넣기로 하였고, 이를 위해 정리를 하던 중에 후보키(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의 모든 튜플은 유일하게 식별 가능하다.(즉, 중복되는 튜플은 없다.)
나의 풀이
이 문제는 생각보다 쉽게 접근한 부분도 있고, 구현하면서 애를 먹은 부분도 있는 문제였다. 막힌 부분은 다른 사람의 코드를 해석하면서 풀어나갔는데도 어려웠던 문제. 이 문제에서 중요한 점은 바로 유일성과 최소성을 파악하는 점인데 이를 한번에 해결하려 하니 손을 대기가 어려웠다. 그래서 이를 분리해서 먼저 유일성을 만족하는 모든 경우의 수를 찾고, 최소성을 만족하지 못하는 경우의 수를 제거하는 방법으로 문제풀이를 접근 했다.
문제 풀이에서 필요한 개념은
Bitmask - 2진법으로 집합을 표현하는 방법이다.
& - 비트 연산자로 포함관계를 파악할 수 있다. ( (int)1 = (bin)0001, (int)3 = (bin)0011 , 1(0001) & 3(0011) = 1 )
아래는 내가 문제풀이에 접근했던 내용을 정리했다.
후보키는 컬럼의 조합(혹은 단일컬럼)으로 이루어져 있는데, 각 컬럼의 조합은 한정되어 있다.
컬럼의 갯수 n 이면 최대 조합은 2^n -1 가지이다. 이를 풀어서 말해보면
1개의 컬럼만으로 이루어진 후보키라면 최대 n가지만 있을 것이고,
2개의 컬럼으로 이루어진 후보키라면 (n-1)*(n-2) 가지가 있을 것,
3개의 컬럼으로 이루어진 후보키라면 (n-1)*(n-2)*(n-3) 가지가 있을 것이다.
...
n개의 컬럼으로 이루어진 후보키는 1가지만 있을 것이다.
예시를 들어 표로 표현해보면 아래 4가지 컬럼으로 이루어진 테이블은 어떤 컬럼을 선택해서 조합하냐에 따라 1부터 16까지 (표에선 1을 아무것도 선택 안하는 경우로 넣음) 숫자로 표현하거나, 이를 2진수로 표현할 수도 있다.
하나의 컬럼만 선택해서 후보키를 만들경우 2진수로 표현하면 0001, 0010, 0100, 1000 과 같이 표현할 수 있겠다. 라는 생각이 의외로 쉽게? 들었다. 그리고 다른 사람의 풀이를 보니 이런 기법을 Bitmask라 부르며 2진법으로 집합을 표현하는 경우라고 한다.
위와 같이 나올 수 있는 모든 경우의 수를 가지고 먼저 다른 튜플(로우)와 겹치는게 없는지 유일성을 체크했다. 유일성이 만족되면 list에 넣어 놓는다. 코드에선 아래 부분이다.
for(int i=1; i< (1 << column_num); i++) { // 모든 경우의 수로 유일성을 체크한다.
if(check(relation, row_num, column_num, i)) {
candidates.add(i);
}
}
/* ----------------------------------------------------------------------*/
//유일성을 체크하는 메서드. subset이 1~16 (컬럼수가 4일때) 중에서 이번차례 경우의수를 가지고 온다.
boolean check(String[][] relation, int row_num, int col_num, int subset) {
for(int i = 0; i < row_num -1; i++) {
for(int j = i+1; j < row_num; j++) {
boolean isSame = true;
for(int k=0; k < col_num; k++) {
if((subset & (1 << k))==0) // 이번 경우의 수가 아니면 넘어간다.
continue;
// 이번 경우의 수(컬럼 조합)으로 다른 로우의 값과 비교한다.
// 다른 로우와 일치하면 이 경우의 수(컬럼 조합)는 유일성을 만족하지 못한는 것이다.
if(!relation[i][k].equals(relation[j][k])) {
isSame = false;
break;
}
}
if(isSame) return false; //유일성 만족이 실패했다.
}
}
return true; //이번 경우의 수(컬럼 조합)로 다른 어떤 로우와도 동일한 값이 없으니 유일성 만족.
}
list에 들어 있는 유일성 체크를 통과한 경우의 수들로 (컬럼의 수가 적게 구성된 경우의 수) & (더 많은 컬럼의 수로 구성된 경우의 수) 연산을 해서 최소성을 체크하도록 했다. 코드에선 아래 부분이다.
while(candidates.size()!=0) { //리스트에서 하나씩 꺼내면서 최소성을 확인한다.
int n = candidates.remove(0); //젤 앞에 있는 경우의 수는 무조건 최소성을 만족한다.
answer++;
for(Iterator<Integer> it = candidates.iterator(); it.hasNext(); ) {
int c = it.next();
//현재 선택된 경우의 수 n과 다른 모든 경우의 수 c를 &연산한다.
//c가 n을 포함한 경우는 c는 최소성을 만족하지 못하기 때문에 list에서 제거한다.
//ex) n = 0001, c = 0101일때 0001 & 0101 == 0001, 0101은 최소성을 만족하지 못한다.
if((n & c) == n) {
it.remove();
}
}
}
쉽게 말하면 0001 이 유일성을 만족하는 후보키라면 , 다른 모든 경우의 수 중에서 xxx1 을 포함하는 경우의 수는 무조건 최소성을 만족할 수 없다는 점을 이용해 list에서 제거하도록 한 것.
전체 코드
import java.util.*;
class Solution {
boolean check(String[][] relation, int row_num, int col_num, int subset) {
for(int i = 0; i < row_num -1; i++) {
for(int j = i+1; j < row_num; j++) {
boolean isSame = true;
for(int k=0; k < col_num; k++) {
if((subset & (1 << k))==0)
continue;
if(!relation[i][k].equals(relation[j][k])) {
isSame = false;
break;
}
}
if(isSame) return false;
}
}
return true;
}
public int solution(String[][] relation) {
int answer = 0;
int row_num = relation.length;
int column_num = relation[0].length;
List<Integer> candidates = new LinkedList<Integer>();
for(int i=1; i< (1 << column_num); i++) {
if(check(relation, row_num, column_num, i)) {
candidates.add(i);
}
}
while(candidates.size()!=0) {
int n = candidates.remove(0);
answer++;
for(Iterator<Integer> it = candidates.iterator(); it.hasNext(); ) {
int c = it.next();
if((n & c) == n) {
it.remove();
}
}
}
return answer;
}
}
Programmers에 올라와 있는 Kakao 문제를 이용하였고, 문제풀이는 먼저는 하는데까지 작성해보고 완성은 다른 사람의 풀이를 참고해 다시풀어보는 방식으로 진행하였다.
문제 설명
무지의 먹방 라이브
* 효율성 테스트에 부분 점수가 있는 문제입니다.
평소 식욕이 왕성한 무지는 자신의 재능을 뽐내고 싶어 졌고 고민 끝에 카카오 TV 라이브로 방송을 하기로 마음먹었다.
그냥 먹방을 하면 다른 방송과 차별성이 없기 때문에 무지는 아래와 같이 독특한 방식을 생각해냈다.
회전판에 먹어야 할 N 개의 음식이 있다. 각 음식에는 1부터 N 까지 번호가 붙어있으며, 각 음식을 섭취하는데 일정 시간이 소요된다. 무지는 다음과 같은 방법으로 음식을 섭취한다.
무지는 1번 음식부터 먹기 시작하며, 회전판은 번호가 증가하는 순서대로 음식을 무지 앞으로 가져다 놓는다.
마지막 번호의 음식을 섭취한 후에는 회전판에 의해 다시 1번 음식이 무지 앞으로 온다.
무지는 음식 하나를 1초 동안 섭취한 후 남은 음식은 그대로 두고, 다음 음식을 섭취한다.
다음 음식이란, 아직 남은 음식 중 다음으로 섭취해야 할 가장 가까운 번호의 음식을 말한다.
회전판이 다음 음식을 무지 앞으로 가져오는데 걸리는 시간은 없다고 가정한다.
무지가 먹방을 시작한 지 K 초 후에 네트워크 장애로 인해 방송이 잠시 중단되었다. 무지는 네트워크 정상화 후 다시 방송을 이어갈 때, 몇 번 음식부터 섭취해야 하는지를 알고자 한다. 각 음식을 모두 먹는데 필요한 시간이 담겨있는 배열 food_times, 네트워크 장애가 발생한 시간 K 초가 매개변수로 주어질 때 몇 번 음식부터 다시 섭취하면 되는지 return 하도록 solution 함수를 완성하라.
제한사항
food_times 는 각 음식을 모두 먹는데 필요한 시간이 음식의 번호 순서대로 들어있는 배열이다.
k 는 방송이 중단된 시간을 나타낸다.
만약 더 섭취해야 할 음식이 없다면-1을 반환하면 된다.
정확성 테스트 제한 사항
food_times 의 길이는1이상2,000이하이다.
food_times 의 원소는1이상1,000이하의 자연수이다.
k는1이상2,000,000이하의 자연수이다.
효율성 테스트 제한 사항
food_times 의 길이는1이상200,000이하이다.
food_times 의 원소는1이상100,000,000이하의 자연수이다.
k는1이상2 x 10^13이하의 자연수이다.
나의 풀이
먼저 가장 단순한 풀이법은 매 회차마다 남아있는 음식을 순서대로 하나씩 선택하며 줄여가는 풀이일텐데, 당연하게? 효율성 테스트는 통과하지 못했다. 그래서 나름의 고민과 결곽적으론 다른 사람의 풀이를 이해해가며 풀어본 방식이 아래 코드이다.
1. 입력받은 음식의 순서를 index로, 걸리는 시간을 times로 갖는 Food 객체를 생성하고 Foods 리스트에 저장.
2. 해당 Foods 리스트를 times 크기로 정렬.
3. 주어진 시간 중 남은시간 - 현재 음식을 마저 다 먹는데 걸리는 시간 * 남은 음식의 수 의 개념으로 남은 시간에서 꾸준히 값을 빼준다.
4. 남은시간 < 현재 음식을 마저 다먹는 시간 * 남은 음식의 수 일 경우, 현재 음식을 다 먹기전에 남은 시간이 종료되는 것이기 때문에 남은 음식들을 처음 주어진 순선대로 다시 재정렬.
5. 남은 시간이 끝나는 순간 선택될 음식을 검색 후 리턴.
위의 순서대로 풀었다.
문제를 풀고나서 든 생각은 Level 4 같지는 않은 느낌이랄까... 오히려 매칭 점수 문제가 더 어려웠던거 같은데 아무래도 내가 약한 부분이 어딘지 들어나는 것 같다. 매칭 점수 문제를 다시 풀어보고 포스팅에 추가하는 걸로.
코드
import java.util.*;
class Solution {
class Food {
int times;
int index;
Food(int times, int index) {
this.times = times;
this.index = index;
}
}
Comparator<Food> Times_Comp = new Comparator<Food>() {
public int compare(Food f1, Food f2) {
return f1.times - f2.times;
}
};
Comparator<Food> Index_Comp = new Comparator<Food>() {
public int compare(Food f1, Food f2) {
return f1.index - f2.index;
}
};
public int solution(int[] food_times, long k) {
int n = food_times.length;
List<Food> foods = new LinkedList<>();
for(int i=0; i<n; i++) {
foods.add(new Food(food_times[i], i+1));
}
foods.sort(Times_Comp);
int pre = 0;
int idx = 0;
for(Food f : foods) {
long diff = f.times - pre;
if(diff>0) {
long temp = diff*n;
if(temp <= k) {
k -= temp;
pre = f.times;
} else {
k %= n;
foods.subList(idx, food_times.length).sort(Index_Comp);
return foods.get(idx+(int)k).index;
}
}
idx++;
n--;
}
return -1;
}
}
