문제집: 2018 KAKAO BLIND RECRUITMENT

[LV. 1]

1. 다트 게임

생각한 문제 유형 : 문자열 쪼개기, 배열 활용, 조건문
소요 시간: 약 1시간

막혔던 부분 :

• 점수를 어떻게 저장해서 처리할 것인가
• 10을 어떻게 처리할 것인가

해결 :

• 어차피 3회만 진행하는 게임이기 때문에 3개짜리 배열을 담아서 각 회의 점수를 저장
• idx를 활용해 각 회차를 마킹, S, D, T가 나오게 되면 idx를 ++ 처리해줌
  그런데 * 또는 #이 나오게 되면, idx를 한 번 줄여주고, 값 처리 후 다시 idx++
• Switch ~ case 구문을 활용해서 1, S, D, T, *, # 인 경우 처리하고, defalut 값으로
  숫자 처리
  단, 1일 때는 다음 나오는 문자가 0인지, 그 외인지에 따라 다르게 처리해줌

코드

class Solution {
    public int solution(String dartResult) {
        int answer = 0;
        
        char[] score = new char[dartResult.length()];
		int[] temp = new int[3];

		for (int i = 0; i < score.length; i++) {
			score[i] = dartResult.charAt(i);
		}

		int idx = 0;

		for (int i = 0; i < score.length; i++) {
			switch (score[i]) {

			case 'S':
				idx++;
				break;
			case 'D':
				temp[idx] = (int) Math.pow(temp[idx], 2);
				idx++;
				break;
			case 'T':
				temp[idx] = (int) Math.pow(temp[idx], 3);
				idx++;
				break;

			case '*':
				idx--;
				if (idx == 0) {
					temp[idx] *= 2;
				} else {
					temp[idx - 1] *= 2;
					temp[idx] *= 2;
				}
				idx++;
				break;

			case '#':
				idx--;
				temp[idx] *= -1;
				idx++;
				break;
			
			case '1' :
				// 10일 때
				if(score[i+1] == '0') {
					temp[idx] = 10;
					i++; // 0은 건너뛰자
				} else {
					temp[idx] = 1;
				}
				break;
			default :
				temp[idx] = score[i] - '0';
			}

		}
		for(int i = 0; i < temp.length; i++) {
			answer += temp[i];
		}
        
        
        return answer;
    }
}

---

2. 비밀 지도

생각한 문제 유형 : 문자열 처리, 2진수 변환, 문자열 포맷팅, long과 int형 구분, 연산자 사용
소요 시간: 약 30분

막혔던 부분 :

• 변환 시 비는 수 만큼 어떻게 0으로 처리할 것인가?
• 제출 후 1회 실패 > 큰 숫자를 넣었더니, 처리하지 못하는 문제

해결 :

• String.format("%0"+n+"d", num); 으로 포맷을 맞춤
• Int형을 Long형으로 변환하여 처리

코드

class Solution {
    public String[] solution(int n, int[] arr1, int[] arr2) {
        String[] answer = new String[n];
        
        for(int i = 0; i < n; i++){
            String num1 = Long.toBinaryString(arr1[i]);
            String num2 = Long.toBinaryString(arr2[i]);
            num1 = String.format("%0"+n+"d", Long.parseLong(num1));
            num2 = String.format("%0"+n+"d", Long.parseLong(num2));
            
            String s = "";
            for(int j = 0; j < n; j++){
                int x = num1.charAt(j) - '0';
                int y = num2.charAt(j) - '0';
                
                if((x|y) == 1) {
                    s += "#";
                } else{
                    s += " ";
                } 
            }
            answer[i] = s;
        }
        
        
        return answer;
    }
}

---

[LV. 2]

1. 캐시

생각한 문제 유형 : List, 페이지 교체 알고리즘
소요 시간: 약 15분

막혔던 부분 :

• 대소문자 상관 없이 비교

해결 :

