프로그래머스 - 불량 사용자(Level 3)

방법

1.  정규식을 사용하기 위해 불량 id에서 '*'제외한 나머지 문자가 일치하는지 보기 위해서 불량 id의 '*'를 '.'으로 바꿔준다.
2.  불량 id의 정규식과 일치하는 사용자 id들을 각각 배열 bans에 담는다
3. dfs를 사용하여 bans에서 하나씩 뽑아 set에 넣으며 조합을 만들어낸다
   각 불량아이디마다 중복될 수 있으므로 set에 넣고, 
   최종조합들도 중복될 수 있으므로 또 그걸 set에 담는다

import java.util.*;

public class Solution {
    private void count(int index, Set<String> banned,
                       String[][] bans, Set<Set<String>> banSet) { 
        if (index == bans.length) {
            banSet.add(new HashSet<>(banned)); //불량 아이디 개수만큼 담겼다면 최종 banSet 생성 후 반환
            return;
        }

        for (String id : bans[index]) { //banned_id 하나씩 끄집어내기
            if (banned.contains(id)) continue; //만약 set banned에 이미 있다면 건너뛰기
            //아래 remove 과정이 있기 때문에 건너 뛰는 것
            banned.add(id);
            count(index + 1, banned, bans, banSet); //아이디 조합을 위해 dfs 방법 사용
            banned.remove(id); 
        }
    }

    public int solution(String[] user_id, String[] banned_id) {
        String[][] bans = new String[banned_id.length][];
        //2차원 배열 만드는 이유: 불량 아이디별로 일치하는 아이디들을 각각 보관하기 위함

        for (int i = 0; i < banned_id.length; i++) {
            String banned = banned_id[i].replace('*', '.');
            //matches 메소드를 이용하기 위함
            // .은 개행문자를 제외한 모든 문자를 뜻하는 정규식임.
            List<String> matchedUsers = new ArrayList<>();
            for (String user : user_id) {
                if (user.matches(banned)) {
                    // boolean matches(String regex) : 문자열이 전달받은 정규표현식에 매칭되는지 여부를 반환
                    matchedUsers.add(user); //유저 아이디 중 전달받은 정규표현식에 매칭되는 아이디들 담기
                }
            }
            bans[i] = matchedUsers.toArray(new String[0]);
            //List<String>을 String[]으로 변환해서 담기
        }

        Set<Set<String>> banSet = new HashSet<>(); //중복방지를 위한 set 생성
        count(0, new HashSet<>(), bans, banSet);
        return banSet.size();
    }
}

 

 

1.  리스트를 배열로 만드는 방법

bans[i] = matchedUsers.toArray(new String[0]);

 

인자로 배열을 전달해야 함.

 

toArray 메서드에 파라미터로 넘기는 배열의 크기가 리스트의 크기보다 작거나 같으면, 

Java는 새로운 배열을 생성해서 반환한다.

따라서 new String [0]으로 생성하면 항상 리스트 크기의 배열이 생성되어 반환됩니다.

Java 8 이전에는 new String [list.size()]를 사용해 새 배열을 생성하는 것이 일반적이었지만, 

Java 8 이후에는 new String [0]이 더 효율적이다.

이는 Java 8 이후에서 배열의 생성과 복사를 최적화하기 위한 변경 때문이다.

 

 

2. 컬렉션 안에 컬렉션 만드는 방법

: 안의 컬렉션에는 컬렉션 이름을 넣지 않는다. 헷갈릴 수 있음.

 

Set<Set<String>> banSet = new HashSet<>();

 

 

3. 왜 banSet.add(banned);로 담지 않을까?

: 이렇게 담으면 banned에서 원소를 추가하거나 삭제하면,

banSet에 추가된 banned도 동일하게 변경된다.

banned가 수정될 가능성이 있으므로 결과가 틀리는 테케가 발생하게 된다.

아래 코드처럼 복사본을 생성하여 추가해야 이런 문제를 해결할 수 있다.

banSet.add(new HashSet<>(banned));

 

 

4. HashSet은 중복된 원소를 저장할 수 없다.

따라서 중복된 원소로 인해 해당 원소가 저장되지 않았는데

remove로 원래 있던 원소가 삭제될 수 있는 상황이 발생한다.

banned.add(id);
count(index + 1, banned, bans, banSet); //아이디 조합을 위해 dfs 방법 사용
banned.remove(id);

 

그것을 해결하기 위해 아래 코드가 추가된다.

if (banned.contains(id)) continue; 

 

중복된 원소라면 HashSet에 추가할 일이 없어 삭제할 일도 없게 된다.

그리고 이 코드로 인해 방문한 적 있는지 확인하는 역할도 대신하고 있다.