카카오 2019 겨울 인턴십_불량사용자_Java 문제풀이

 

1. go 메소드 (문자 비교과정)

 

idx=0 즉, 단어 첫글자부터 서로 비교해갈 것이다.

여기서,

1. 제재ID가 "*"이 아님에도 유저ID와 글자가 다르면 즉시 비교과정을 중지한다.

2. 만약 "*"일 경우(비교하지않아도 되기에) 와 제재 ID와 유저ID 동일 위치의 글자가 같다면, idx를 하나 증가시키고 다음 위치의 글자를 비교하는 과정을 실행한다.

3. 만약 idx값이 글자 끝에 다다랐음에도 1번 조건문에 걸리지 않는다면, 제재대상인 ID이므로, flag변수를 false로 지정하고 비교과정을 끝낸다.

public static void go(String ban, String user) {
	if (idx == ban.length()) {
		flag = false;
		return;
	} else if (ban.charAt(idx) != user.charAt(idx) && ban.charAt(idx) != '*') {
		return;
	} else if (ban.charAt(idx) == '*') {
		idx++;
		go(ban, user);
	} else {
		idx++;
		go(ban, user);
	}
	return;
}

 

2. 메인 메소드

첫단계는 사용자ID와 어떤 제재ID를 선택할 것인가였다.

이 과정에서 시간을 줄일 수 있을 방법을 생각해보니,

제재ID와 사용자ID의 길이가 다르면 애초에 검증을 진행하지 않아도 되었기에 걸러주고

길이가 같은 것들을 대상으로 go메소드를 진행시켰다.

 

go메소드가 끝나는 이유는 위에 작성해놨듯이 2가지이다.

1. 제재ID와 유저ID 글자가 달라 비교 도중 중지

2. 제재ID와 유저ID를 끝까지 비교해, 유저ID가 제재 대상이라는 것을 확인 후에 중지

 

2번의 경우, 1번과 차이를 주기위해 flag변수를 false로 변경한채로 끝마쳤다.

만약, flag가 false일 경우, 해당 유저가 제재 대상이므로, 2차원 배열에 +1을 해준다. 

 

1번 예제

String[] user = { "frodo", "fradi", "crodo", "abc123", "frodoc" };
String[] banned = { "fr*d*", "abc1**" };

의 경우, 해당 배열으로 결과가 도출된다.

 

2차원 배열을 사용한 이유는, 처음에 누가 제재 대상인지 확인해보고 싶었고

해당 배열에서 1인 요소들 중 행에서 하나씩 뽑아 조합을 이루면 되지 않을까? 라는 생각에서였다.

따라서, 조합을 진행하기 위해 dfs 메소드를 진행했다.

public static int solution(String[] user_id, String[] banned_id) {
	int[][] result = new int[banned_id.length][user_id.length];
	for (int i = 0; i < banned_id.length; i++) {
		for (int j = 0; j < user_id.length; j++) {
			if (banned_id[i].length() != user_id[j].length()) {
				continue;
			} else {
				idx = 0;
				flag = true;
				go(banned_id[i], user_id[j]);
				if (!flag) {
					result[i][j]++;
				}
			}
		}
	}

	boolean[] real = new boolean[100001];
	int depth = 0;
	hs = new HashSet<>();
	dfs(result, real, depth);
	return answer;
}

 

3. dfs 메소드

 

흔히 볼 수 있는 조합을 구하는 과정이다. 다만 다른 점은 하나의 행에서 1인 것을 뽑으면 다음 행으로 넘어간다는 것...?

그리고,  이들을 String으로 변경하여, HashSet에 넣어주었다. 

이렇게 하면, 겹치는 조합없는 진짜 조합(?)이 나올 수 있어 경우의 수를 구할 수 있었다.  

public static void dfs(int[][] result, boolean[] real, int depth) {
	if (depth == result.length) {
		String t = "";
		for (int i = 0; i < real.length; i++) {
			if (real[i]) {
				t += i;
			}
		}
		hs.add(t);
		return;
	}
	for (int j = 0; j < result[depth].length; j++) {
		if (result[depth][j] == 1 && !real[j]) {
			real[j] = true;
			dfs(result, real, depth + 1);
			real[j] = false;
		}
	}
}

 

4. 전체 코드

import java.util.HashSet;

public class kakao_불량사용자 {
	static int answer;
	static int idx;
	static boolean flag;
	static ArrayList<Integer> al;
	static HashSet<String> hs;

	public static void main(String[] args) {

		String[] user = { "frodo", "fradi", "crodo", "abc123", "frodoc" };
//		String[] banned = { "fr*d*", "abc1**" };
//		String[] banned = { "*rodo", "*rodo", "******"};
		String[] banned = { "fr*d*", "*rodo", "******", "******" };
		solution(user, banned);
	}

	public static int solution(String[] user_id, String[] banned_id) {
		int[][] result = new int[banned_id.length][user_id.length];
		for (int i = 0; i < banned_id.length; i++) {
			for (int j = 0; j < user_id.length; j++) {
				if (banned_id[i].length() != user_id[j].length()) {
					continue;
				} else {
					idx = 0;
					flag = true;
					go(banned_id[i], user_id[j]);
					if (!flag) {
						result[i][j]++;
					}
				}
			}
		}

		boolean[] real = new boolean[100001];
		int depth = 0;
		hs = new HashSet<>();
		dfs(result, real, depth);
		return hs.size();
	}

	public static void dfs(int[][] result, boolean[] real, int depth) {
		if (depth == result.length) {
			String t = "";
			for (int i = 0; i < real.length; i++) {
				if (real[i]) {
					t += i;
				}
			}
			hs.add(t);
			return;
		}
		for (int j = 0; j < result[depth].length; j++) {
			if (result[depth][j] == 1 && !real[j]) {
				real[j] = true;
				dfs(result, real, depth + 1);
				real[j] = false;
			}
		}
	}

	public static void go(String ban, String user) {
		if (idx == ban.length()) {
			flag = false;
			return;
		} else if (ban.charAt(idx) != user.charAt(idx) && ban.charAt(idx) != '*') {
			return;
		} else if (ban.charAt(idx) == '*') {
			idx++;
			go(ban, user);
		} else {
			idx++;
			go(ban, user);
		}
		return;
	}
}