• equalsIgnoreCase를 통해 대소문자 상관 없이 비교 가능
• 또한 프로그래머스는 상단에 import까지 해주어야 List같은 유틸을 사용 가능...

코드

import java.util.ArrayList;

class Solution {
    public int solution(int cacheSize, String[] cities) {
        int answer = 0;
        // List 생성
        ArrayList<String> list = new ArrayList<>();
        
        // 도시 수 만큼 반복
		for(int i = 0; i < cities.length; i++) {
			// 캐시 사이즈가 list의 최대 크기
			// list안에 대소문자 구별 없이 같은 도시가 있으면
			boolean check = false;
			for(int j = 0; j < list.size(); j++) {
				if(list.get(j).equalsIgnoreCase(cities[i])) {
					// j 지우고
					list.remove(j);
					// 맨 뒤에 추가
					list.add(cities[i]);
					// 시간은 1초만 소요
					answer += 1;
					check = true;
					break;
				}
			}
			
			if(!check) {
				list.add(cities[i]);
				answer += 5;
			}
			
			if(list.size() > cacheSize ) {
				while(list.size() != cacheSize) {
					list.remove(0);
				}
			}
			
		}
        
        return answer;
    }
}

---

2. 프렌즈 4블록

생각한 문제 유형 : BFS, 그래프 탐색
소요 시간: 약 2시간

막혔던 부분 :

• BFS탐색을 하면서 어떻게하면 블럭을 깨면서 탐색을 진행할 수 있을까...
  answer에 답을 올리는 부분에서 많은 고민

• 또한, 어차피 4개의 블록만 진행하면 되기 때문에 4방 탐색을 진행하지 않고 우, 우하, 하 세 방향만 탐색하면서
  Queue에 넣으며 진행하였다

• 솔직히 벽돌깨기랑 비슷했는데, 조건 주는게 너무 헷갈려서 많은 시간을 썼다

해결 :

• copyMap이라는 새로운 맵을 생성해서 사용하고, 마지막에 블록을 중력으로 땡겨준 뒤
  map을 copyMap으로 복사해서 진행

• TestCase 5, 6, 10, 11이었나? 4개 정도 틀린 코드를 제출했었다
  틀린 이유는 블럭을 땡겨주면서 한 번 땡겼으면 break로 종료하고 나갔어야 했는데, 종료처리를 해주지 않아서 틀렸었다

코드

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

class Solution {
    
    static class Node {
        int r, c;
        char name;
        
        public Node(int r, int c, char name){
            this.r = r;
            this.c = c;
            this.name = name;
        }
        
    }
    
