프로그래머스

[프로그래머스/JAVA] 불량 사용자

찌끄랭이 2022. 11. 29. 16:20

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

 

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

문제 설명

개발팀 내에서 이벤트 개발을 담당하고 있는 "무지"는 최근 진행된 카카오이모티콘 이벤트에 비정상적인 방법으로 당첨을 시도한 응모자들을 발견하였습니다. 이런 응모자들을 따로 모아 불량 사용자라는 이름으로 목록을 만들어서 당첨 처리 시 제외하도록 이벤트 당첨자 담당자인 "프로도" 에게 전달하려고 합니다. 이 때 개인정보 보호을 위해 사용자 아이디 중 일부 문자를 '*' 문자로 가려서 전달했습니다. 가리고자 하는 문자 하나에 '*' 문자 하나를 사용하였고 아이디 당 최소 하나 이상의 '*' 문자를 사용하였습니다.
"무지"와 "프로도"는 불량 사용자 목록에 매핑된 응모자 아이디를 제재 아이디 라고 부르기로 하였습니다.

예를 들어, 이벤트에 응모한 전체 사용자 아이디 목록이 다음과 같다면

응모자 아이디
frodo
fradi
crodo
abc123
frodoc

다음과 같이 불량 사용자 아이디 목록이 전달된 경우,

불량 사용자
fr*d*
abc1**

불량 사용자에 매핑되어 당첨에서 제외되어야 야 할 제재 아이디 목록은 다음과 같이 두 가지 경우가 있을 수 있습니다.

제재 아이디
frodo
abc123
제재 아이디
fradi
abc123

이벤트 응모자 아이디 목록이 담긴 배열 user_id와 불량 사용자 아이디 목록이 담긴 배열 banned_id가 매개변수로 주어질 때, 당첨에서 제외되어야 할 제재 아이디 목록은 몇가지 경우의 수가 가능한 지 return 하도록 solution 함수를 완성해주세요.

[제한사항]

  • user_id 배열의 크기는 1 이상 8 이하입니다.
  • user_id 배열 각 원소들의 값은 길이가 1 이상 8 이하인 문자열입니다.
    • 응모한 사용자 아이디들은 서로 중복되지 않습니다.
    • 응모한 사용자 아이디는 알파벳 소문자와 숫자로만으로 구성되어 있습니다.
  • banned_id 배열의 크기는 1 이상 user_id 배열의 크기 이하입니다.
  • banned_id 배열 각 원소들의 값은 길이가 1 이상 8 이하인 문자열입니다.
    • 불량 사용자 아이디는 알파벳 소문자와 숫자, 가리기 위한 문자 '*' 로만 이루어져 있습니다.
    • 불량 사용자 아이디는 '*' 문자를 하나 이상 포함하고 있습니다.
    • 불량 사용자 아이디 하나는 응모자 아이디 중 하나에 해당하고 같은 응모자 아이디가 중복해서 제재 아이디 목록에 들어가는 경우는 없습니다.
  • 제재 아이디 목록들을 구했을 때 아이디들이 나열된 순서와 관계없이문아이디 목록의 내용이 동일하다면 같은 것으로 처리하여 하나로 세면 됩니다.

코드

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashSet;
import java.util.List;

class Solution {
    HashSet<String> set = new HashSet<>();  //  정답의 개수
    List<String> list = new ArrayList<>(); // user_id를 저장

    public int solution(String[] user_id, String[] banned_id) {
        DFS(user_id, banned_id, 0, 0);
        return set.size();
    }

    public void DFS(String[] user_id, String[] banned_id, int count, int index) {
        if (count == banned_id.length) { //banned_id에 대응하는 user_id를 모두 모은다면
            StringBuilder sb = new StringBuilder();
            Collections.sort(list); //순서 상관없이 정답을 1개로 만든다.
            for (String s : list) sb.append(s);
            set.add(sb.toString());
            return;
        }
        if (index >= banned_id.length) return;
        for (int i = 0; i < user_id.length; i++) {
            String ban = banned_id[index];
            String user = user_id[i];
            if (list.contains(user)) continue; //같은 user_id가 들어가지 않는다.
            if (check(ban, user)) {
                list.add(user);
                DFS(user_id, banned_id, count + 1, index + 1);
                list.remove(user);
            }
        }
    }

    public boolean check(String ban, String user) { //banned_id에 user_id가 들어갈 수 있는지 판별
        if (ban.length() != user.length()) return false;
        for (int i = 0; i < ban.length(); i++) {
            if (ban.charAt(i) == '*') continue;
            if (ban.charAt(i) != user.charAt(i)) return false;
        }
        return true;
    }
}

문제 풀이

첫번째 접근 방식은 banned_id의 요소 하나하나에 user_id가 몇 개 들어갈 수 있는지 계산하고 계산된 banned_id당 개수를 HashMap에 저장하였다. 이 후에 저장된 값을 모두 곱하여 답을 구했는데, 이렇게 계산한다면 같은 아이디가 중복되어 들어가는 경우와 순서가 다르고 내용은 똑같은데 따로 계산되서 정답으로 들어가게 되었다.

 

