2018 카카오 블라인드 코딩테스트 1차(프로그래머스, 모든 문제, Java)

1. 비밀지도(난이도: 하)

문제링크: https://programmers.co.kr/learn/courses/30/lessons/17681

코딩테스트 연습 - [1차] 비밀지도 | 프로그래머스

알고리즘 설명:

단순한 2진수 덧셈인데 자릿수 올림이 없는 문제이다.

• 두 배열에서 차례대로 값을 가져와 2로 나눈다.
• 나머지 값을 더했을 때 1 또는 2이면 #, 0이면 공백을 answer배열에 넣었다.
• answer배열 한 줄이 완성되었을 때 배열을 반대로 넣어주면 자릿수 올림이 없는 2진수 덧셈완성

코드(Java)

package test;

public class ScreteMap {

	public static String[] solution(int n, int[] arr1, int[] arr2) {
		String answer[] =new String[n];
		
		for (int j = 0; j < n; j++) {
			int temp1 = arr1[j];
			int temp2 = arr2[j];
			answer[j] ="";
			
			for (int i = 0; i < n; i++) {
				if((temp1%2 + temp2%2)>0) {
					answer[j] += "#";
				}else {
					answer[j] +=" ";
				}
				temp1 = temp1/2;
				temp2 = temp2/2;
			}
			answer[j] = new StringBuffer(answer[j]).reverse().toString();
		}

		return answer;
	}

	public static void main(String[] args) {
		int arr1[] = { 9, 20, 28, 18, 11 };
		int arr2[] = { 30, 1, 21, 17, 28 };
		int n = 5;
		for (String val : solution(n, arr1, arr2)) {
			System.out.println(val);
		}
	}

}

---

2. 다트게임(난이도: 하)

문제링크: https://programmers.co.kr/learn/courses/30/lessons/17682

코딩테스트 연습 - [1차] 다트 게임 | 프로그래머스

알고리즘 설명:

배열로 하나씩 읽어가면서 조건에 맞게 계산하는 문제였다.

• 반복문으로 배열 값을 하나씩 읽으면서 처음에 오는 숫자가 10인 경우인지 아닌지를 체크한다.
• 스위치문으로 그 다음 문자들에 맞는 조건으로 answer값을 계산한다.
• 점수가 3번 계산된다고 문제에서 주어졌기 때문에 answer 배열을 3 크기로 만든 뒤 각각에 결과 값을 넣어주고 마지막에 더한다.

막혔던 지점:

제곱을 할 때 함수를 이용하지 않고 단순히 곱셈으로 제곱을 하면 값이 약간 달라질 수 있다.

 

코드(Java)

package test;

public class Dartgame {
	public static int solution(String dartResult) {
		int[] answer = new int[3];
		char dartarr[] = dartResult.toCharArray();
		String temp = "";

		int curindex = 0;
		for (int i =0; i < dartarr.length; i++) {
			temp = "";
			if (Character.isDigit(dartarr[i])) {
				
				temp += dartarr[i];
				answer[curindex] = Integer.parseInt(temp);
				if(Character.isDigit(dartarr[i+1])) {
					answer[curindex]*=10;
					i++;
				}
				curindex++;
				continue;
			}
			
			switch (dartarr[i]) {
			case '*':
				answer[curindex-1] *= 2;
				if(curindex > 1)answer[curindex-2]*=2;
				break;
				
			case '#':
				answer[curindex-1] *= -1;
				break;
			case 'D':
				answer[curindex-1] = (int) Math.pow(answer[curindex-1], 2);
				break;
			case 'S':
				break;
			case 'T':
				answer[curindex-1] = (int) Math.pow(answer[curindex-1], 3);
				break;
			}
		}

		return answer[0]+answer[1]+answer[2];
	}

	public static void main(String[] args) {
		String dartResult = "1D2S#10S";
		System.out.println(solution(dartResult));

	}

}

---

3. 캐시(난이도: 하)

문제링크: https://programmers.co.kr/learn/courses/30/lessons/17680

코딩테스트 연습 - [1차] 캐시 | 프로그래머스

알고리즘 설명:

LRU알고리즘에서 문제가 요구하는 부분에 answer 값을 올려주면 쉽게 구할 수 있다.

 

코드(Java)

package test;

import java.util.HashMap;
import java.util.Map;

public class Cache {
	static Map<String,Node> map = new HashMap<>();
	static Node head;
	static Node end;
	
	public static int solution(int cacheSize, String[] cities) {
        if(cacheSize==0)
            return cities.length*5;
        
		LRU lru = new LRU(cacheSize);
		for(String city : cities) {
			lru.set(city.toLowerCase());
		}
		return lru.getAnswer();
	}
	public static class LRU{
		int cacheSize;
		int answer = 0;
		public int getAnswer() {
			return answer;
		}
		
