[Java] 프로그래머스_64064 : 불량 사용자

완전탐색

불량 사용자 - Level3

 

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

프로그래머스

 

 

 

풀이1

import java.util.*;

class Solution {
    
    private void count(int idx, Set<String> banned,
                      String[][] bans, Set<Set<String>> banSet) {
        if (idx == bans.length) {
            banSet.add(new HashSet<>(banned));
            return;
        }
        
        for (String id : bans[idx]) {
            if (banned.contains(id)) continue;
            banned.add(id);
            count(idx + 1, banned, bans, banSet);
            banned.remove(id);
        }
    }
    
    public int solution(String[] user_id, String[] banned_id) {
        String[][] bans = Arrays.stream(banned_id)
            .map(banned -> banned.replace('*', '.'))
            .map(banned -> Arrays.stream(user_id)
                    .filter(id -> id.matches(banned))
                    .toArray(String[]::new))
            .toArray(String[][]::new);
        
        Set<Set<String>> banSet = new HashSet<>();
        count(0, new HashSet<>(), bans, banSet);
        return banSet.size();
    }
}

 

=> 이 코드는 주어진 user_id와 banned_id로 가능한 모든 경우의 수를 찾아내는 문제를 해결하는 프로그램이다.

ㄴ 주어진 banned_id에서 *를 정규표현식의 .으로 변환하고, 해당 패턴에 맞는 user_id를 찾아내어 가능한 모든 조합을 찾아냈다.

*를 .으로 변환하는 이유
ㄴ *를 .으로 변환하는 이유는 정규표현식에서 .이 어떤 문자든지 하나의 문자와 매치되는 와일드카드로 사용되기 때문이다.
ㄴ 여기서는 *가 0개 이상의 어떤 문자열이라는 의미를 가지고 있기 때문에, .으로 변환하여 모든 문자 하나에 대응되도록 한다.
(예를 들어, a*c라는 패턴은 ac, abc, abbc, ... 등과 매치된다. 그래서 *를 .으로 변환하여 정규표현식으로 패턴 매칭을 할 때, 어떤 문자든지 1개가 올 수 있도록 한다.)

https://namu.wiki/w/%EC%A0%95%EA%B7%9C%20%ED%91%9C%ED%98%84%EC%8B%9D

 

ㄴ 이를 위해 재귀적인 방식을 사용하고, 중복된 조합을 피하기 위해 Set을 활용한다.

 

 

count 메서드

ㄴ 재귀적으로 가능한 모든 조합을 찾아내는 역할을 한다.

ㄴ idx는 bans 배열의 인덱스를 나타내며, banned는 현재까지 선택된 사용자 아이디를 담고 있는 Set다.

ㄴ 재귀 호출이 완료되면 banSet에 현재까지의 조합을 추가한다.

private void count(int idx, Set<String> banned,
                      String[][] bans, Set<Set<String>> banSet) {

 

ㄴ idx 와 bans 는 상태 변수이다. bans 는 불량 사용자 아이디별로 매칭되는 사용자 아이디 정보를 담은 매개변수이며, banSet 은 찾은 조합을 저장할 때 매개변수이다.

 

if (idx == bans.length) {
    banSet.add(new HashSet<>(banned));
    return;
}

for (String id : bans[idx]) {
    if (banned.contains(id)) continue;
    banned.add(id);
    count(idx + 1, banned, bans, banSet);
    banned.remove(id);
}

 

ㄴ banned에 현재까지 선택한 사용자 아이디가 들어 있기 때문에 종료 조건에 도달했을 때 해당 Set에는 사용자 아이디 조합이 들어있다.

ㄴ 이를 복사하여 banSet에 넣어주면 조합을 찾을 수 있다. 

 

• idx : 현재 처리 중인 bans 배열의 인덱스
• banned : 현재까지 선택된 사용자 아이디들의 집합
• bans : 각 금지 아이디에 해당하는 사용자 아이디들을 담은 2차원 배열
• banSet : 서로 다른 조합의 사용자 아이디 집합을 저장하는 Set<Set<String>>

if (idx == bans.length) {
    banSet.add(new HashSet<>(banned));
    return;
}

 

ㄴ 모든 금지 아이디에 대한 처리가 끝났을 때, 현재까지 선택된 사용자 아이디 집합을 banSet에 추가

 

• for (String id : bans[idx]) : 현재 금지 아이디에 해당하는 사용자 아이디들을 하나씩 순회
• if (banned.contains(id)) continue; : 이미 선택된 사용자 아이디라면 무시하고 다음 아이디를 확인
• banned.add(id); : 현재 아이디를 선택 집합에 추가
• count(idx + 1, banned, bans, banSet); : 재귀적으로 다음 금지 아이디에 대한 사용자 아이디를 선택하도록 호출
• banned.remove(id); : 현재 아이디를 선택 집합에서 제거하여 다른 경우의 수도 고려할 수 있도록 함

for (String id : bans[idx]) {
    if (banned.contains(id)) continue;
    banned.add(id);
    count(idx + 1, banned, bans, banSet);
    banned.remove(id);
}

ㄴ 금지 아이디에 대한 사용자 아이디들을 하나씩 확인하면서 재귀 호출한다.

 

solution 메서드

ㄴ 이 메서드는 주어진 banned_id에서 가능한 모든 경우의 수를 찾아내는 역할을 한다.

ㄴ 먼저 bans 배열을 생성하여 각 banned_id에 대해 정규표현식을 적용하고, 해당 패턴에 맞는 user_id를 찾아 2차원 배열에 저장한다.

ㄴ 그런 다음 count 메서드를 호출하여 가능한 모든 조합을 찾아내고, 이를 저장하는 banSet을 반환한다.

 

String[][] bans = Arrays.stream(banned_id)
            .map(banned -> banned.replace('*', '.'))
            .map(banned -> Arrays.stream(user_id)
                    .filter(id -> id.matches(banned))
                    .toArray(String[]::new))
            .toArray(String[][]::new);

 

ㄴ 첫 번째 예시 데이터를 이용하여 위 코드를 실행하면, 첫 번째 배열은 "frd"에 매칭되는 "frodo"와 "fradi"를 포함하고, 두 번째 배열은 "abc1**"에 매칭되는 "abc123"을 포함한다.

ㄴ 아래와 같이 2차원 배열이 만들어진다.

bans = [    ["frodo", "fradi"],
    ["abc123"]
]

 

 

=> 완전 탐색을 통해 가능한 모든 조합을 찾아내는 방식을 사용했다. 하지만 이러한 방식은 입력이 커질수록 계산 시간이 길어지는 단점이 있다.

 

 

 

 

Level3은 아직 나에게 어려운 레벨인 것 같다.

 

Set 안에 Set 을 넣는 것이 생소했고, stream 문법이 아직 익숙치 않아 쉽지 않았다.

아직 메서드를 생성해서 문제를 푸는 것도 익숙치 않아 쉽지 않은 문제였다.

정규 표현식도 아직 더 공부를 많이 해야할 것 같다.

앞으로 이렇게 문제를 계속 풀다 보면 실력이 많이 늘지 않을까 하는 생각이 든다!