IT Docs

문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/1829
레벨 : Level 2
분류 : 2017 카카오코드 예선

이 문제는 가장 큰 컬러의 면적과 컬러의 종류를 구하는 문제이다.

문제를 보고 모든 위치를 전부 탐색하는 문제라는 것을 파악해 bfs로 풀이를 시도하였다.

하지만 몇개월만에 다시 시작하는 코딩 테스트라 bfs, dfs를 다 까먹었다...

앞으로 코딩테스트는 한번 할 때 쭉 해야 할 거 같다.

구체적인 설명은 하지 않겠다 bfs를 알고 있다면 쉽게 풀 수 있는 문제이다.

아래와 같이 풀이를 공유합니다.

import java.util.*;

class Solution {
    public static class Node {
        int x, y;
        Node(int x, int  y) {
            this.x = x;
            this.y = y;
        }
    }
    
    private static int cnt, x, y;
    private static boolean[][] visit;
    private static int[] dx = {0, -1, 0, 1};
    private static int[] dy = {-1, 0, 1, 0};    
    private static Queue<Node> que = new LinkedList<>();
    
    public int[] solution(int m, int n, int[][] picture) {

        visit = new boolean[m][n];
        x = m;
        y = n;
        int max = Integer.MIN_VALUE;
        int type = 0;
        
        for(int i = 0; i < m; i++) {
            for(int j = 0; j < n; j++) {
                if(visit[i][j] || picture[i][j] == 0) continue;
                
                cnt = 1;
                type++;
                bfs(picture, i, j);                
                max = Math.max(max, cnt);
            }
        }
        
        int[] answer = new int[2];
        
        answer[0] = type;
        answer[1] = max;
        
        return answer;
    }
    
    public void bfs(int[][] pic, int i, int j) {
        visit[i][j] = true;
        que.add(new Node(i, j));

        int source = pic[i][j];

        while(!que.isEmpty()) {
            Node node = que.poll();

            for(int k = 0; k < 4; k++) {
                int xx = node.x + dx[k], yy = node.y + dy[k];
                if(xx < x && yy < y && xx >= 0 && yy >= 0) {
                    int target = pic[xx][yy];
                    if(!visit[xx][yy] && source == target) {
                        visit[xx][yy] = true;
                        cnt++;
                        que.add(new Node(xx, yy));
                    }
                }
            }
        }
    }
}

문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/42888
레벨 : Level 2
분류 : 2019 KAKAO BLIND RECRUITMENT

이 문제는 채팅방의 이용자의 입장 이력을 출력하는 문제이다.

입력되는 배열의 최대 길이는 100,000만이라는 것을 보고 o(n)의 시간 복잡도로 풀어야 한다는 생각을 했다.

그래서 입력된 배열에서 닉네임을 추출하여 user라는 Map에 저장하였다.

 - Enter와 Change라는 커맨드일때만 닉네임이 생거나 변경되었다.

입력된 배열에서 Enter, Leave만 추출하여 최종 변경된 닉네임이 들어왔는지 나갔는지 판단하면 어렵지 않게 해결할 수 있다.

아래와 같이 풀이를 공유합니다.

import java.util.*;

class Solution {
    public String[] solution(String[] record) {
        String[] answer = {};
        
        Map<String, String> user = new HashMap<>();
        
        for(int i = 0; i < record.length; i++) {
            String[] info = record[i].split(" ");
            
            String com = info[0];
            String uid = info[1];
            
            if(com.equals("Enter") || com.equals("Change")) {
                user.put(uid, info[2]);
            }
        }
        
        List<String> list = new ArrayList<>();
        
        for(int i = 0; i < record.length; i++) {
            String[] info = record[i].split(" ");
            
            String com = info[0];
            String uid = info[1];
            
            if(com.equals("Enter")) {
                list.add(user.get(uid) + "님이 들어왔습니다.");
            }else if(com.equals("Leave")) {
                list.add(user.get(uid) + "님이 나갔습니다.");
            }
        }
        
        answer = list.toArray(new String[list.size()]);
        
        return answer;
    }
}

문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/12905
레벨 : Level 2
분류 : 연습문제

이 문제는 주변 요소를 이용하여 정사각형의 크기를 구하는 문제이다.

DFS, BFS와 비슷해 보이긴 했지만 전혀 구상해내지 못하였다. 

그래서 다른 사람의 풀이를 보고 코드를 분석해가며 풀었고 이 유형의 문제를 처음 접한 것 같다.

다른 사람의 문제 풀이 방식을 학습하고 나서 구현은 쉽게 할 수 있었다.

하지만 예외를 찾지 못해서 한참을 헤맸는데 찾은 예외는 1X1를 대처하지 못하였다.

그래서 1X1을 대처하기 위해 결과 배열의 크기를 1행 1열씩 더 크게 정의하여 해결하였다.

아래와 같이 풀이를 공유합니다.

class Solution
{
    public int solution(int [][]board)
    {
        int answer = Integer.MIN_VALUE;
        
        int[][] map = new int[board.length+1][board[0].length+1];
        
        for(int i = 0; i < board.length; i++) {
            for(int j = 0; j < board[0].length; j++) {
                map[i+1][j+1] = board[i][j];
            }
        }
        
        
        for(int i = 1; i < map.length; i++) {
            for(int j = 1; j < map[0].length; j++) {
                if(map[i][j] != 0) {
                    int min = Math.min(map[i-1][j-1], Math.min(map[i-1][j], map[i][j-1])) + 1;
                    map[i][j] = min;
                    answer = Math.max(answer, min);    
                }
            }
        }
        
        return answer * answer;
    }
}

문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/12911
레벨 : Level 2
분류 : 연습문제

이 문제는 2진수의 1의 개수를 구하는 것이 핵심이다.

소스를 보면 getBinarycountOne이라는 2진수에서 1을 구하는 함수를 만들어서 해결했으나 다른 사람들의 풀이를 보면서 복습하다가 Integer에 bitCount 함수를 알게 되었다. 

bitCount함수가 1의 개수를 카운팅 해주어 커스텀 함수를 만들 필요가 없게 되었다.

아래와 같이 풀이를 공유합니다.

import java.util.*;

class Solution {
    public int solution(int n) {
        int nc = Integer.bitCount(n);
        
        while(true) {
            if(nc == Integer.bitCount(++n)) break;
        }
        
        return n;
	}
    
    public int getBinaryCountOne(int n) {
        int cnt = 0;
        while(n > 0) {
            int o = n % 2;
            n /= 2;
            if(o == 1) cnt++;
        }
        
        return cnt;
    }
}