		public void remove(Node n) {
			if(n.pre != null) {
				n.pre.next = n.next;
			}else {
				head = n.next;
			}
			
			if(n.next != null) {
				n.next.pre = n.pre;
			}else {
				end = n.pre;
			}
		}
		public LRU(int cacheSize) {
			this.cacheSize = cacheSize;
		}

		public void set(String name) {
			if(map.containsKey(name)) {
				Node n = map.get(name);
				remove(n);
				setHead(n);
				answer++;
			}else {
				Node n = new Node(name);
				
				if(map.size() >= cacheSize) {
					map.remove(end.cityname);
					remove(end);
				}
				setHead(n);
				map.put(name,n);
				answer+=5;
			}
		}
		
		public void setHead(Node n) {
			n.next = head;
			n.pre = null;
			
			if(head!= null) 
				head.pre = n;
			
			head = n;
			
			if(end == null)
				end = head;
		}
	}
	
	public static class Node{
		String cityname;
		Node pre;
		Node next;
		
		public Node(String cityname) {
			this.cityname = cityname;
		}
	}
	public static void main(String[] args) {
		System.out.println(solution(0, new String[] { "Jeju", "Pangyo", "Seoul", "NewYork", "LA" })); // 25

	}

}

4. 셔틀버스(난이도: 중)

문제링크: https://programmers.co.kr/learn/courses/30/lessons/17678

코딩테스트 연습 - [1차] 셔틀버스 | 프로그래머스

 

알고리즘 설명:

가장 늦게 가는 방법을 구하는 문제이므로 마지막 버스에 경우만 생각해서 풀었다.

마지막 버스에서의 경우의 수를 생각해보니 4가지가 나왔다.

1. 아직 못 탄 사람이 존재하는데 버스가 꽉찬 경우: 마지막 탄 사람의 시간 - 1분
2. 아직 못 탄 사람이 존재하는데 버스에 자리가 남은 경우: 마지막 버스가 온 시간
3. 기다리는 사람은 없는데 버스가 꽉 찬 경우(딱 맞게 탄 경우): 마지막 탄 사람의 시간 - 1분
4. 기다리는 사람은 없는데 버스에 자리가 남은 경우: 마지막 버스가 온 시간

• 먼저 문자열로 들어온 시간배열을 분(Integer)배열으로 바꾼다
• 반복수를 줄이기 위해 배열을 오름차순으로 정렬해준다.
• 반복문으로 버스가 도착한 시간을 업데이트 해주고 그 시간보다 먼저 온 사람들을 버스 인원수 만큼 태우고 태운 인원을 카운트한다.
• index는 태운 사람의 배열은 접근 안해도 되므로 반복문 시작을 태우지 않은 사람부터 돌리기 위해 사용하였다.
• 마지막 버스 마지막에 탄 사람의 시간을 저장하고 반복문을 빠져나온다.
• 탄 사람 수와 마지막 탄 사람의 시간 값을 가지고 위에서 말한 4가지 경우와 비교해본다.

막혔던 지점:

처음에는 List를 사용하여 버스에 탄 경우 remove하는 방식으로 코드를 진행했는데 프로그래머스에서 100점이 나오지 않았다... 그래서 혹시나 배열로 바꾸어 돌려보니 100점....

 

코드(Java)

package test;

import java.util.Arrays;

public class ShuttleBus {
	public static String solution(int n, int t, int m, String[] timetable) {
		String answer = "";
		int[] minarr = new int[timetable.length];
		int start = 9 * 60 - t;
		int index=0;
		
		for (int i = 0; i < timetable.length; i++) {
			String[] strtime = timetable[i].split(":");
			minarr[i]=(Integer.parseInt(strtime[0]) * 60 + Integer.parseInt(strtime[1]));
		}
		Arrays.sort(minarr);
		int count = 0;
		for (int i = 0; i < n; i++) {
			start += t;
			count = 0;
			for (int j=index;j<minarr.length;j++) {
					if (start >= minarr[j]) {
						count++;
						index++;
						if(count==m)break;
					}
			}
			if(start>=(24*60))break;
		}
		if (index==minarr.length) {
			if (count == m) {
				int temp = minarr[index-1] - 1;
				int hour = temp / 60;
				int min = temp % 60;
				answer = String.format("%02d:%02d", hour, min);
				return answer;
			} else {
				int hour = start / 60;
				int min = start % 60;
				answer = String.format("%02d:%02d", hour, min);
				return answer;
			}
		} else {
			if (count == m) {
				int temp = minarr[index-1] - 1;
				int hour = temp / 60;
				int min = temp % 60;
				answer = String.format("%02d:%02d", hour, min);
				return answer;
			} else {
				int hour = start / 60;
				int min = start % 60;
				answer = String.format("%02d:%02d", hour, min);
				return answer;
			}

		}
	}

