씅의 기록하는 개발노트

문제출처

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

문제풀이

정규표현식과 완전탐색으로 풀이하면 되는 문제입니다. DFS시 저는 bitmask를 visit배열 대신 사용해서 풀이했습니다. 

문제를 풀이할때 제가 생각한 알고리즘은 다음과 같습니다.

1. *문자를 정규표현식에 맞게 .로 치환

2. pattern과 matcher를 사용해 응모자 아이디와 매칭되는지 판단

3. 매칭이 된다면 길이가 같은지 판단

4. 이미처리한 사항(방문한 사항)이라면 건너뛰고 처리하지 않았다면 dfs함수를 호출

5. banned_id와 지금까지 찾아낸 제제된 아이디의 사이즈(bannedIdSize)가 같다면 set에 추가

6. 중복없는 set의 사이즈를 반환

비트마스크가 익숙하지 않은 분이면 아래 포스팅을 참고하시면 도움이 되실겁니다.

2019/01/28 - [Algorithm 이론] - [Bitmask] 비트마스크 기초

레벨3문제인데 개인적으로 어렵게 풀이한 문제였습니다. 정규표현식과 비트마스크 개념을 다시 확인할 수 있던 문제

소스코드

https://github.com/sw93/algorithm/blob/master/Programmers/%EC%B9%B4%EC%B9%B4%EC%98%A4%20-%20%EB%B6%88%EB%9F%89%20%EC%82%AC%EC%9A%A9%EC%9E%90.java

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

// * 문자 . 로 치환
// Pattern matcher를 사용해 해당되는 문자인지 판단
// 해당된다면 길이도 같은지 확인하고 이미 추가한 아이디가 아니라면 set에 추가
class Solution {
    private static HashSet<Integer> set;
    public int solution(String[] user_id, String[] banned_id) {
        set = new HashSet<>();
        dfs(user_id, banned_id, 0, 0, 0);
        return set.size();
    }
    
    private static void dfs(String[] user_id, String[] banned_id, int index, int bannedIdSize, int visitBit) {
        if (bannedIdSize == banned_id.length) {
            set.add(visitBit);
            return;
        }
        
        for (int i=0; i<user_id.length; i++) {
            String changeBannedId = banned_id[index].replace("*", ".");
            Pattern pattern = Pattern.compile(changeBannedId);
            Matcher matcher = pattern.matcher(user_id[i]);
            
            // 정규 표현식에 매칭되고 길이가 같으면
            if (matcher.find() && user_id[i].length() == banned_id[index].length()) {
                
                // 이미 방문한 것은 건너뜀
                if ((visitBit & (1<<i)) == 1<<i) continue;
                dfs(user_id, banned_id, index+1, bannedIdSize+1, (visitBit | (1<<i)));
            }
        }
    }
}

문제출처

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

문제풀이

문제를 풀기 이전에 이분탐색에 대해 익숙하지 않다면 이글을 먼저 읽는게 이해가 빠르실 겁니다.

[Algorithm] - [프로그래머스 43238] - 입국심사

입국심사 문제와 같이 이분탐색을 이용한 문제입니다. 

한번에 건너뛸 수 있는 칸수 = k
stones = 징검다리 값

lowCount = 최소 인원수

highCount = 최대 인원수

averageCount = 건널 수 있는 인원수

문제의 핵심은 이분탐색 문제로 재해석 하는 것이다. 건넌 사람이 3명인경우 stone[i] - 3의 값이 양수여야 다리가 남아있는 경우이다. 이외의 경우 징검다리가 사라진 경우여서 건너뛰어야 하며 건너뛰는 징검다리 수를 저장하는 jumpCount변수에 저장한다.

jumpCount 변수는 최대 점프 횟수인 k를 넘을 수 없으며 k이상인 경우 최대 건너뛸 수 있는 사람의 제한을 줄여 재 탐색한다.

n = 건넌 사람

stones[i] = 징검다리 값

문제를 푸는데 입국심사 문제가 큰 도움이 되었다. 이해가 잘 되지 않는다면 위에있는 입국심사 포스팅을 읽고 문제를 풀어보면 더 쉬울거라 생각된다.

소스코드

https://github.com/sw93/algorithm/blob/master/Programmers/%EC%B9%B4%EC%B9%B4%EC%98%A4%20-%20%EC%A7%95%EA%B2%80%EB%8B%A4%EB%A6%AC%20%EA%B1%B4%EB%84%88%EA%B8%B0.java

class Solution {
   
