IT Docs

자료 구조와 개발 언어는 알고 있다는 가정하에 코딩 테스트만 이야기하려 한다.

예전에는 코딩 테스트를 공부하기 위해 한 문제를 두고 직접 생각해보며 생각하는 힘을 기르려고 노력하였다.

그래서 하루 한 문제를 푸는데 3시간을 사용하곤 했다.

돌이켜보면 멍청했던 것 같다.

사실 코딩 테스트의 알고리즘은 생각한다고 되는 게 아닌 거 같다. 천재들은 될 수도..

알고리즘이 수학 공식과 비슷하다고 생각했다. 

결국 문제를 풀어내는 기준은 공식 아느냐 모르느냐 차이인 거 같다.

이제는 모르는 문제를 마주하더라도 5분 이상 시간을 사용하지 않으려고 한다.

사실 실전에서 문제를 만나면 문제를 읽는 도중 혹은 문제를 다 읽고 나면 어떤 알고리즘을 적용해야 하는지 머릿속에 떠오른다.

그걸 오래 본다고 모르는 게 갑자기 머릿속에 주입되지는 않을 것이다.

5분 동안 생각해보고 안 되면 모르는 문제라고 생각하고 어떤 알고리즘을 적용하는지 보는 게 더 효율적인 공부 방법이라고 생각한다.

왜 이 알고리즘을 적용하는지?, 최적화는 어떻게 하는지? 등 기술적인 고민을 더 하는 게 개발자로서 공부가될 거 같다.

결론은 모른다고 기죽지 말자 다른 사람들도 처음은 있었을 것이다.

모름에서 아는 것으로 넘어가는 시간을 최소한으로 줄여 효율적인 학습을 하자.

문제 링크 : 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;
    }
}