	public static void main(String[] args) {

		System.out.println(solution(2, 1, 2, new String[] { "09:00", "09:00", "09:00", "09:00" }));

	}
}

5. 뉴스 클러스터링(난이도: 중)

문제링크: https://programmers.co.kr/learn/courses/30/lessons/17677

코딩테스트 연습 - [1차] 뉴스 클러스터링 | 프로그래머스

알고리즘 설명:

문제에서 주어진 것 처럼 문자열을 2개씩 끊어 읽어 답을 구하면 된다.

• 들어온 문자열을 각각 패턴을 사용하여 영문자인 경우만 Hashmap에 추가
• 이미 map에 들어있는 문자가 또 존재하면 value 값을 +1
• 전체 집합의 개수를 totalsize 변수를 이용하여 map에 put 할 때마다 카운트
• hashmap에 같은 key값이 존재하면 그 key에 두 value 값(map1,map2)을 비교해서 더 작은 값이 교집합 개수
• totalsize - 교집합 개수 = 합집합 개수
• answer = 교집합 개수/합집합 개수

코드(Java)

package test;

import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
import java.util.Set;
import java.util.regex.Pattern;

public class NewsClustering {
	public static int solution(String str1, String str2) {

		Map<String, Integer> map1 = new HashMap<>();
		Map<String, Integer> map2 = new HashMap<>();
		int totalsize = 0;
		for (int i = 0; i < str1.length() - 1; i++) {
			if (Pattern.matches("^[a-zA-Z]*$", str1.substring(i, i + 2))) {
				String part = str1.substring(i, i + 2).toLowerCase();
				if (map1.containsKey(part)) {
					map1.put(part, map1.get(part)+1);
				} else {
					map1.put(part, 1);
				}
				totalsize++;
			}
		}
		for (int i = 0; i < str2.length() - 1; i++) {
			if (Pattern.matches("^[a-zA-Z]*$", str2.substring(i, i + 2))) {
				String part = str2.substring(i, i + 2).toLowerCase();
				if (map2.containsKey(part)) {
					map2.put(part, map2.get(part)+1);
				} else {
					map2.put(part, 1);
				}
				totalsize++;
			}
		}
		if(totalsize==0)return 65536;
		
		Set<String> set1 = map1.keySet();
		Iterator<String> itr1 = set1.iterator();
		int count = 0;
		while (itr1.hasNext()) {
			String name = itr1.next();
			if (map2.containsKey(name)) {
				count += Math.min(map1.get(name), map2.get(name));
			}
		}
		double answer = (double) count / (double) (totalsize - count) * 65536;

		return (int) answer;
	}

	public static void main(String[] args) {
		System.out.println(solution("aa1+aa2", "AAAA12"));
	}

}

6. 프렌즈4블록(난이도: 상)

문제링크: https://programmers.co.kr/learn/courses/30/lessons/17679

코딩테스트 연습 - [1차] 프렌즈4블록 | 프로그래머스

알고리즘 설명:

4칸씩 전체를 스캔하면서 조건이 성립하면 index를 가지고 있다가 전체 스캔이 끝난 뒤 지우고 빈 자리를 위에 있는 index 값으로 채우는 형식

• 4중 for문으로 하나의 index를 기준으로 4칸씩 스캔
• 4칸이 전부 같은 문자면 visited 배열에 체크
  • visited에 체크안된 경우에만 answer 값을 +1
• 전체 스캔이 끝난 뒤 체크된 index들의 값들을 공백으로 바꾼다.
• 3중 for문으로 마지막 행의 index를 기준으로 visited가 체크된지 확인하고 체크된 경우의 열 index값을 줄여가면서 visited체크가 안된 index를 찾는다.
• 찾으면 그 index와 기준 index의 값을 바꿔준다.
• 전체 스캔을 했을 때 조건이 성립하는 경우가 아예 없을 때 까지 반복

 

막혔던 지점:

• Boolean 배열을 2개 사용하여 지워진 배열 index를 접근 못하게 관리했다.
• 배열 1개로만 4개가 같은 조건이 성립하면 true로 바꾸어 접근은 관리했다면 이전에 조건이 성립한 경우의 배열 index에는 아예 접근을 할 수 없었다. (일부 중복된 index 존재 가능)
• 그래서 2개를 만들어 스캔하는 동안 접근제한을 할 index를 체크하는 boolean 배열과 실질적으로 접근을 관리하는 boolean 배열을 만들었다.
• 전체 스캔을 끝냈을 때 체크한 배열을 실제 접근 관리 배열에 그대로 넣는 방식으로 코드를 짰는데 여기서 멍청하게 얕은 복사를 해서 완벽하게 점수가 나오지 않았다.
• 결국 깊은 복사 대신 스캔이 끝난 뒤에 조건에 성립한 index에 있는 문자를 공백으로 바꿔버렸다.

