[카카오 기출] 2019 카카오 개발자 겨울 인턴십 문제 풀이

하반기 코딩테스트가 곧 몰아칩니다..

스스로 해결한 문제도 있고, 그렇지 못한 문제도 있지만

모두가 이해할 수 있게끔 풀이하면서 복기할 목적으로 문제 풀이를 해보려 합니다.

레벨 순으로 가면서 풀었던 코드를 분석해보겠습니다.

 

1. 크레인 인형뽑기 게임 (Level 1)

https://school.programmers.co.kr/learn/courses/30/lessons/64061

프로그래머스

import java.util.*;

class Solution {
    // 인형 담을 바구니
    Stack<Integer> basket = new Stack<>();
    
    public int solution(int[][] board, int[] moves) {
        int answer = 0;
        
        for (int move : moves) {
            int r = dollIdx(board, move - 1, board.length);
            
            // 인형이 없는 경우, 다음 move 확인
            if (r == -1) continue;
            
            // 바구니의 TOP과 집은 인형 비교, 같다면 바구니 pop, 다르면 집은 인형 push
            int doll = board[r][move - 1];
            if (basket.size() >= 1) {
                if (basket.peek() == doll) { 
                    basket.pop();
                    answer += 2;
                }
                else basket.push(doll);
            } else basket.push(doll);
            
            // 보드 인형 위치 수정
            board[r][move - 1] = 0;
        }
        return answer;
    }
    
    private int dollIdx(int[][] board, int r, int c) {
        // 인형이 위치한 행을 반환하는 함수, 없으면 -1 반환
        for (int i = 0; i < c; i++) 
            if (board[i][r] != 0) return i;
        return -1;
    }
}

접근방법

"만약 같은 모양의 인형 두 개가 바구니에 연속해서 쌓이게 되면 두 인형은 터뜨려지면서 바구니에서 사라지게 됩니다." 라는 문구를 보고 스택을 떠올렸습니다. 

스택을 인형담을 바구니로 사용하고, 매 move마다 최상단의 인형 위치를 가져와서 스택의 값과 비교하고 있습니다.

 

이 코드에서, 매 move마다 최상단 인형 위치를 찾는 함수가 조금 불편해보입니다.

그렇다면 각 번호별 최상단 인형 위치를 저장하고 있다면 어떨까요?

어차피 최상단 인형을 뺐다면, 다음은 어느 위치를 확인해야 할 지 알고 있습니다. (바로 밑이죠)

문제 조건 또한 최대 30번까지의 격자가 존재한다고 했으므로 무리가 없어보입니다.

 

그렇다면 아래와 같이 변경할 수 있겠습니다.

import java.util.*;

class Solution {
    // 인형 담을 바구니입니다.
    static Stack<Integer> basket = new Stack<>();
    // 격자가 몇 번까지 존재하는지 저장합니다.
    static int N;
    // 각 번호별 최상단 인형의 행을 저장합니다.
    static int[] tops;
    
    public int solution(int[][] board, int[] moves) {
        N = board.length;
        tops = new int[N];
        
        // 0으로 초기화하면, 해당 번호의 tops값이 지정된지 판단할 수 없어 -1로 초기화했습니다.
        Arrays.fill(tops, -1);

        for (int i = 0; i < N; i++)
            for (int j = 0; j < N; j++)
                // 해당 위치에 인형이 있고, 해당 번호의 tops값이 없는 경우 갱신합니다.
                if (board[i][j] != 0 && tops[j] == -1)
                    tops[j] = i;

        int answer = 0;
        for (int move : moves) {
            // tops 값을 가져오고, 다음 접근을 위해 후위 연산을 수행합니다.
            int r = tops[move - 1]++;

            // 범위를 벗어난 경우, 즉 인형이 없는 경우는 넘어갑니다.
            if (r >= N) continue;

            // 집은 인형과 바구니의 TOP을 비교합니다.
            // 같다면 바구니를 pop, 다르면 집은 인형을 push합니다.
            // pop한다면, 집은 인형과 바구니의 TOP을 터트리는 것이므로 2개를 카운트합니다.
            int doll = board[r][move - 1];
            if (basket.size() >= 1 && basket.peek() == doll) {
                    basket.pop();
                    answer += 2;
            } else basket.push(doll);
        }
        
        return answer;
    }
}

 

---

2. 튜플 (Level 2)

https://school.programmers.co.kr/learn/courses/30/lessons/64065

프로그래머스

import java.util.*;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

