Algorithm/기타

Kakao 카카오 블라인드 채용 - 1차 코딩 테스트

밤이2209 2017. 9. 21. 02:07

Kakao 카카오 블라인드 채용 - 1차 코딩 테스트


- 6, 7번 코드는 프로그래머스에 문제 공개되면 다시 채점해보고 코드 올리도록 하겠습니다.

- 4번 문제도 채점은 다시 해봐야되는데 틀린 점이 없어보여서 일단 올려봅니다. 잘못된 점 있으면 댓글 부탁드립니다.

- 5번 문제는 너무 급하게 풀어서 불합리한 부분이 있을 수 있습니다. 댓글 달아주세요.

1번 문제. 비밀 지도

/**
* 카카오 Test#1_1 비밀지도
*/

public class Main {

public static void main(String[] args) {

int n = 5;
int[] arr1 = { 9, 20, 28, 18, 11 };
int[] arr2 = { 6, 1, 21, 17, 28 };

String[] map = solution(n, arr1, arr2);

for (int i = 0; i < n; i++) {

System.out.println(map[i]);
}
}

static String[] solution(int n, int[] arr1, int[] arr2) {

String[] answer = new String[n];

for (int i = 0; i < n; i++) {

answer[i] = convert(arr1[i] | arr2[i], n);
}

return answer;
}

static String convert(int num, int n) {

StringBuilder sb = new StringBuilder();
char[] binaryStr = Integer.toBinaryString(num).toCharArray();

int length = n - binaryStr.length;
for (int i = 0; i < length; i++) {

sb.append(" ");
}

for (char c : binaryStr) {

if (c == '1') sb.append("#");
else if (c == '0') sb.append(" ");
}

return sb.toString();
}
}



2번 문제. 다트 게임

/**
* 카카오 Test#1_2 다트 게임
*/
public class Main {

public static void main(String[] args) {

String[] testCase = {"1S2D*3T", "1D2S#10S", "1D2S0T", "1S*2T*3S", "1D#2S*3S", "1T2D3D#", "1D2S3T*"};
for (String s : testCase) {

System.out.println(solution(s));
}
}

public static int solution(String dartResult) {

int[] score = new int[3];
String[] num = dartResult.split("[SDT](\\#)?(\\*)?");
String[] operator = dartResult.split("\\d+");

for (int i = 0; i < 3; i++) {

char op1 = operator[i + 1].charAt(0);

// S, D, T
switch (op1) {

case 'S':
score[i] = Integer.parseInt(num[i]);
break;

case 'D':
score[i] = Integer.parseInt(num[i]);
score[i] *= score[i];
break;

case 'T':
score[i] = Integer.parseInt(num[i]);
score[i] *= score[i] * score[i];
break;
}

// *, #
if (operator[i + 1].length() > 1) {

char op2 = operator[i + 1].charAt(1);

switch (op2) {

case '*':
for (int j = (i - 1 < 0 ? 0 : i - 1); j <= i; j++) {

score[j] *= 2;
}
break;

case '#':
score[i] *= -1;
break;
}
}
}

int answer = 0;
for (int i = 0; i < 3; i++) {

answer += score[i];
}
return answer;
}
}



3번 문제. 캐시

import java.util.LinkedList;
import java.util.Queue;

/**
* 카카오 Test#1_3 캐시
*/
public class Main {

static final int HIT = 1;
static final int MISS = 5;

public static void main(String[] arg) {

String[] cities = {"Jeju", "Pangyo", "Seoul", "NewYork", "LA", "Jeju", "Pangyo", "Seoul", "NewYork", "LA"};
int cacheSize = 3;

System.out.println(solution(cacheSize, cities));
}

static int solution(int cacheSize, String[] cities) {

int answer = 0;

Queue<String> queue = new LinkedList<>();

for (String city : cities) {

String c = city.toLowerCase();

// HIT
if (queue.contains(c)) {

queue.remove(c);
queue.add(c);

answer += HIT;
}
// MISS
else {

if (queue.size() < cacheSize) {

queue.add(c);
}
// 페이지 교체
else {

queue.poll();

if (queue.size() < cacheSize) queue.add(c);
}

answer += MISS;
}
}

return answer;
}
}




4번 문제. 셔틀버스

import java.util.PriorityQueue;