코드(Java)

package test;

public class FriendsFourBlock {

	public static int solution(int m, int n, String[] board) {
		int answer = 0;
		char[][] boardchar = new char[m][n];
		boolean[][] visited = new boolean[m][n];
		for (int i = 0; i < m; i++) {
			boardchar[i] = board[i].toCharArray();
		}
		boolean flag = true;

		while (flag) {
			flag = false;
			for (int i = 0; i < m - 1; i++) {
				for (int j = 0; j < n - 1; j++) {
					int count = 0;
					if (boardchar[i][j] != ' ') {
						for (int x = 0; x < 2; x++) {
							for (int y = 0; y < 2; y++) {
								if (boardchar[i][j] == boardchar[i + x][j + y])
									count++;
							}
						}

						if (count == 4) {
							flag = true;
							for (int x = 0; x < 2; x++) {
								for (int y = 0; y < 2; y++) {
									if (!visited[i + x][j + y]) {
										visited[i + x][j + y] = true;
										answer++;
									}
								}
							}
						}

					}

				}
			}
			for (int i = m - 1; i > 0; i--) {
				for (int j = 0; j < n; j++) {
					if (visited[i][j]) {
						boardchar[i][j] = ' ';
						for (int k = i - 1; k >= 0; k--) {
							if (!visited[k][j]) {
								char temp = boardchar[i][j];
								boardchar[i][j] = boardchar[k][j];
								boardchar[k][j] = temp;
								visited[i][j] = false;
								visited[k][j] = true;
								break;
							}
						}
					}
				}
			}
		}
		return answer;

	}

	public static void main(String[] args) {
		System.out.println(
        solution(6, 6, new String[] { "TTFATT", "RRFACC", "RRRFCC", "TRRFAA", "TTMMAA", "TMMMTT" }));
	}

}

7. 추석 트래픽(난이도: 상)

문제링크: https://programmers.co.kr/learn/courses/30/lessons/17676

코딩테스트 연습 - [1차] 추석 트래픽 | 프로그래머스

알고리즘 설명:

응답 완료시간이 오름차순으로 정렬되어 있으므로 응답 시작을 기준으로 1초 사이에 응답 완료시간이 있는 트래픽의 개수를 구하여 가장 큰 값을 찾는 문제이다.

• split을 사용하여 문자열을 분으로 바꾸었다.
• trafficValue의 이름을 가진 배열로 트래픽의 시작과 종료시간을 넣었다.
• 맨 뒤 index를 기준으로 트래픽 시작시간 ~ 트래픽 시작시간 -1 사이에 트래픽 종료시간이 있는 index들의 개수를 카운팅한다.
• 카운팅된 값들 중 가장 큰 값이 answer

막혔던 지점:

시작시간을 기준으로 문제를 풀려고 하다보니 너무 복잡해졌다.

다음 부터는 문제에서 주어진 조건(종료시간 오름차순)을 기준으로 생각하고 풀어야겠다.

 

코드(Java)

package test;

public class TrafficTest {

	public static int solution(String[] lines) {

		double[][] trafficValue = new double[lines.length][2];
		for (int i = 0; i < lines.length; i++) {
			String[] subSpace = lines[i].split(" ");
			String[] hour = subSpace[1].split(":");

			trafficValue[i][1] = Double.parseDouble(hour[0]) * 60 * 60;
			trafficValue[i][1] += Double.parseDouble(hour[1]) * 60;

			trafficValue[i][1] += Double.parseDouble(hour[2]);

			String duringSec = subSpace[2].replace("s", "");

			trafficValue[i][0] = trafficValue[i][1] - Double.parseDouble(duringSec) + 0.001;
			trafficValue[i][0] = Double.parseDouble(String.format("%.3f", trafficValue[i][0]));

		}

		int answer = 0;

		for (int i = trafficValue.length - 1; i >= 0; i--) {
			int count = 0;
			double endrange = trafficValue[i][0];
			double startrange = (trafficValue[i][0] - 1) + 0.001;
			startrange = Double.parseDouble(String.format("%.3f", startrange));

			for (int j = trafficValue.length - 1; j >= 0; j--) {
				if (trafficValue[j][1] < startrange)
					break;
				if (endrange >= trafficValue[j][0]) {
					count++;
				}
			}
			if (answer < count)
				answer = count;
		}
		return answer;
	}

	public static void main(String[] args) {
		/*
		 * String lines[] = { "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" };
		 */
		String lines[] = { "2016-09-15 01:00:04.002 2.0s", "2016-09-15 01:00:07.000 2s" };
		System.out.println(solution(lines));

	}

}