class Solution {
    public int[] solution(String s) {
        Map<Integer, Integer> map = new HashMap<>();

        Pattern pattern = Pattern.compile("\\d+");
        Matcher matcher = pattern.matcher(s);

        while(matcher.find()) {
            int num = Integer.parseInt(matcher.group(0));
            map.put(num, map.getOrDefault(num, 0) + 1);
        }

        ArrayList<Integer> tuple = new ArrayList<>(map.keySet());
        tuple.sort((value1, value2) -> (map.get(value2).compareTo(map.get(value1))));

        return tuple.stream().mapToInt(i -> i).toArray();
    }
}

접근방법

문제의 예시를 보았을 때, 가장 많이 나온 숫자순으로 튜플이 표현되는 것을 파악할 수 있었습니다.

따라서 주어지는 문자열에서 모든 숫자의 빈도를 먼저 구해야겠다 생각했습니다. 중복되는 원소가 없는 튜플을 표현하고 있다는 조건이 있기에 빈도를 구해도 문제되지 않겠다싶었습니다.

이후 나타난 숫자를 모두 리스트에 저장하고, 이를 빈도 수 기준으로 내림차순으로 정렬합니다.

이 리스트는 곧 정답이 됩니다. (int[]형 반환을 위해 스트림으로 형 변환을 수행합니다.)

 

이건 더 개선할 방법이 떠오르지 않네요..

 

---

3. 불량 사용자 (Level 3)

https://school.programmers.co.kr/learn/courses/30/lessons/64064

프로그래머스

import java.util.*;
import java.util.regex.Pattern;

class Ban {
    HashSet<HashSet<String>> banSet;
    ArrayList<ArrayList<String>> bannedIdList;

    public Ban() {
        banSet = new HashSet<>();
        bannedIdList = new ArrayList<>();
    }

    public void makeSet(String banned_id, String[] user_id) {
        // 정규표현식 사용을 위해 변환합니다.
        // .은 1문자를 의미합니다!
        String regex = banned_id.replace('*', '.');
        ArrayList<String> tmpList = new ArrayList<>();

        for (String user : user_id) {
            boolean isMatch = Pattern.matches(regex, user);
            if (isMatch) tmpList.add(user);
        }
        bannedIdList.add(tmpList);
    }

    public void findBadUser(HashSet<String> set, int size) {
        if (size == bannedIdList.size()) {
            banSet.add(new HashSet<>(set));
            return;
        }

        // list번째 제재 아이디를 set에 추가합니다.
        for (String id : bannedIdList.get(size)) {
            if (set.contains(id)) continue;
            set.add(id);
            findBadUser(set, size + 1);
            set.remove(id);
        }
    }

    public int getCount() {
        return banSet.size();
    }
}

class Solution {
    public int solution(String[] user_id, String[] banned_id) {
        Ban b = new Ban();

        for (String ban : banned_id)
            b.makeSet(ban, user_id);

        b.findBadUser(new HashSet<>(), 0);

        return b.getCount();
    }
}

접근방법

문제에서 문자를 뭐로 가리고, 문자열에 대한 설명이 많은 것으로 보았을 때, 문자열 문제임은 확실해보입니다.

먼저, 불량 사용자 목록을 통해 불량 아이디일 수 있는 후보군을 만들어야 합니다. 

그리고 만들어진 후보군들로부터 제재 아이디 목록을 만들고, 이를 최종 Set에 저장합니다.

이 Set의 크기가 곧 경우의 수를 의미합니다.

 

이때, DFS를 이용해 불량 사용자 목록 하나당 사용자 한 명씩 매핑하여 제재 아이디 목록을 생성하도록 합니다.

 

다른 풀이를 보니, 어쨌든 Set의 포함 여부를 판단하고, 넣을지 말지를 결정하는 문제이므로

이에 대해 비트마스킹을 사용하여 더 빠른 시간복잡도를 가지도록 구현하기도 하더군요.

 

---

4. 징검다리 건너기 (Level 4)

https://school.programmers.co.kr/learn/courses/30/lessons/64062

프로그래머스

import java.util.*;

class StoneBridge {
    public int crossBridge(int[] stones, int k) {
        int friends = 0;
        int min = Integer.MAX_VALUE;
        int max = 0;

        // min과 max 사이에 건널 수 있는 최대 인원 수가 존재합니다.
        for (int stone : stones) {
            if (stone < min) min = stone;
            if (stone > max) max = stone;
        }

        while (min <= max) {
            int mid = (min + max)/2;

            // 건널 수 있다면, min을 1 증가시키고 반복합니다.
            if (canCrossOver(stones, k, mid)) {
                min = mid + 1;
                friends = mid;
            } else {
                max = mid - 1;
            }
        }

        return friends;
    }

    private boolean canCrossOver(int[] stones, int k, int n) {
        int cantOver = 0;

        for (int stone : stones) {
            // 건널 수 없는 돌
            if (stone < n) cantOver++;
            else cantOver = 0;

            // 건널 수 없는 돌다리가 k개 연속이라면 건널 수 없습니다.
            if (cantOver == k) return false;
        }

        return true;
    }
}

