Problem

• 문제 링크

징검다리를 건널 수 있는 프렌즈 인원수를 구하는 문제입니다.

징검다리는 stones 배열로 주어지며, 한번 발을 디딜때마다 1 씩 줄어듭니다.

프렌즈들은 0 인 돌을 만나면 최대 k 만큼 가장 가까운 돌로 점프할 수 있습니다.

Solution

이분탐색을 응용한 파라메트릭 서치(Parametric Search) 를 활용하는 문제입니다.

건널 수 있는 프렌즈들의 최대, 최소값은 stones 배열의 최대, 최소값과 동일합니다.

stones 배열의 최대값이 5, 최소값이 1 이라고 할 때 1 과 5 로 이진탐색을 돌립니다.

중간값 mid 가 3 이기 때문에 프렌즈 인원을 3 으로 정해두고 전부 다 건널 수 있는지 탐색합니다.

만약 다 건널 수 있다면 3 보다 작은 1, 2 도 전부 건널 수 있기 때문에 3 ~ 5 사이의 값을 탐색합니다.

이런식으로 건널 수 있는 프렌즈 인원 중 가장 큰 값이 남을때까지 계속 하면 됩니다.

건널 수 있는지 판단하는 canCross 함수는 돌에서 프렌즈 값을 뺀 숫자를 갖고 음수가 최대 k 만큼 연속하지 않은지 확인하면 됩니다.

Java Code

import java.util.*;

class Solution {
    public int solution(int[] stones, int k) {
        int max = Integer.MIN_VALUE;
        int min = Integer.MAX_VALUE;
        
        for (int stone : stones) {
            max = Math.max(max, stone);
            min = Math.min(min, stone);
        }
        
        return binarySearch(stones, k, min, max);
    }
    
    private int binarySearch(int[] stones, int k, int lo, int hi) {
        if (hi == lo) return lo;
        
        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            
            if (canCross(stones, k, mid)) {
                lo = mid + 1;
            } else {
                hi = mid;
            }
        }
        
        return lo - 1;
    }
    
    private boolean canCross(int[] stones, int k, int friends) {
        int passCount = 0;
        
        for (int stone : stones) {
            if (stone - friends < 0) {
                passCount++;
            } else {
                passCount = 0;
            }
            
            if (passCount == k) return false;
        }
        
        return true;
    }
}

Problem

• 문제 링크

총 방의 갯수 k 와 고객들이 선택한 방이 주어질 때 각 방별로 배정된 사람들의 목록을 return 하는 문제입니다.

방은 고객들이 선택한 순서대로 정해집니다.

A 고객이 선택한 방을 이미 B 고객이 선택했다면 A 고객은 다음 방을 배정받습니다.

A 고객이 선택한 방번호보다 크고 아무도 선택하지 않은 가장 작은 방번호가 다음 방입니다.

Solution

정확성 뿐만 아니라 효율성까지 고려해야 하는 문제입니다.

단순하게 풀이한다면 Set 자료구조에 선택된 방들을 담아두고 중복된 방을 선택한 경우 +1 하며 전체 스캔하는 것으로 정확성은 통과할 수 있다.

하지만 k 가 최대 10^12 이기 때문에 O(n)으로 매번 검색을 해버리면 효율성을 하나도 통과할 수 없습니다.

다음 방을 선택하는 과정에서 O(n) 으로 스캔하는 건 어쩔수가 없습니다.

그렇다면 한번 선택한 방은 다음번에 선택할 때 스캔을 최소 로 한다면 정확성을 통과할 수 있습니다.

접근법은 우선 HashMap 을 선언하여 <방 번호 : 다음 방 번호> 이렇게 저장해두는 겁니다.

고객이 방을 선택했을 때 map.containsKey() 로 다음 방을 바로 찾을 수가 있죠.

다음으로 할 일은 다음 방을 갱신해주는 겁니다.

예를 들어 방이 6 번까지 있고 [1, 2, 3, 4] 는 이미 선택되었다고 가정합니다.

다음 고객이 1 을 선택하였을 때 5 번 방이 비어있는 걸 알기 위해 1 -> 2 -> 3 -> 4 -> 5 순서대로 가야 하지만

다음 방을 미리 저장해둔다면 1 -> 5 로 바로 스캔할 수 있습니다.

그리고 1 번을 갱신하는 김에 2, 3, 4 방도 똑같이 다음 방이 5 니까 갱신해줍니다.

이것을 재귀로 구현한 게 long findEmptyRoom(long room) 함수입니다.

Java Code

import java.util.*;

class Solution {
    Map<Long, Long> map = new HashMap<>();

    public long[] solution(long k, long[] room_number) {
        int n = room_number.length;
        long[] answer = new long[n];

        for (int i = 0; i < n; i++) {
            answer[i] = findEmptyRoom(room_number[i]);
        }

        return answer;
    }
    
    private long findEmptyRoom(long room) {
        if (!map.containsKey(room)) {
            map.put(room, room + 1);
            return room;
        }
        
        long nextRoom = map.get(room);
        long emptyRoom = findEmptyRoom(nextRoom);
        map.put(room, emptyRoom);
        return emptyRoom;
    }
}

Problem

• 문제 링크

사용자 목록 user_id 와 불량 사용자 목록 banned_id 가 주어졌을 때 당첨에서 제외되어야 하는 사용자 목록의 경우의 수를 구하는 문제입니다.

Solution

