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

1. N진수 게임

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

코딩테스트 연습 - [3차] n진수 게임 | 프로그래머스

알고리즘 설명:

10진수를 주어진 진수로 바꾼 뒤 한 글자씩 list에 넣어 알려줘야 하는 개수만큼 반복문을 돌리면 되는 문제이다.

• 시작은 무조건 0 - answerlist에 넣고 시작
• list를 두 개 사용한 이유는 진수로 변환할 때 나눈 나머지를 차례대로 list에 넣어서 결과를 보면 list에 값이 반대로 들어가 있다. 그래서 십진수를 진수로 나눈 나머지들을 list에 넣은 뒤 reverse를 해주어야 진수 변환이 정상적으로 들어간다.
• 십진수의 변환이 완료되면 answerlist에 그대로 넣어 누적시켜준다.
• answerlist의 크기가 m(게임에 참가한 인원)* t(구해야 할 답의 개수) 보다 커지기 전까지 반복
• 튜브의 순서 인덱스는 p-1 이므로 탐색 시작 인덱스를 p-1로 하고 인덱스를 m씩 늘려가며 답을 탐색
• 혹시나 하는 생각에 찾는 값의 개수가 t(구해야 할 답의 개수)와 같아졌을 때 탐색 반복문을 break 한다.

코드(Java)

package test;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class NumberGame {
	public static String solution(int n, int t, int m, int p) {
		String answer = "";
		List<Character> list = new ArrayList<>();
		List<Character> listanswer = new ArrayList<>();
		int i=1;
		listanswer.add('0');
		while(listanswer.size()<(m*t)){
			int num = i;
			while (num != 0) {
				int insert = num % n;
				char listadd;
				
				if (insert >= 10) {
					listadd = (char) ('A' + (insert % 10));

				} else {
					listadd = (char) ('0' + insert);
				}
				list.add(listadd);
				num = num / n;
			}
			Collections.reverse(list);
			i++;
			listanswer.addAll(list);
			list.clear();
		}
	
		int index = p-1;
		int count=0;
		while(index<listanswer.size()) {
			answer += listanswer.get(index).toString();
			index+=m;
			count++;
			if(count==t)break;
			
		}
		return answer;
	}

	public static void main(String[] args) {
		System.out.println(solution(2, 4, 2, 1));
	}

}

---

2. 압축

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

코딩테스트 연습 - [3차] 압축 | 프로그래머스

알고리즘 설명:

Hashmap에 추가 되는 단어들을 저장하면서 정답을 누적해가면 쉽게 구할 수 있다.

• 문제에서 주어진 것처럼 알파벳 26자를 Hashmap에 저장하고 시작(HashMap이 사전 역할)
• 주어진 문자열의 인덱스에 하나씩 접근
  • Hashmap에 존재하지 않은 경우가 나올 때까지 접근한 인덱스에서 길이를 늘려가면서 탐색
  • print에는 출력해야 될 값 즉 Hashmap에 들어있는 값들을 계속 경신해준다.
• Hashmap에 존재하지 않은 경우가 나오면 그 문자열을 Hashmap저장
• 탐색한 만큼 탐색 인덱스를 옮겨준다.
• list에 있는 값들을 모두 더하면 answer!

코드(Java)

package test;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class Compression {
	  public static int[] solution(String msg) {
	      Map<String,Integer> map = new HashMap<>();
	      List<Integer>list = new ArrayList<>();
	      int w=26;
	      for(int i=0;i<26;i++) {
	    	  String key = Character.toString((char) ('A'+i));
	    	  map.put(key, i+1);
	      }
	      
	      char[] msgarr = msg.toCharArray();
	      for(int i=0;i<msgarr.length;) {
	    	  String temp = Character.toString(msgarr[i]);
	    	  int searchIndex = 0;
	    	  int print =0;
	    	  while(map.containsKey(temp)){
	    		  print = map.get(temp);
	    		  searchIndex++;
	    		  if((i+searchIndex)>(msgarr.length-1))break;
	    		  temp+=Character.toString(msgarr[i+searchIndex]);
	    	  }
	    	  list.add(print);
	    	  map.put(temp, ++w);
	    	  i+=searchIndex;
	      }
	      int[] answer = new int[list.size()];
	      for(int i=0;i<list.size();i++) {
	    	  answer[i] = list.get(i);
	      }
	      return answer;
	  }

	public static void main(String[] args) {
		int[] answer= solution("KAKAO");
		for(int i=0;i<answer.length;i++) {
			System.out.println(answer[i]);
		}
		
	}

}