class Solution {
    public int solution(int[] stones, int k) {
        StoneBridge sb = new StoneBridge();
        
        return sb.crossBridge(stones, k);
    }
}

접근방법

처음에는 단순히 1명이 지나갈 때마다 모든 디딤돌의 숫자를 1씩 감소시키는 코드를 짰던 것 같습니다. 당연히 효율성에서 틀렸습니다.

 

다른 접근방법을 생각해보겠습니다.

 

문제의 조건에서, "다음으로 밟을 수 있는 디딤돌이 여러 개인 경우, 무조건 가장 가까운 디딤돌로만 건너뛸 수 있습니다." 라고 명시했습니다. 따라서 마음대로 k 만큼 점프할 수 있는 것이 아닙니다.

숫자가 적힌 디딤돌은 무조건 순서대로 밟힙니다.

디딤돌이 1개이고, 적힌 숫자가 1이라면, k 또한 1입니다.

그렇다면 2명이 건널 수 있을까요? 절대 불가능합니다.

따라서 디딤돌에 적힌 최소 숫자와 최대 숫자 사이에 건널 수 있는 최대 인원수가 존재할 것입니다.

 

그럼 범위는 정해졌고, 이 범위 내에서 다시 한 명씩 건너면서 숫자를 감소시키는 코드를 짜면 될까요?

이 또한 실패했습니다.

 

그렇다면 범위 내에서 효율적으로, 건널 수 있는 인원 수를 탐색해야겠습니다.

어 ... 주어진 범위 내의 어떤 특정 숫자를 찾는 문제로 치환될 수 있겠네요.

그리고 이를 위해 이분 탐색 알고리즘을 사용할 수 있겠습니다!

 

최소 숫자와 최대 숫자가 left, right가 되고,

이 둘의 중간이 mid가 되겠습니다.

그리고 mid명이 건널 수 있는지 확인하면서,

건널 수 있다면 min을 mid + 1로 변경하면서 건널 수 있는 최대 인원을 구할 수 있습니다.

 

그리고 건널 수 있는지 확인하는 로직은

• 디딤돌 배열을 탐색하면서, mid보다 작은 디딤돌을 발견하면 카운트를 증가합니다.
• mid와 같거나 큰 디딤돌이라면 카운트를 0으로 돌립니다.
• 만약 카운트가 주어진 k와 같아진다면, 연속적으로 mid명이 건널 수 없는 디딤돌이 존재한다는 의미이므로 false를 반환합니다!

 

---

5. 호텔 방 배정 (Level 5)

https://school.programmers.co.kr/learn/courses/30/lessons/64063

프로그래머스

import java.util.*;

class Solution {
    Map<Long, Long> roomMap = new HashMap<>();
    
    public long[] solution(long k, long[] room_number) {
        long[] answer = new long[room_number.length];

        for (int i = 0; i < room_number.length; i++)
            answer[i] = getRoom(room_number[i]);
        
        return answer;
    }
    
    private long getRoom(long room) {
        // 해당 방이 아직 배정 받지 않은 경우입니다.
        if (!roomMap.containsKey(room)) {
            roomMap.put(room, room + 1);
            return room;
        }

        // 해당 방이 이미 배정된 경우, 재귀 호출을 통해 빈 방을 찾습니다.
        long emptyRoom = getRoom(roomMap.get(room));
        roomMap.put(room, emptyRoom);
        
        return emptyRoom;
    }
}

접근방법

원하는 방 번호가 있다면 배정받지만, 그렇지 않다면 비어있지 않은 다음 방을 배정받는다는 조건을 보고

학교 강의에서 배웠던 Union-Find 알고리즘이 떠올랐습니다.

상위 루트 방 번호를 가지도록 만들어 연결시키는 방법으로,

해당 번호와 그 루트 번호가 같다면, 아직 비어있는 방이고

다르다면, 루트 번호를 가지고 다시 탐색하도록 합니다.

 

그림을 그려 표현한다면,

마지막 1번 배정 시, 1번에 해당하는 루트를 찾아보니 1번이 아니라 2번을 가르키고 있습니다.

즉, 1번은 비어있지 않고, 2번 방을 확인하라는 의미입니다!

이와 같이 다음 방 번호를 재귀적으로 확인하여 비어있는 방을 배정받을 수 있도록 합니다.

 

---

아직 많이 모자라서 코드가 많이 깔끔하지 않을 수 있습니다 .. 😂

혹시 더 효율적인 방법이나 질문 있으시면 댓글 편하게 남겨주시면 감사하겠습니다..!!