Kakao 카카오 블라인드 채용 - 1차 코딩 테스트
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;
}
}
'Algorithm > 기타' 카테고리의 다른 글
| 카카오 코드 페스티벌 예선 - 캠핑 문제 해설 (Java) (7) | 2017.09.28 |
|---|---|
| 카카오 모의 테스트 문제(Java) (7) | 2017.09.12 |
| [Interview] a^3 + b^3 = c^3 + d^3 을 만족하는 100 이하의 자연수를 모두 찾아보자 (0) | 2017.09.08 |
| 알고리즘 공부 리스트 및 순서 (Algorithm Problem Solving Roadmap) (6) | 2017.06.04 |
| 세그먼트 트리(Segment Tree, 구간 트리) (0) | 2017.05.25 |