[Java] 프로그래머스 64064.불량사용자 (Lv.3)

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

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

 

Lv.3치고 간단한 조합 응용문제입니다.

전체 사용자 리스트 Y개에서 불량 사용자 리스트에 대하여 대입이 가능한 X개를 뽑아 만들면 됩니다. (yCx)

 

조합과 다른 점은 아이디를 넣을 수 있는 경우가 제한되어 있어 사용자 Y가 아닌 불량 사용자 X에 대해 찾는다는 점입니다. 

모든 경우(Y x X)에 대하여 가능 여부를 미리 계산한 뒤, 재귀를 통해 불량 사용자 리스트마다 사용자를 대입하고 X개를 뽑았을 때 저장했습니다.

 

입력 데이터의 최대 사이즈가 8개이기 때문에 중복체크는 bitmask를 이용해 간단히 구현했습니다. 

가능한 리스트 최대 길이가 64이기 때문에 HashMap을 이용해도 구현이 가능할 것 같습니다. 

package programmers;

public class q64064_Programmers_불량사용자 {

	public static void main(String[] args) {
		String[] user_id = { "frodo", "fradi", "crodo", "abc123", "frodoc" };
		String[] banned_id = { "fr*d*", "*rodo", "******", "******" };
		System.out.println(solution(user_id, banned_id));
	}

	private static int solution(String[] user_id, String[] banned_id) {
		int answer = 0;
		boolean[] bitmask = new boolean[1 << user_id.length];

		boolean[][] possible = new boolean[user_id.length][banned_id.length];

		for (int u = 0; u < user_id.length; u++) {
			for (int b = 0; b < banned_id.length; b++) {
				boolean flag = true;

				if (user_id[u].length() != banned_id[b].length()) {
					flag = false;
				} else {
					for (int i = 0; i < user_id[u].length(); i++) {
						if (banned_id[b].charAt(i) == '*')
							continue;
						else if (user_id[u].charAt(i) != banned_id[b].charAt(i)) {
							flag = false;
							break;
						}
					}
				}

				possible[u][b] = flag;
			}
		}

		recur(possible, bitmask, 0, 0);

		for (int i = 0; i < bitmask.length; i++) {
			if (bitmask[i])
				answer++;
		}
		return answer;
	}

	private static void recur(boolean[][] possible, boolean[] bitmask, int mask, int idx) {
		if (idx == possible[0].length) {
			bitmask[mask] = true;
			return;
		}

		for (int u = 0; u < possible.length; u++) {
			if (possible[u][idx] && (mask & (1 << u)) == 0) {
				recur(possible, bitmask, mask | (1 << u), idx + 1);
			}
		}
	}
}