---

3. 파일명 정렬

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

코딩테스트 연습 - [3차] 파일명 정렬 | 프로그래머스

알고리즘 설명:

문자열을 Head, Number, Tail로 분리하는 전처리 후 Sorting을 하면 해결

• 숫자가 나오기 전까지 Head, 숫자가 Number, 나머지 Tail로 split 해준다.
• Arrays.sorting, Comparator를 사용하여 Head 순으로 정렬하되 Head가 같은 경우 Number로 정렬을 한다.
• 정렬된 순서대로 출력하면 끝

막혔던 지점:

해설을 읽어보니 안정 정렬을 사용해야지만 문제가 풀린다던데 다행히 자바에서 제공해주는 메서드인 Arrays.sort는 안정 정렬인 삽입 정렬과 병합 정렬을 사용하여서 문제가 풀렸다.

또 문제의 조건인 Number의 최대 길이가 5 자라는 조건을 적용을 하지 않았더니 일부 테스트 케이스가 틀렸다고 나왔다. (정말 무섭다 무서워...)

코드(Java)

package test;

import java.util.Arrays;
import java.util.Comparator;

public class FilenameSorting {
	public static String[] solution(String[] files) {
		String[] answer = new String[files.length];
		String[][] headNumTail = new String[files.length][3];

		for (int i = 0; i < files.length; i++) {

			headNumTail[i][0] = files[i];
			headNumTail[i][1] = files[i].split("[0-9]")[0];
			files[i]=files[i].replace(headNumTail[i][1], "");
			
			headNumTail[i][1] = headNumTail[i][1].toUpperCase();
			char[] arr = files[i].toCharArray();
			
			headNumTail[i][2] = "";
            for(char c : arr) {
                if(Character.isDigit(c) && headNumTail[i][2].length() < 5) {
                	headNumTail[i][2] += c;
                } else {
                    break;
                }
            }
		}

		Arrays.sort(headNumTail, new Comparator<String[]>() {
			@Override
			public int compare(String[] o1, String[] o2) {

				return o1[1].equals(o2[1]) ? Integer.parseInt(o1[2]) - Integer.parseInt(o2[2]) : o1[1].compareTo(o2[1]);
			}
		});

		for (int i = 0; i < files.length; i++) {
			answer[i] = headNumTail[i][0];
		}
		return answer;
	}
	
	public static void main(String[] args) {
		
		  String[] answer = solution( new String[] { "img12.png", "img10.png",
		  "img02.png", "img1.png", "IMG01.GIF", "img2.JPG" });
		  
		  for (int i = 0; i < answer.length; i++) { System.out.println(answer[i]); }
		 
		answer = solution(
				new String[] { "F-5 Freedom Fighter", "B-50 Superfortress", "A-10 Thunderbolt II", "F-14 Tomcat" });
		for (int i = 0; i < answer.length; i++) {
			System.out.println(answer[i]);
		}
	}

}

---

4. 방금 그 곡

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

코딩테스트 연습 - [3차] 방금그곡 | 프로그래머스

알고리즘 설명:

• InFo라는 클래스를 만들어서 재생된 곡 정보들의 이름과 멜로디를 관리
• 반올림한 맬로디는 소문자로 바꾸어 하나의 문자로 비교 가능하게 전처리
• 방송된 시간만큼 맬로디를 반복시킨 문자열에 네오의 멜로디가 들어 있는 경우 list에 Info 객체로 add 시킨다.
• list를 info 객체의 music 길이 즉 방송 길이 순으로 정렬을 한 면 인덱스 0 값이 정답

코드(Java)

package test;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;

public class RecentSong {

