[Programmers] 2019 카카오 인턴십 3번 - 불량 사용자

[문제 설명]

유저 id / 악성 유저 id 가 주어진다.

단 악성 유저에는 * 문자가 섞여 있다. (* : 모든 숫자, 문자 대체 가능)

 

[조건]

1 <= len (user_id, banned_id) <= 8

1 <= len (id) <= 8

 

[풀이]

악성 유저 id에 속할 수 있는 유저 id를 미리 뽑아서 저장해둔다. (아래 코드 : isAbleId[ ])

그렇다면 악성 유저 id의 갯수만큼 String이 생성된다.

(ex. isAbleId[3] = "123" -> 3번 악성 유저 문자에는 1번 2번 3번 user가 해당될 수 있음)

 

악성 유저 id의 개수만큼 dfs 탐색을 진행한다.

단 이 문제에서 한 가지 추가로 해결해야 하는 점은 바로 순서가 중요하지 않다는 점이다.

이 문제를 해결하기 위해서 dfs 탐색이 끝나는 시점에 기존의 조합이 들어왔는지 아닌지를 체크하였다.

(HashMap과 Bit 연산 활용)

 

public class Programmers_kakao2019_intern_3 {
	static HashMap<Integer, Integer> visit;
	
	static void search(String[] isAbleId, String[] banned_id, int idx, int visitNumber) {
		if (idx == banned_id.length) {
			if(!visit.containsKey(visitNumber)) {
				visit.put(visitNumber, 1);
			}
			return;
		}
		for (int i = 0; i < isAbleId[idx].length(); ++i) { 
			int curIdx = isAbleId[idx].charAt(i) - '0';
			if ((visitNumber & (1 << curIdx)) == 0) {
				search(isAbleId, banned_id, idx + 1, visitNumber | (1 << curIdx));
			}
		}
	}
	
	static boolean isPossible (String banned, String id) {
		if (banned.length() != id.length()) {           // (1) 길이가 다른 경우 false
			return false;
		}
		for (int i = 0; i < banned.length(); ++i) {
			if (banned.charAt(i) == '*')
				continue;
			else if (banned.charAt(i) != id.charAt(i)){ // (2) 길이는 같지만 문자 구성이 다른 경우 false
				return false;
			}
		}
		return true;                                    // 그 외 true
	}
	
    public static int solution(String[] user_id, String[] banned_id) {
        visit = new HashMap<>();
        String[] isAbleId = new String[banned_id.length];
        Arrays.fill(isAbleId, "");
        
        for (int bi = 0; bi < banned_id.length; ++bi) {
        	for (int ui = 0; ui < user_id.length; ++ui) {
        		if (isPossible(banned_id[bi], user_id[ui])) {    // 가능한 구성인 경우
        			isAbleId[bi] = isAbleId[bi].concat("" + ui); // concat하고 다시 대입해주는 걸 빼먹음
        		}
        	}
        	System.out.println(isAbleId[bi]);
        }
        
        search(isAbleId, banned_id, 0, 0);
        return visit.size();
    }	 
   public static void main(String[] args) {
	   System.out.println(solution(new String[] {"aaaaaaaa", "bbbbbbbb", "cccccccc", "dddddddd", "eeeeeeee", "ffffffff", "gggggggg", "hhhhhhhh"}, new String[] {"********", "********", "********", "********", "********", "********", "********", "********"}));
   }
}

 

 

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

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