프로그래머스. 불량 사용자

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

코딩테스트 연습 - 불량 사용자

 

재귀형식의 DFS 방식으로 풀었다.

순열을 만들듯이 각 불량이용자 아이디와 이용자 아이디를 대조해봐서 제외되어야 할 아이디가 될 수 있다면 벡터에 넣는 방식이다.

 

제외되어야 할 아이디인지 판단은 

1. 길이가 같지 않다면 아니다

2. 길이가 같다면, 유저 아이디에 *을 같은 위치에 넣었을때 같은 문자열이 아니라면 아니다.

 

이렇게 하면 다음과 같이 될 수 있는 모든 경우를 구할수 있다.

input:

vector<string> user_id =
        {
                "frodo", "fradi", "crodo", "abc123", "frodoc"
        };
vector<string> banned_id =
        {
                "fr*d*", "*rodo", "******", "******"
        };

경우의수:

 

그런데 나열된 순서와 관계없이 아이디 목록의 내용이 동일하다면 같은 것으로 처리

위 조건 때문에, 

frodo crodo abc123 frodoc
frodo crodo frodoc abc123

이런 경우 하나로 처리해야한다.

 

따라서 모든 경우를 저장해 놓고, 정렬 한후 erase, unique 함수를 이용해 중복을 제거해서 남은 경우의수의 갯수가 답이다.

user_id 벡터의 최대크기가 8이기 때문에, 시간초과 걱정은 없다. 

 

 

---

다른 분들 코드를 참조해 set 컨테이너를 이용해봤다.

sort,unique, erase 함수로 중복 제거 과정이 필요없어진다.