	public static String solution(String m, String[] musicinfos) {
		m = m.replace("C#", "c").replace("D#", "d").replace("F#", "f").replace("G#", "g").replace("A#", "a");
		List<Info> matchList = new ArrayList<>();

		for (int i = 0; i < musicinfos.length; i++) {

			String[] sp = musicinfos[i].split(",");
			String[] startTime = sp[0].split(":");
			String[] endTime = sp[1].split(":");
			int end = (Integer.parseInt(endTime[0]) * 60 + Integer.parseInt(endTime[1]));
			int start = Integer.parseInt(startTime[0]) * 60 + Integer.parseInt(startTime[1]);
			int time = end - start;
			String music = "";
			sp[3] = sp[3].replace("C#", "c").replace("D#", "d").replace("F#", "f").replace("G#", "g").replace("A#",
					"a");

			int j = 0;
	        for(int k = 0; k < time ; k++) {
	            j = k % sp[3].length();
	            music += sp[3].charAt(j);
	        }

			if (music.contains(m)) {
				matchList.add(new Info(sp[2], music));
			}
		}
		Collections.sort(matchList, new Comparator<Info>() {

			@Override
			public int compare(Info o1, Info o2) {
				return o2.music.length() - o1.music.length();
			}
		});

		return matchList.size() > 0 ? matchList.get(0).name : "(None)";
	}

	public static class Info {
		String name;
		String music;

		public Info(String name, String music) {
			this.name = name;
			this.music = music;
		}
	}

	public static void main(String[] args) {
		solution("CC#BCC#BCC#BCC#B", new String[] { "03:00,03:30,FOO,CC#B", "04:00,04:08,BAR,CC#BCC#BCC#B" });
	}

}

 

---

5. 자동완성

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

코딩테스트 연습 - [3차] 자동완성 | 프로그래머스

알고리즘 설명:

사전 순으로 정렬한 뒤 앞 뒤 값들만 비교하면 풀리는 문제

• Comparator를 사용하여 배열을 정렬한다.
  • 비교 문자열을 문자 배열로 바꾸고 한 문자씩 비교하면서 다른 경우가 존재하면 그 글자를 기준으로 sort
  • 비교 문자열 중 하나가 다른 하나에 포함되는 경우라면 길이가 짧은 순으로 sort
• 문자열 배열의 처음 index(0)와 끝 index(words.length -1)는 각각 뒤 index와 앞 index만 비교, 나머지 index들은 앞 뒤 index 둘 다 비교
• 앞 뒤 index들과 앞에서부터 다른 문자가 나올 때까지 같은 문자의 개수를 카운트한다.
• 앞 뒤 중 더 카운트 개수가 큰 값을 answer에 누적시켜준다.
• 앞 index가 현재 index에 포함되는 경우라면 카운트 개수가 1개 덜 나오기 때문에 그 경우에 카운트 +1

 

막힌 지점:

해설에서는 Trie 알고리즘으로 문제를 풀면 된다고 나와있지만 그냥 그대로 Trie를 사용하면 정답 100%가 나오지 않는다. 예상으로는 깊이 설정을 해줘야 하는 것 같은데 확실히 모르겠다...

 

코드(Java)

package test;

import java.util.Arrays;
import java.util.Comparator;

public class AutomaticComplete {

	public static int solution(String[] words) {
		int answer = 0;
		Arrays.sort(words, new Comparator<String>() {

			@Override
			public int compare(String beforeWord, String aftereWord) {
				char[] before = beforeWord.toCharArray();
				char[] after = aftereWord.toCharArray();

				for (int i = 0; i < before.length && i < after.length; i++) {
					if (before[i] != after[i])
						return before[i] - after[i];
				}

				return before.length > after.length ? 1 : -1;
			}

		});

		for (int i = 0; i < words.length; i++) {
			char[] word = words[i].toCharArray();
			int countBefore = 0;
			int countAfter = 0;

			if (i != 0) {
				char[] before = words[i - 1].toCharArray();
				countBefore = 0;
				for (int j = 0; j < word.length && j < before.length; j++) {
					countBefore++;
					if (word[j] != before[j])
						break;

					if (j == before.length - 1)
						countBefore++;
				}
			}

			if (i != words.length - 1) {
				char[] next = words[i + 1].toCharArray();
				countAfter = 0;
				for (int j = 0; j < word.length && j < next.length; j++) {
					countAfter++;
					if (word[j] != next[j])
						break;
				}
			}

			if (countBefore > countAfter)
				answer += countBefore;
			else
				answer += countAfter;


		}

		return answer;
	}

	public static void main(String[] args) {

		System.out.println(solution(new String[] { "go", "gone", "guild" }));

		System.out.println(solution(new String[] { "abc", "def", "ghi", "jklm" }));
		System.out.println(solution(new String[] { "word", "war", "warrior", "world" }));

	}

}