    public int solution(int[] stones, int k) {
        int answer = 0;
        
        // 건너뛰는 최소 인원수
        int lowCount = 1;   
        
        // 건너뛰는 최대 인원수
        int highCount = Integer.MAX_VALUE;  
        
        // 이분탐색에서 이용할 중간값
        int averageCount = (lowCount + highCount) / 2;  
        
        while (lowCount <= highCount) {
            averageCount = (lowCount + highCount) / 2;
            
            // 건너뛴 징검다리 수
            int jumpCount = 0;
            for (int i=0; i<stones.length; i++) {
                if (stones[i] - averageCount <= 0) {
                    jumpCount++;
                } else {
                    jumpCount = 0;
                }
                
                // k개 이상 건너뛰어야 하는경우 건너뛰는 인원수를 반으로 줄인다
                if (jumpCount >= k) {    
                    highCount = averageCount - 1;
                    break;
                }
            }
            
            // 건너뛴 징검다리 개수가 k개 미만인 경우 인원수를 늘린다.
            if (jumpCount < k) {
                lowCount = averageCount + 1;
                answer = lowCount;
            }  
        }

        return answer;
    }
}

문제출처

https://programmers.co.kr/learn/courses/30/lessons/43238

문제풀이

이분탐색을 응용한 문제입니다. 처음에 왜 이문제가 이분탐색인지 몰랐는데 다른 블로그를 보면서 이해할 수 있었습니다. 이 문제는 times배열에 각 심사관이 한명을 심사하는데 걸리는 시간 정보가 주어지고 n명을 모두 심사할 때 심사시간의 최소값을 구하는 문제입니다.

n의 최대값은 10억이며 times의 최대 크기는 10만입니다. n의 값이 크기 때문에 일반적인 풀이로는 풀수 없고 시간복잡도를 줄일 수 있는 답안을 생각해야 합니다.

입출력 예시로 주어진 대로 6명을 심사하고 각각 7분, 10분이 걸리는 2명의 심사관이 있는 경우를 생각해보겠습니다.

걸리는 시간을 기준으로 이분탐색을 할 예정이며 최소시간은 1분 최대시간은 n X 가장 오래걸리는 심사관의 시간 으로 시작했습니다. 이 문제에서 이분탐색을 할 때 핵심은 mid시간 이내에 심사가능한 인원의 수는 sum(mid / times[i])라는 것입니다.

최소시간을 left, 최대시간을 right변수에 담아 평균 시간을 mid에 저장합니다. 즉 1 // 30 // 60 으로 이분탐색을 시작합니다.

mid = 30

30분 이내에 심사가능한 인원은 (30 / 7) + (30 / 10) 으로  4 + 3 = 7명입니다.

7은 6보다 크므로 6명을 심사하기 위해서는 30분보다 더 적은 시간에도 가능한 것을 유추할 수 있습니다. 즉 rigth 변수값을 mid - 1을 해 29로 저장한뒤 재탐색 합니다. 이때 29분에는 6명을 심사할 수 없을 수도 있기 때문에 answer에 mid값을 저장합니다.

mid = (1 + 29) / 2 = 15

1 // 30 // 60 에서 1 // 15 // 30 으로 탐색범위가 반으로 줄었습니다. 15분 이내에 심사가능한 인원은 (15 / 7) + (15 / 10) = 2 + 1 = 3명입니다. 3은 6보다 작으므로 6명을 심사하기 위해서는 15분보다는 더 시간이 필요한 것을 알 수 있습니다. 이분탐색을 위해 left 값을 1에서 16으로 바꾼 후 탐색을 다시 시작합니다.

mid = (16 + 30) / 2 = 22

1 // 15 // 30 에서 16 // 22 // 30 으로 탐색범위가 또 반으로 줄었습니다. 22분 이내에 심사가능한 인원은 (22 / 7) + (22 / 10) = 3 + 2 = 5명입니다. 5는 6보다 작으므로 6명을 심사하기 위해서는 22분보다 시간이 더 필요합니다. left 값을 16에서 23으로 바꾼 뒤 탐색을 다시 시작합니다.

반복해서 나아가면

mid = (23 + 30) / 2 = 26

....

mid =  (26 + 30) / 2 = 28

(28 / 7) + (28 / 10) = 4 + 2 = 6명이므로 28이 정답임을 알 수 있습니다.

각각의 탐색과정에서 범위가 반으로 줄고 있으므로 시간복잡도는 O(logN)입니다.

소스코드

https://github.com/sw93/algorithm/blob/master/Programmers/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4%20-%20%EC%9E%85%EA%B5%AD%EC%8B%AC%EC%82%AC.java

import java.util.Arrays;
class Solution {
    public long solution(int n, int[] times) {
        long answer = 0;
        Arrays.sort(times);
        
        long left = 1;
        long right = (long)n * times[times.length - 1];
        while (left <= right) {
            long mid = (left + right) / 2;
            long count = 0;
            
            // 심사 가능한 인원 = 시간 / 심사하는데 걸리는 시간
            for (int i=0; i<times.length; i++) {
                count += mid / times[i];
            }
            
            // mid 시간동안 심사한 인원이 n명보다 적은 경우 시간이 더 필요
            if (count < n) {
                left = mid + 1;
            } else { // 심사한 인원이 n명 이상인 경우 시간을 줄여도 됨
                right = mid - 1;
                answer = mid;
            }
        }
        
        return answer;
    }
}