[프로그래머스(Programmers)][자바(java)] (Lv3) 불량 사용자

 

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

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

 

문제 풀이

 

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

public class Solution {
	
	public void perm( int k, int n, int m, int a[], boolean v[], Set<Set<String>> r, String uid[], String bid[] ) {
		int i;
		if( k == m ) {
			for( i = 0; i < m; i++ )
				if( !isBannedId( uid[a[i]], bid[i] ) )
					return;
			Set<String> s = new HashSet<>();
			for( i = 0; i < m; i++ )
				s.add( uid[a[i]] );
			r.add( s );
			return;
		}
		for( i = 0; i < n; i++ ) {	
			if( !v[i] ) {
				v[i] = true;
				a[k] = i;
				perm( k + 1, n, m, a, v, r, uid, bid );
				v[i] = false;
			}
		}
	}
	
	public boolean isBannedId( String uid, String bid ) {
		int lu = uid.length(), lb = bid.length();  char cu, cb;
		if( lu != lb )
			return false;
		for( int i = 0; i < lb; i++ ) {
			cb = bid.charAt(i);
			if( cb == '*' )  continue;
			cu = uid.charAt(i);
			if( cb != cu )  return false;
		}
		return true;
	}
	
	public int solution(String[] user_id, String[] banned_id) {
		int nu = user_id.length, nb = banned_id.length;
		int a[] = new int[nu];
		boolean v[] = new boolean[nu];
		Set<Set<String>> r = new HashSet<>();
		perm( 0, nu, nb, a, v, r, user_id, banned_id );
		return r.size();
	}

}

 

*  완전 탐색, 해시

-  조건에서 'user_id 배열의 크기는 1 이상 8 이하입니다.',
   'user_id 배열 각 원소들의 값은 길이가 1 이상 8 이하인 문자열입니다' 를 보아 완전 탐색을 해도 괜찮음
-  user_id[]의 개수를 nu, banned_id[]의 개수 nb라고 할 때,
   nu개 중 nb개를 중복 없이 뽑는 순열 중 banned_id[]와 일치하는 경우의 수를 구해야 함
   --> perm() 함수와 isBannedId() 함수 작성
-  조건에서 '제재 아이디 목록들을 구했을 때 아이디들이 나열된 순서와 관계없이 아이디 목록의 내용이 동일하다면
   같은 것으로 처리하여 하나로 세면 됩니다.' 로 보아 중복이 있으면 안되므로 
   Set<Set<String>> 안에 넣음  ( HashSet, TreeSet 둘 다 키 값이 오름차순으로 자동 정렬됨 )
-  Set의 크기( size() )가 정답이 됨