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

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

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

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

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

이것 또한 공부가 되겠죠.

전 손도 못댄 문제 입니다. pass 하길 잘했네요.

함정은 "처리시간은 시작시간과 끝시간을 포함"입니다.

또한 java 같은 경우에는 double, float 계산이 함정일 수 있겠네요.

자바에서 double, float의 계산은 부정확 합니다.

해설처럼 로그의 시작, 종료 타임을 기준으로 계산하면 되네요.

public class kakao7 { public static void main(String[] args) { //solution(new String[]{"2016-09-15 03:10:33.020 0.011s"}); solution(new String[]{"2016-09-15 01:00:04.001 2.0s", "2016-09-15 01:00:07.000 2s"}); solution(new String[]{"2016-09-15 01:00:04.002 2.0s", "2016-09-15 01:00:07.000 2s"}); solution(new String[]{"2016-09-15 20:59:57.421 0.351s", "2016-09-15 20:59:58.233 1.181s", "2016-09-15 20:59:58.299 0.8s", "2016-09-15 20:59:58.688 1.041s", "2016-09-15 20:59:59.591 1.412s", "2016-09-15 21:00:00.464 1.466s", "2016-09-15 21:00:00.741 1.581s", "2016-09-15 21:00:00.748 2.31s", "2016-09-15 21:00:00.966 0.381s", "2016-09-15 21:00:02.066 2.62s"}); } static int solution(String[] inputLogs) { ArrayList<log> logs = new ArrayList<log>(); for (int i=0; i<inputLogs.length; i++) { logs.add(new log(inputLogs[i])); } int maxNum = 0; for (int i=0; i<logs.size(); i++) { int startNum = 0, exitNum = 0; float startTime = logs.get(i).getStartTime(); float exitTime = logs.get(i).getExitTime(); for (int j=0; j<logs.size(); j++) { if (startTime <= logs.get(j).getExitTime() && startTime + (float)0.999 >= logs.get(j).getStartTime()) { startNum ++; } if (exitTime <= logs.get(j).getExitTime() && exitTime + (float)0.999 >= logs.get(j).getStartTime()) { exitNum ++; } } maxNum = maxNum > startNum ? maxNum : startNum; maxNum = maxNum > exitNum ? maxNum : exitNum; } System.out.println(maxNum); return maxNum; } static class log { private float startTime, exitTime; public log(String time) { String[] times = time.split(" "); String[] tempTime = times[1].split(":"); float exitTime = Float.parseFloat(tempTime[0])*60*60; exitTime += Float.parseFloat(tempTime[1])*60; exitTime += Float.parseFloat(tempTime[2]); this.exitTime = exitTime; tempTime = times[2].split("s"); float startTime = exitTime - Float.parseFloat(tempTime[0]); startTime += (float)0.001; this.startTime = startTime; } public float getStartTime() { return startTime; } public float getExitTime() { return exitTime; } } }

"처리시간은 시작시간과 끝시간을 포함"이기 때문에 1초 대신 0.999를, 0.001초를 적절히 사용했습니다.

- 추가 코드 ( 17년 10월 25일) -

import java.util.ArrayList; public class Q7 { public static void main(String[] args) { //solution(new String[]{"2016-09-15 03:10:33.020 0.011s"}); solution(new String[]{"2016-09-15 01:00:04.001 2.0s", "2016-09-15 01:00:07.000 2s"}); solution(new String[]{"2016-09-15 01:00:04.002 2.0s", "2016-09-15 01:00:07.000 2s"}); solution(new String[]{"2016-09-15 20:59:57.421 0.351s", "2016-09-15 20:59:58.233 1.181s", "2016-09-15 20:59:58.299 0.8s", "2016-09-15 20:59:58.688 1.041s", "2016-09-15 20:59:59.591 1.412s", "2016-09-15 21:00:00.464 1.466s", "2016-09-15 21:00:00.741 1.581s", "2016-09-15 21:00:00.748 2.31s", "2016-09-15 21:00:00.966 0.381s", "2016-09-15 21:00:02.066 2.62s"}); //solution(new String[]{"2016-09-15 01:00:04.001 2.0s", "2016-09-15 01:00:07.000 2s", "2016-09-15 01:00:04.002 2.0s", "2016-09-15 01:00:07.000 2s", "2016-09-15 20:59:57.421 0.351s", "2016-09-15 20:59:58.233 1.181s", "2016-09-15 20:59:58.299 0.8s", "2016-09-15 20:59:58.688 1.041s", "2016-09-15 20:59:59.591 1.412s", "2016-09-15 21:00:00.464 1.466s", "2016-09-15 21:00:00.741 1.581s", "2016-09-15 21:00:00.748 2.31s", "2016-09-15 21:00:00.966 0.381s", "2016-09-15 21:00:02.066 2.62s"}); } static void solution(String[] inputLogs) { int result = 0; ArrayList<log> logs = new ArrayList<log>(); logs = getLogs(inputLogs); for ( int i = 0; i < inputLogs.length; i++ ) { int num = 1; int exitTime = logs.get(i).getExitTime(); for ( int j = 0; j < inputLogs.length; j++ ) { int tempStartTime = logs.get(j).getStartTime(); int tempExitTime = logs.get(j).getExitTime(); if ( i != j && tempStartTime <= exitTime + 999 && exitTime <= tempExitTime ) { num++; } } if ( result < num ) { result = num; } } System.out.println(result); } static ArrayList<log> getLogs(String[] inputLogs) { ArrayList<log> logs = new ArrayList<log>(); for ( int i = 0; i < inputLogs.length; i++ ) { logs.add(new log(inputLogs[i])); } return logs; } } class log { private int startTime, exitTime; public log(String time) { int exitTime = 0; String[] timeSplit = time.split(" "); String[] exitTimeSplit = timeSplit[1].split(":"); exitTime += Integer.valueOf(exitTimeSplit[0]) * 3600000; exitTime += Integer.valueOf(exitTimeSplit[1]) * 60000; exitTime += getSeconds(exitTimeSplit[2]); this.exitTime = exitTime; this.startTime = exitTime - getSeconds(timeSplit[2].replace("s", "")) + 1; } int getSeconds(String second) { int time = 0; String[] Seconds = second.split("\\."); time += Integer.valueOf(Seconds[0]) * 1000; if ( Seconds.length > 1 ) { int temp = Integer.valueOf(Seconds[1]); if ( Seconds[1].length() == 1 ) { temp *= 100; } else if ( Seconds[1].length() == 2 ) { temp *= 10; }  time += temp; } return time; } public int getStartTime() { return startTime; } public int getExitTime() { return exitTime; } }

자바의 경우 float, double 연산을 수행할 경우

올바른 값이 나오지 않는 경우가 빈번합니다.

("java float double 연산"로 검색해보세요.)

따라서 float와 double를 사용하지 않고 코드를 짜봤습니다.

1000값을 곱해주어 소수점을 없애는 것이죠.

여러 조건이 맞기 때문에 가능했습니다.

다른 방법으로는 BigDecimal 사용이 있습니다.

"ㅇㄴㄻㅇㄹ"님께서

EndNum만으로도 결과를 구할수 있다는 정보를 주셨습니다.

감사합니다.

- 추가 코드 ( 17년 11월 30일) -

import java.util.ArrayList; import java.util.Collections; public class Q7 { public static void main(String[] args) { solution(new String[]{"2016-09-15 03:10:33.020 0.011s"}); solution(new String[]{"2016-09-15 01:00:04.001 2.0s", "2016-09-15 01:00:07.000 2s"}); solution(new String[]{"2016-09-15 01:00:04.002 2.0s", "2016-09-15 01:00:07.000 2s"}); solution(new String[]{"2016-09-15 20:59:57.421 0.351s", "2016-09-15 20:59:58.233 1.181s", "2016-09-15 20:59:58.299 0.8s", "2016-09-15 20:59:58.688 1.041s", "2016-09-15 20:59:59.591 1.412s", "2016-09-15 21:00:00.464 1.466s", "2016-09-15 21:00:00.741 1.581s", "2016-09-15 21:00:00.748 2.31s", "2016-09-15 21:00:00.966 0.381s", "2016-09-15 21:00:02.066 2.62s"}); solution(new String[]{"2016-09-15 01:00:04.001 2.0s", "2016-09-15 01:00:07.000 2s", "2016-09-15 01:00:04.002 2.0s", "2016-09-15 01:00:07.000 2s", "2016-09-15 20:59:57.421 0.351s", "2016-09-15 20:59:58.233 1.181s", "2016-09-15 20:59:58.299 0.8s", "2016-09-15 20:59:58.688 1.041s", "2016-09-15 20:59:59.591 1.412s", "2016-09-15 21:00:00.464 1.466s", "2016-09-15 21:00:00.741 1.581s", "2016-09-15 21:00:00.748 2.31s", "2016-09-15 21:00:00.966 0.381s", "2016-09-15 21:00:02.066 2.62s"}); } static void solution(String[] inputLogs) { ArrayList<log> logs = getLogs(inputLogs); if ( logs.size() == 0 ) { System.out.println(0); return; } else if ( logs.size() == 1 ) { System.out.println(1); return; } int result = 1; Collections.sort(logs); //startTime을 기준으로 정렬 for ( int i = 0; i < inputLogs.length-1; i++ ) { int num = 1; //자기 자신을 포함해서 1 int exitTime = logs.get(i).getExitTime(); for ( int j = i+1; j < inputLogs.length; j++ ) { int tempStartTime = logs.get(j).getStartTime(); int tempExitTime = logs.get(j).getExitTime(); if ( tempStartTime <= exitTime + 999 && exitTime <= tempExitTime ) { num++; } } result = result < num ? num : result; } System.out.println(result); } static ArrayList<log> getLogs(String[] inputLogs) { ArrayList<log> logs = new ArrayList<log>(); for ( int i = 0; i < inputLogs.length; i++ ) { logs.add(new log(inputLogs[i])); } return logs; } } class log implements Comparable<log> { private int startTime, exitTime; public log(String time) { int exitTime = 0; String[] timeSplit = time.split(" "); String[] exitTimeSplit = timeSplit[1].split(":"); exitTime += Integer.valueOf(exitTimeSplit[0]) * 3600000; exitTime += Integer.valueOf(exitTimeSplit[1]) * 60000; exitTime += getSeconds(exitTimeSplit[2]); this.exitTime = exitTime; this.startTime = exitTime - getSeconds(timeSplit[2].replace("s", "")) + 1; } int getSeconds(String second) { int time = 0; String[] Seconds = second.split("\\."); time += Integer.valueOf(Seconds[0]) * 1000; if ( Seconds.length > 1 ) { int temp = Integer.valueOf(Seconds[1]); if ( Seconds[1].length() == 1 ) { temp *= 100; } else if ( Seconds[1].length() == 2 ) { temp *= 10; }  time += temp; } return time; } public int getStartTime() { return startTime; } public int getExitTime() { return exitTime; } @Override //startTime을 기준으로 정렬하기 public int compareTo(log otherLog) { if (this.startTime < otherLog.getStartTime()) { return -1; } else if (this.startTime > otherLog.getStartTime()) { return 1; } return 0; } }

"codility"님께서

시작 시간을 기준으로 정렬 후 탐색하면

시간 복잡도 NlogN을 구할 수 있다고

알려주셨습니다. 감사합니다.

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