LEVEL 3 : 불량 사용자

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

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

 

• 문제

  • 

    문제 1

  • 

    문제 2

  • 

    제한 사항

 

---

풀이

• BackTracking을 활용하여 모든 경우의 수를 구하는 문제이다( 백트래킹이 바로 생각나지 않았다ㅠㅠ)
  
  • String의 Match함수를 통해 일치하는 문자열을 모든 경우의 수를 구한 뒤, 몇 개의 조합이 생기는지 계산해주면 해결된다.
• 방문 여부를 저장할 visit 배열과, 중복이 되지 않도록 저장하는 Set을 생성한다.
• 정규식을 사용해야 하므로 * -> .으로 변경하여, 해당 자리를 제외한 모든 문자가 같음을 비교해주는 정규식을 만든다.(replace 함수)
• Backtracking 메서드
  • 종료 조건 : idx(뽑은 갯수) 가 선택될 수 있는 총개수랑 같을 때(banned_id.length)
    • 종료 조건을 만났을 때, 해당 조합이 List에 담은 뒤, 중복 여부를 파악한다.
  • 반복문 : 방문하지 않았으며, 정규식에 포함되는 문자일 경우
    • 방문 표시를 한다( visit[i] = true)
    • 선택한다(answer[idx] = user_id[i])
    • 재귀 함수를 호출한다(선택된 상태에서 같은 함수를 재귀적으로 호출, 종료 조건을 만날 때까지)
    • 방문 표시를 제거한다(visit[i] = false)

• public static boolean[] visit; //방문 여부
  public static Set<List<String>> set; // 조합, 중복이 되지 않도록
  public static int solution(String[] user_id, String[] banned_id) {
  	visit = new boolean[user_id.length];	
      set = new HashSet<>();
      String[] regex = new String[banned_id.length];//
      for(int i = 0; i < banned_id.length; i++) {
      	regex[i] = banned_id[i].replace("*", "."); // * -> . 으로 바꿔 정규식을 만든다.
          //fr*do -> fr.do (. 자리에 어떤 문자도 허용)
      }
      String[] answer = new String[banned_id.length];//선택된 애들이 들어갈 배열
      Backtracking(regex,user_id,0,answer);
      return set.size();
  }
  private static void Backtracking(String[] regex, String[] user_id, int idx, String[] answer) {
  	if(regex.length == idx) {
      	List<String> tmpList = new ArrayList<>();
          for(String str : answer) {
          	tmpList.add(str); //선택된 애들을 리스트에 담는다.
  		}
  		Collections.sort(tmpList); //정렬을 해준다
          if(set.contains(tmpList)) { //이미 포함시킨적이 있다면
          	return; //return
          }
          set.add(tmpList);//포함된 적이 없으므로 set에 추가
          return;
  	}
      for(int i=0;i<user_id.length;++i) {
  		if(!visit[i] && user_id[i].matches(regex[idx])) {  //방문하지 않았으며, 정규식과 matching된다면
  			visit[i] = true; //방문 표기
  			answer[idx] = user_id[i]; //현재 선택된 애를 넣어준다
  			Backtracking(regex,user_id, idx+1, answer); // 재귀호출
  			visit[i] = false;//방문 해제
  		}
      }
  }