    public int solution(int m, int n, String[] board) {
        int answer = 0;
        char[][] map = new char[m][n];
        char[][] copyMap = new char[m][n];
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                map[i][j] = board[i].charAt(j);
                copyMap[i][j] = board[i].charAt(j);
            }
        }
        boolean[][] visited = new boolean[m][n];
        int[] dr = {0, 1, 1};
        int[] dc = {1, 1, 0};
            
        Queue<Node> q = new LinkedList<>();
        
        
        while(true) {
        int temp = answer; // 종료 조건을 주기 위한 임시 변수
        visited = new boolean[m][n];
        visited[0][0] = true;       
        q.offer(new Node(0, 0, map[0][0])); // 시작 지점 q에 삽입
        
        // 파괴 조건 생성
        while(!q.isEmpty()){
            Node cur = q.poll();
            int nowR = cur.r;
            int nowC = cur.c;
            char item = cur.name;
            if(nowR == m-1 || nowC == n-1) {
                continue;               
            }
            
            boolean check = true;
            
            for(int d = 0; d < 3; d++){
                int nr = nowR + dr[d];
                int nc = nowC + dc[d];
                
                if(bc(nr, nc, m, n)){
                    if(!visited[nr][nc]) {
                    visited[nr][nc] = true;
                    q.offer(new Node(nr, nc, map[nr][nc]));
                    }
                    if(item != map[nr][nc]){
                        check = false;
                    }
                }      
            }
            // 위의 검증을 통과했으면
            if(check) {
                if(copyMap[nowR][nowC] != '0'){
                    copyMap[nowR][nowC] = '0';    
                    answer++;
                }
                
                for(int nd = 0; nd < 3; nd++){
                    int nnr = nowR + dr[nd];
                    int nnc = nowC + dc[nd];
                        
                    if(bc(nnr, nnc, m, n) && copyMap[nnr][nnc] != '0') {
                        copyMap[nnr][nnc] = '0';
                        answer++;
                    }
                }                    
            } 
        }
 
            
        // 중력 조건 생성
        for(int c = 0; c < n; c++){
            for(int r = m-1; r >= 0; r--){
                if(copyMap[r][c] == '0'){
                    for(int k = r-1; k >= 0; k--){
                        if(copyMap[k][c] != '0'){
                            copyMap[r][c] = copyMap[k][c];
                            copyMap[k][c] = '0';
                            break;
                        }
                    }
                }
            }
        }
            
        // 맵을 copyMap으로 변경
        for(int r = 0; r < m; r++){
            for(int c = 0; c < n; c++){
                map[r][c] = copyMap[r][c];
            }
        }    
        
    
        if(temp == answer) break; // 위의 조건식을 돌렸는데 temp가 안바뀌었다? 그럼 더 이상 파괴할 것이 없는 것
        }
        
        return answer;
    }
    
    public static boolean bc(int nr, int nc, int m, int n){
        return nr >= 0 && nc >= 0 && nr < m && nc < n;
    }
    
}

---

3. 뉴스 클러스터링

생각한 문제 유형 : 문자열, HashMap
소요 시간: 약 2시간

막혔던 부분 :

• 하.. 제일 힘들었다. HashMap이 익숙하지가 않아서, 기초적인 문법들을 따로 보면서 했다
  특히 중복 부분을 어떻게 처리할지..
  그래서 각 문장의 HashMap을 만들고 새로운 HashMap 하나를 더 만들었다
  그래서 교집합인 부분은 양쪽 다 존재하는 경우의 최소값을 넣어줬다

• 최대값은 조건을 걸어서 양 쪽 다 존재하는 경우, 한 쪽만 존재하는 경우를 나누어서 담아주었다
  새로운 HashMap은 초기화 해주었음

해결 :

• HashMap 3개 사용, 배열도 3개 사용, 탐색용으로 배열을 쓰고 값 저장용으로 HashMap3을 썼다
  메모리 낭비가 심할지도...?

• 다 풀고 다른 사람 풀이 보니까 스트림이란게 있는데 뭔지 잘 모르겠다..

코드

import java.util.HashMap;
import java.util.Arrays;