/**
* 카카오 Test#1_4 셔틀버스
*/
public class Main {

public static void main(String[] args) {

String[] timeTable = {"08:00", "08:01", "08:02", "08:03"};
System.out.println(solution(1, 1, 5, timeTable));
}

/**
* 1. con은 출근을 하긴 해야한다
* 2. con은 가장 늦게 버스정류장에 도착하고 싶다
* 3. 즉, 마지막 버스(막차)를 타면 되는데, 몇시 몇분에 줄을 서야 하는지 알아내보자
* 4. 모든 crew의 출근이 보장되는 것은 아니다. 그러므로 처음부터 순서대로 시뮬레이션을 해보면서 가장 늦게 도착할 수 있는 시간을 구해보자
* 5-1. 버스의 정원이 남는 경우, con은 버스 도착 시간에 맞춰 정류장에 도착하면 된다
* 5-2. 버스의 정원이 남지 않는 경우, con은 마지막에 탑승한 crew보다 1분 일찍 정류장에 도착하면 된다
*/
static String solution(int n, int t, int m, String[] timetable) {

PriorityQueue<Time> pq = new PriorityQueue<>();
for (String time : timetable) pq.add(new Time(time));

// conTime : 콘이 버스 정류장에 가장 늦게 도착할 수 있는 시간
Time conTime = new Time("00:00");

for (int i = 0; i < n; i++) {

Time busTime = new Time("09:00");
busTime.add(i, t);

conTime = busTime;

int capacity = m;

// 버스에 사람 태우기
while (!pq.isEmpty() && capacity > 0 && pq.peek().compareTo(busTime) <= 0) {

Time crewTime = pq.poll();

if (capacity == 1) {

conTime = crewTime;
conTime.add(1, -1);
}

capacity--;
}
}

return conTime.toString();
}
}

class Time implements Comparable<Time> {

int h, m;

Time(String time) {

this.h = Integer.parseInt(time.substring(0, 2));
this.m = Integer.parseInt(time.substring(3, 5));
}

void add(int n, int t) {

int addHour = (n * t) / 60;
int addMin = (n * t) % 60;

h += addHour;
m += addMin;

if (m >= 60) {

h++;
m %= 60;
} else if (m < 0) {

h--;
m = 60 + m;
}
}

@Override
public String toString() {

return String.format("%02d:%02d", this.h, this.m);
}

@Override
public int compareTo(Time o) {

return this.h < o.h ? -1 : this.h > o.h ? 1 : this.m < o.m ? -1 : this.m > o.m ? 1 : 0;
}
}



5번 문제. 뉴스 클러스터링

import java.util.HashMap;
import java.util.Iterator;

/**
* 카카오 Test#1_5 뉴스 클러스터링
*/
public class Main {

static final int MUL = 65536;

public static void main(String[] args) {

String str1 = "aa1+aa2";
String str2 = "AAAA12";

System.out.println(solution(str1.toLowerCase(), str2.toLowerCase()));
}

static int solution(String str1, String str2) {

str1 = str1.toUpperCase();
str2 = str2.toUpperCase();

HashMap<String, Integer> map1 = new HashMap<>();
HashMap<String, Integer> map2 = new HashMap<>();
HashMap<String, Integer> minMap = new HashMap<>();
HashMap<String, Integer> maxMap = new HashMap<>();

// 다중집합1
for (int i = 0; i < str1.length() - 1; i++) {

char c1 = str1.charAt(i);
char c2 = str1.charAt(i + 1);

if (c1 >= 65 && c1 <= 90 && c2 >= 65 && c2 <= 90) {

String subString = str1.substring(i, i + 2);

if (map1.containsKey(subString)) map1.put(subString, map1.get(subString) + 1);
else map1.put(subString, 1);
}
}

// 다중집합2
for (int i = 0; i < str2.length() - 1; i++) {

char c1 = str2.charAt(i);
char c2 = str2.charAt(i + 1);

if (c1 >= 65 && c1 <= 90 && c2 >= 65 && c2 <= 90) {

String subString = str2.substring(i, i + 2);

if (map2.containsKey(subString)) map2.put(subString, map2.get(subString) + 1);
else map2.put(subString, 1);
}
}

// 교집합, 합집합
for (String key : map1.keySet()) {

if (minMap.containsKey(key)) {

if (minMap.get(key) > map1.get(key)) {

minMap.put(key, map1.get(key));
}
} else {

minMap.put(key, map1.get(key));
}

if (maxMap.containsKey(key)) {

if (maxMap.get(key) < map1.get(key)) {

maxMap.put(key, map1.get(key));
}
} else {

maxMap.put(key, map1.get(key));
}
}

for (String key : map2.keySet()) {

if (minMap.containsKey(key)) {

if (minMap.get(key) > map2.get(key)) {

minMap.put(key, map2.get(key));
}
}

if (maxMap.containsKey(key)) {

if (maxMap.get(key) < map2.get(key)) {

maxMap.put(key, map2.get(key));
}
} else {

maxMap.put(key, map2.get(key));
}
}

for (String key : minMap.keySet()) {

if (!map2.containsKey(key)) minMap.remove(key);
}

Iterator<String> min = minMap.keySet().iterator();
Iterator<String> max = maxMap.keySet().iterator();

int minSize = 0;
int maxSize = 0;

while (min.hasNext()) minSize += minMap.get(min.next());
while (max.hasNext()) maxSize += maxMap.get(max.next());

int answer;

if (minSize == 0 && maxSize == 0) answer = MUL;
else answer = (int) (((double) minSize / (double) maxSize) * MUL);

return answer;
}
}