카카오 블라인드 채용 신입 공채 1차 코딩 테스트) 5번 문제

문제 출처 : http://tech.kakao.com/2017/09/27/kakao-blind-recruitment-round-1/

지난 9월 16일(토) 오후 2시부터 오후 7시까지 5시간동안 진행한 코딩테스트입니다.

보통 코딩 테스트 문제 유출하면 안되는데, 카카오는 문제를 공개하고 직접 문제 해설도 진행했습니다.

시험 당시 제출했던 코드와 해설을 참고하여 수정한 코드를 올리겠습니다.

이것 또한 공부가 되겠죠.

함정은 중복을 허용하는 다중집합입니다.

따라서 중복처리를 수행해야 합니다.

중복이 있을경우 숫자를 추가하여 (a1, a2, a3, a4 방식처럼) 처리했습니다.

public class kakao5 { public static void main(String[] args) { solution("FRANCE", "french"); solution("handshake", "shake hands"); solution("aa1+aa2", "AAAA12"); solution("E=M*C^2", "e=m*c^2"); } static int solution(String str1, String str2) { String[] set1 = getSet(str1.toUpperCase()); //다중집합(영문자 원소만) String[] set2 = getSet(str2.toUpperCase()); //다중집합(영문자 원소만) set1 = getCalDupli(set1); //중복 원소 수정 set2 = getCalDupli(set2); //중복 원소 수정 double resultIntersectionSet = intersectionSet(set1, set2); //교집합 double resultSumSet = sumSet(set1, set2); //합집합 int result = 65536; if ( resultIntersectionSet != 0 || resultSumSet != 0) { //공집합이 아닐 경우 result = (int)((resultIntersectionSet / resultSumSet) * result); } System.out.println(result); return result; } static String[] getSet(String temp) { //65~90 (영문) ArrayList<String> resultTemp = new ArrayList<String>(); for(int i=0; i<temp.length()-1; i++) { if(temp.charAt(i) >= 65 && temp.charAt(i) <= 90 && temp.charAt(i+1) >= 65 && temp.charAt(i+1) <= 90) { //모두 영문일 경우에만 resultTemp.add(temp.substring(i,i+2)); } } String[] result = new String[resultTemp.size()]; for(int i=0; i<resultTemp.size();i++) { result[i] = resultTemp.get(i); } return result; } static String[] getCalDupli(String[] temp) { for(int i=0; i<temp.length; i++) { String now = temp[i]; if (now != null && now.length() == 2) { int size = 1; temp[i] = temp[i] + (size++); //1추가 (ex. a1) for(int j=i+1; j<temp.length; j++) { if (temp[j] != null && temp[j].length() == 2 && now.equals(temp[j])) { temp[j] = temp[j] + (size++); //중복이 있을 경우 숫자 추가(ex. a2, a3, a4 ...) } } } } return temp; } static int intersectionSet(String[] set1, String[] set2) { int intersection = 0; for(int i=0; i<set1.length; i++) { for(int j=0; j<set2.length; j++) { if (set1[i].equals(set2[j])) { intersection ++; break; } } } return intersection; } static int sumSet(String[] set1, String[] set2) { HashSet<String> set = new HashSet<String>(); for(int i=0; i<set1.length; i++) { set.add(set1[i]); } for(int j=0; j<set2.length; j++) { set.add(set2[j]); } return set.size(); } }

보통 StringUtils를 사용하지만, 세팅문제로 사용하지 않았습니다.

자카드 유사도 계산방식은 간단하지만 교, 합집합 구하기가 까다로웠습니다.

- 추가 소스 (17년 10월 25일) -

import java.util.LinkedList; public class Q5 { public static void main(String[] args) { solution("FRANCE", "french"); solution("handshake", "shake hands"); solution("aa1+aa2", "AAAA12"); solution("E=M*C^2", "e=m*c^2"); } static void solution(String str1, String str2) { LinkedList str1Array = getSet(str1.toUpperCase()); LinkedList str2Array = getSet(str2.toUpperCase()); float jacquard = 1; int sumSet = 0, intersectionSet = 0; if ( str1Array.size() != 0 && str2Array.size() != 0 ) { for ( int i = 0; i < str1Array.size(); i++ ) { for ( int j = 0; j < str2Array.size(); j++ ) { if ( str1Array.get(i).equals(str2Array.get(j)) ) { sumSet += 1; intersectionSet += 1; str1Array.remove(i); str2Array.remove(j); i--; j = -1; break; } } } sumSet += str1Array.size() + str2Array.size(); jacquard = (float)intersectionSet / (float)sumSet; } System.out.println((int)(jacquard * 65536)); } static LinkedList<String> getSet(String str) { LinkedList array = new LinkedList<>(); for ( int i = 0; i+1 < str.length(); i++ ) { if ( str.charAt(i) < 65 || str.charAt(i) > 90 ) { continue; } if ( str.charAt(i+1) < 65 || str.charAt(i+1) > 90 ) { i++; continue; } String temp = String.valueOf(str.charAt(i)) + String.valueOf(str.charAt(i+1)); array.add(temp); } return array; } }

원소의 중복을 허용하는 다중집합을 LinkedList로 구현했습니다. (삭제에 적합하기 때문에)

가장 까다로운 부분이 원소의 중복을 허용하는 다중집합의 합집합과 교집합입니다.

문자열 다중집합의 원소를 각각 비교하여 서로 같을 경우에는

합집합 += 1;  교집합 +=1; 을 수행했으며

해당 원소를 문자열 다중집합에서 삭제했습니다.

이로써 교집합은 쉽게 구했고,

남아있는 원소의 개수를 합집합에 더함으로써 합집합을 구했습니다.

급하게 테스트 볼때 보다 지금 다시짠 코드가 확실히 더 깔끔하네요.

좀 더 좋은 코드 및 다듬을 부분을 알려주시면 감사히 학습하겠습니다.