두번째 접근 방식은 백트래킹을 이용하였는데 banned_id에 들어갈 수 있는 user_id를 리스트에 넣으면서 같은 user_id를 넣지 못하게 막았다. 그 다음 리스트에 들어간 개수가 banned_id의 개수가 동일해진다면 정답으로서 하나씩 추가하는데, 이 때 순서가 달라도 내용이 같으면 1개로 하기 위해서 정렬을 하였다. 정렬을 한다면 내용물이 같으면 순서도 같게 된다.

그리고 중복을 막기 위해 HashSet에 List가 가지고있는 user_id를 넣었다. 그렇다면 HashSet에 있는 값은 순서가 달라도 한 개의 정답으로 만들면서 중복이 없는 값을 지니고 있기 때문에 HashSet의 사이즈를 반환한다면 정답이다.

 

1. banned_id에 들어 갈 수 있는 user_id를 리스트에 넣기, 이때 list.contains()의 역할은 같은 user_id 중복을 방지 

2. 리스트의 크기가 banned_id의 크기와 같다면 리스트를 정렬한 후에 HashSet(중복제거)으로 리스트가 가지고 있는

모든 문자열을 병합하여 넣기.

 

 

나름 풀이가 괜찮다고 생각했는데 다른 분의 코드를 보고 충격을 받았다.

/*
작성자 성함: 채윤병
*/

import java.util.HashSet;
import java.util.Set;

public class Solution {

    Set<Integer> set;

    public int solution(String[] user_id, String[] banned_id) {
        set = new HashSet<>();

        go(0, user_id, banned_id, 0);

        return set.size();
    }

    public void go(int index, String[] user_id, String[] banned_id, int bit) {

        if (index == banned_id.length) { //bit에 저장된 부분집합의 개수가 banned_id의 개수와 동일하다면 정답이다.
            set.add(bit);
            return;
        }

        String reg = banned_id[index].replace("*", "[\\w\\d]"); //[\w\d]는 문제에서 *가 가지고 있는 의미를 대신해주고 있다.
        for (int i = 0; i < user_id.length; ++i) {
            if ((((bit >> i) & 1) == 1) || !user_id[i].matches(reg)) continue; // 이미 bit가 가지고있는 값이거나 banned_id에 충족X
            go(index + 1, user_id, banned_id, (bit | 1 << i)); // bit | 1 << i 는 bit에 부분집합을 넣는 과정이다.
        }

    }

}

이 분의 코드를 처음보고 코드가 이렇게 짧을 수가 있는지 정말 감탄이 나왔다.

핵심은 bit와 if문이다. bit에 신기하게도 부분집합을 저장할 수 있다. 예를 들자면 user_id가 5개 [1,2,3,4,5]가 있다고 하자.

bit를 0이라고 한다면, 부분집합{}을 의미한다. 만약 10000이면 [5], 10100이면 [5, 3], 10111이면 [5, 3, 2, 1]를 저장한다.

 

여기서 우리는 어느 부분집합을 저장해야할까? banned_id에 해당하는 user_id를 중복없이 저장해야한다.

이를 위한 조건문  if((((bit>>i) & 1) == 1) || !user_id[i].matches(reg))을 살펴보면 (bit>>i & 1) == 1은 bit에 저장된 부분집합 중 중복이 있는지 확인하는 것이다. 만약 bit가 10100인데 i=2 이라면 bit >> 2 = 101 이고 (101 & 1 ) =1 이므로 true인데

이때가 true값이 중복을 의미한다. 왜냐하면 user_id[2] 는 00100 인데 bit는 10100으로 user_id[2]를 가지고 있다.

 

다음으로 user_id[i].matches(reg)를 살펴보자. 유저 아이디가 reg와 일치하는지 확인하는 코드인데,

그 전에 String reg = banned_id[index].replace("*", "[\\w\\d]") 이 코드를 예시로 들자면, "ab5c9"를 user_id라고 하고

"ab*c*"를 banned_id라고 하자. 그렇다면 replace를 한다면 "ab*c*"는 "ab[\w\d]c[\w\d]"로 치환된다. 그렇다면,

"ab5c9".matches("ab[\w\d]c[\w\d]") 가 되는데 이 값은 놀랍게도 true이다. 어떻게 가능하냐면 matches 안에 오는 값 중에서 정규 표현식이 있기때문에 가능했다. 문제의 제한 사항 중 아이디는 영어 소문자와 숫자만 온다고 했는데 \w는 알파벳이나 숫자, \d는 0~9사이의 숫자를 의미한다. 즉 [\w\d]의 순서에 a~z나 0~9가 온다면 matches는 비교할 때 같다고 처리한다.

다시 예로 든다면 ab5c9와 ab[\w\d]c[\w\d]가 동일하다고 할 수 있다. 참고로 [\\w]로 replace해도 값은 동일하게 나온다.

왜냐하면 \w는 숫자와 알파벳을 모두 포함한다.

 

이번 문제를 풀면서 제일 큰 수확은 문제를 푼 것이 아니다.

다른 분의 코드를 보고 하나 더 배웠다는 점이 제일 큰 수확이라고 생각한다.

저작자표시 (새창열림)