class Solution {
    public int solution(String str1, String str2) {
        int answer = 0;
        
        // 1. 문자열을 각각 쪼개서 배열에 담는다
        String[] arr1 = new String[str1.length()-1];        
        String[] arr2 = new String[str2.length()-1];
        String[] arr3 = new String[str1.length()+str2.length()-2];
        
        Arrays.fill(arr1, "");
        Arrays.fill(arr2, "");
        Arrays.fill(arr3, "");
        

        for(int i = 0; i < arr1.length; i++){
            char c1 = str1.charAt(i);
            char c2 = str1.charAt(i+1);
 
            // 알파벳이 아닌 범위(아스키 코드로 바꿔서)는 continue 해버리기
            // 대문자 A는 17 ~ 42
            // 소문자 a는 49 ~ 74
            if((c1 - '0' >= 17 && c1 - '0' <= 42) || (c1 - '0' >= 49 && c1 - '0' <= 74)) {
                if((c2 - '0' >= 17 && c2 - '0' <= 42) || (c2 - '0' >= 49 && c2 - '0' <= 74)){
                    String s = str1.substring(i, i+2);
                    arr1[i] = s.toUpperCase();     
                } 
            }  
        }
        
        for(int i = 0; i < arr2.length; i++){
            char c1 = str2.charAt(i);
            char c2 = str2.charAt(i+1);
 
            // 알파벳이 아닌 범위(아스키 코드로 바꿔서)는 continue 해버리기
            // 대문자 A는 17 ~ 42
            // 소문자 a는 49 ~ 74
            if((c1 - '0' >= 17 && c1 - '0' <= 42) || (c1 - '0' >= 49 && c1 - '0' <= 74)) {
                if((c2 - '0' >= 17 && c2 - '0' <= 42) || (c2 - '0' >= 49 && c2 - '0' <= 74)){
                    String s = str2.substring(i, i+2);
                    arr2[i] = s.toUpperCase(); // 그냥 다 대문자로 바꿔버리자
                } 
            }  
        }
        
        // 2. hashmap을 만들어서 key 값과 value값의 쌍으로 만든다(중복제거)
        HashMap<String, Integer> hashmap1 = new HashMap<>();
        HashMap<String, Integer> hashmap2 = new HashMap<>();
        HashMap<String, Integer> hashmap3 = new HashMap<>();
        
        for(int i = 0; i < arr1.length; i++){
            if(!hashmap1.containsKey(arr1[i])) {
                hashmap1.put(arr1[i], 1);    
            } else {
                hashmap1.put(arr1[i], hashmap1.get(arr1[i])+1);
            }
        }
        
        for(int i = 0; i < arr2.length; i++){
            
            
            if(!hashmap2.containsKey(arr2[i])) {
                hashmap2.put(arr2[i], 1);    
            } else {
                hashmap2.put(arr2[i], hashmap2.get(arr2[i])+1);
            }
        }
        
        // 탐색을 위해 두 배열을 합쳐서 탐색용으로 쓰자
        for(int i = 0; i < arr1.length; i++ ) {
            arr3[i] = arr1[i];
        }
        for(int i = arr1.length; i < arr3.length; i++){
            arr3[i] = arr2[i-arr1.length];
        }
        
        // 3. 두 hashmap을 비교해서 같은 key값의 value값을 통해 합집합과 교집합 원소의 수를 만든다
        // double형이어야 소수점 검사 가능
        double small = 0;
        double big = 0;
        
        for(int i = 0; i < arr3.length; i++){
            if(arr3[i] == "") continue;
            // 두 해시맵 모두 있을 때는 교집합 처리
            if(hashmap1.containsKey(arr3[i]) && hashmap2.containsKey(arr3[i])) {
                hashmap3.put(arr3[i], Math.min(hashmap1.get(arr3[i]), hashmap2.get(arr3[i])));
            }            
        }
        
        for(int v : hashmap3.values()) {
            small += v;
        }
        // 비워주고
        hashmap3.clear();
        for(int i = 0; i < arr3.length; i++){
            if(arr3[i] == "") continue;
            // 두 해시맵 중 하나라도 있으면 값 더해주기
            if(hashmap1.containsKey(arr3[i]) && hashmap2.containsKey(arr3[i])) {
                hashmap3.put(arr3[i], Math.max(hashmap1.get(arr3[i]), hashmap2.get(arr3[i])));
            }       
            if(!hashmap1.containsKey(arr3[i]) && hashmap2.containsKey(arr3[i])){
                hashmap3.put(arr3[i], hashmap2.get(arr3[i]));
            }
            if(hashmap1.containsKey(arr3[i]) && !hashmap2.containsKey(arr3[i])){
                hashmap3.put(arr3[i], hashmap1.get(arr3[i]));
            }
        }
        
        for(int v : hashmap3.values()) {
            big += v;
        }
        
        // 4. 자카드 유사도를 출력한다
        
        if(big == 0) {
            answer = 65536;
        }
        else{
            answer = (int) Math.floor((small / big) * 65536);    
        }

        return answer;
    }
}