최대 길이가 8 이기 때문에 완전 탐색을 해도 괜찮습니다.

사용자 목록에서 DFS 로 banned_id.length 만큼의 사용자를 뽑습니다.

뽑힌 사용자들을 banned_id 와 비교하여 일치하는 케이스를 구하면 됩니다.

중복된 값은 모두 하나의 경우가 되기 때문에 set 에 넣어서 필터링 해줍니다.

boolean isSameString(String a, String b) 함수는 두 String 의 일치 여부를 판단합니다.

boolean isBannedUsers(Set<String> set, String[] banned_id) 함수는 뽑힌 set 과 banned_id 목록을 비교하여 경우의 수에 해당되는지 판단합니다.

어차피 중복은 제거되기 때문에 banned_id 와 일대일 비교를 하기 위해 set 을 LinkedHashSet 으로 선언했습니다.

Java Code

import java.util.*;

class Solution {
    private Set<Set<String>> result;
    
    public int solution(String[] user_id, String[] banned_id) {
        result = new HashSet<>();
        dfs(user_id, banned_id, new LinkedHashSet<>());
        return result.size();
    }
    
    private void dfs(String[] user_id, String[] banned_id, Set<String> set) {
        if (set.size() == banned_id.length) {
            if (isBannedUsers(set, banned_id)) {
                result.add(new HashSet<>(set));
            }
            
            return;
        }
        
        for (String userId : user_id) {
            if (!set.contains(userId)) {
                set.add(userId);
                dfs(user_id, banned_id, set);
                set.remove(userId);
            }
        }
    }
    
    private boolean isBannedUsers(Set<String> set, String[] banned_id) {
        int i = 0;
        
        for (String user : set) {
            if (!isSameString(user, banned_id[i++])) {
                return false;
            }
        }
        
        return true;
    }
    
    private boolean isSameString(String a, String b) {
        if (a.length() != b.length()) {
            return false;
        }
        
        for (int i = 0; i < a.length(); i++) {
            if (b.charAt(i) == '*') continue;
            
            if (a.charAt(i) != b.charAt(i)) {
                return false;
            }
        }
        
        return true;
    }
}

Problem

• 문제 링크

집합이 문자열 s 로 주어졌을 때 해당 집합이 표현하는 튜플을 배열에 담아 return 하는 문제입니다.

Solution

이 문제의 핵심은 개수가 많은 값 순서대로 배열을 정렬하는 겁니다.

집합 별로 분리할 필요 없이 먼저 숫자만 구해줍니다.

s 는 '{', '}', ',' 와 숫자로만 이루어져 있다고 문제에 나와있기 때문에 중괄호를 제거하고 쉼표를 기준으로 split 해줍니다.

그리고 각 값들을 Key 로 하고 개수를 value 로 한 keyMap 을 만들어줍니다.

개수를 기준으로 정렬해야하기 때문에 keyMap 에서 key, value 를 뒤집은 valueMap 을 만들어줍니다.

그리고 answer 배열에 valueMap 에 있는 값을 순서대로 넣어주면 됩니다.

숫자의 갯수가 key 로 되어 있기 때문에 배열의 뒤에서부터 넣어주면 개수가 가장 많은 숫자가 맨 앞으로 오게 됩니다.

Java Code

import java.util.*;

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

        String[] strs = s.replace("{", "").replace("}", "").split(",");

        for (String str : strs) {
            int key = Integer.parseInt(str);
            keyMap.compute(key, (k, v) -> v == null ? 1 : v + 1);
        }
        
        keyMap.forEach((k, v) -> valueMap.put(v, k));
        
        int n = valueMap.size();
        int[] answer = new int[n];

        for (int i = 1; i <= n; i++) {
            answer[n-i] = valueMap.get(i);
        }
        
        return answer;
    }
}

Problem

• 문제 링크

2 x 2 배열의 보드판이 주어집니다.

인형을 뽑는 위치를 정하는 moves 배열이 정해집니다.

위치는 가로만 정해지며, 해당 위치의 가장 위에 있는 인형만 뽑을 수 있습니다.

뽑은 인형은 바구니에 순서대로 쌓이며, 같은 인형이 연달아 들어온 경우 두 인형은 사라집니다.

사라진 인형의 갯수를 구해야 합니다.

Solution

단순한 구현 문제입니다.

moves 를 순회하며 인형 뽑기, 바구니에 넣기, 사라지게 하기를 순서대로 구현합니다.

보드의 높이만큼 확인해서 0 이 아닌 좌표를 찾습니다.

뽑은 인형 자리는 0 으로 바꿔줍니다.

바구니는 Stack 으로 관리하면 됩니다.

한 가지 주의할 점은 사라진 횟수가 아닌 사라진 인형의 갯수를 구하는 문제이기 때문에 answer += 2 로 해주어야 합니다.

Java Code

import java.util.*;

class Solution {
    public int solution(int[][] board, int[] moves) {
        int answer = 0;
        Stack<Integer> stack = new Stack<>();
        
        for (int move : moves)  {
            int row = move - 1;
        
            for (int col = 0; col < board.length; col++) {
                if (board[col][row] == 0) continue;
                
                int doll = board[col][row];
                board[col][row] = 0;
                
                if (!stack.isEmpty() && stack.peek() == doll) {
                    stack.pop();
                    answer += 2;
                } else {
                    stack.push(doll);
                }
                
                break;
            }
        }
        
        return answer;
    }
}