[Java] 프로그래머스 - 불량 사용자

박철현·2024년 8월 9일

목록 보기

79/80

문제

코드

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;

class Solution {
	HashSet<HashSet<String>> resultSet = new HashSet<>();

	public int solution(String[] user_id, String[] banned_id) {
		List<List<String>> list = new ArrayList<>();
		// 1. 각 banned 패턴에 맞아 떨어지는 user list 구하기
		for (String bannedPattern : banned_id) {
			List<String> patternMatchedList = new ArrayList<>();

			// 사용자 id가 해당 패턴과 맞는지 전수조사
			for (String user : user_id) {
				// 패턴 길이랑 사용자 id 다르면 해당 id는 패턴에 부합하지 않음
				if (user.length() != bannedPattern.length()) {
					continue;
				}
				boolean isMatched = true;
				for (int j = 0; j < user.length(); j++) {
					// 해당 자리수의 문자가 *이 아닌 문자로 다르면 패턴 불일치
					if (bannedPattern.charAt(j) != user.charAt(j)) {
						if (bannedPattern.charAt(j) != '*') {
							isMatched = false;
							break;
						}
					}
				}
				if (isMatched) {
					patternMatchedList.add(user);
				}
			}
			// 조건 만족하는 사람 있는 패턴 부합하는 사람들 목록에 넣기
			if (!patternMatchedList.isEmpty()) {
				list.add(patternMatchedList);
			}
		}

		// 2. 가능한 조합 찾기
		findCombinations(list, new HashSet<String>(), 0);
		return resultSet.size();
	}

	private void findCombinations(List<List<String>> list, HashSet<String> currentSet, int index) {
		// 종료 조건 : 현재 인덱스가 리스트 size와 같다면 끝에있는 인덱스까지 도달 => 조건 만족
		if (index == list.size()) {
			resultSet.add(new HashSet<>(currentSet));
			return;
		}

		// 반복
		for (String user : list.get(index)) {
			// 중복이 안되는 경우만 넣기 : 안되는 경우의 수 사전 차단
			if (!currentSet.contains(user)) {
				currentSet.add(user);
				findCombinations(list, currentSet, index + 1);
				currentSet.remove(user);
			}
		}
	}
}

로직

패턴별 일치하는 userId 구하기

예제3번을 위 코드에 맞게 list를 그림으로 표현하면 위와 같습니다.
각 패턴별 조건을 만족하는 userId 경우를 모두 구한다.
- 불량 사용자 아이디 하나는 응모자 아이디 중 하나에 해당하고 같은 응모자 아이디가 중복해서 제재 아이디 목록에 들어가는 경우는 없습니다.
  - 위 조건에 의해 frodo 예를 들면 fr*d*, *rodo 두 곳에 모두 포함되는 경우는 안된다.
패턴에 맞는지를 검사하기 위해 패턴을 하나씩 보며 모든 userId가 만족하는지 파악한다.
- 길이가 안맞으면 될 수 없으니 넘어가기
- 패턴의 문자와 실제 userId의 문자가 다를 때 * 문자면 가능하지만 아닐 경우 패턴이 다르니 반복문 종료

가능한 조합을 만들어보고 문제의 조건을 만족하는지 확인한다.

불량 사용자 아이디 하나는 응모자 아이디 중 하나에 해당하고 같은 응모자 아이디가 중복해서 제재 아이디 목록에 들어가는 경우는 없습니다.
- 위 조건에 의해 각 패턴 하나당 Id 1개씩 가집니다.
- 즉 위 그림에서 4가지 패턴 -> 총 4명의 Id가 나와야 합니다.
제재 아이디 목록들을 구했을 때 아이디들이 나열된 순서와 관계없이 아이디 목록의 내용이 동일하다면 같은 것으로 처리하여 하나로 세면 됩니다.
- 이는 동일한 case를 1가지 경우로 보는 것, 아래 예시에서 총 2가지 경우를 1개로 쳐야함
  - ex) frodo-crodo-abc123-frodoc
  - ex) frodo-crodo-frodoc-abc123
- 위 예시처럼 가능한 경우를 만들고 이를 Set으로 담아서 중복을 제거하면 됩니다!

어떻게 조합을 생각할까?

위처럼 패턴별 가능한 Id를 모두 구하고 각 리스트를 순회하면서 하나씩 조합을 만들어보고 결과에 추가하면 된다고 생각했습니다.
근데 List안에 포함된 List가 몇개인 지도 모르고 어떻게 순회를 해야하나 고민했는데 뤼튼에게 물어본 결과 바로 답을 알려줬습니다.
list는 변하지 않는데 계속 함수 호출마다 넘겨주므로, list는 전역변수로 빼두는게 좋을 것 같습니다~!~!

재귀 함수를 통해 list 크기까지 depth를 반복합니다.

private void findCombinations(List<List<String>> list, HashSet<String> currentSet, int index) {
		// 종료 조건 : 현재 인덱스가 리스트 size와 같다면 끝에있는 인덱스까지 도달 => 조건 만족
		if (index == list.size()) {
			resultSet.add(new HashSet<>(currentSet));
			return;
		}

		// 반복
		for (String user : list.get(index)) {
			// 중복이 안되는 경우만 넣기 : 안되는 경우의 수 사전 차단
			if (!currentSet.contains(user)) {
				currentSet.add(user);
				findCombinations(list, currentSet, index + 1);
				currentSet.remove(user);
			}
		}
	}

현재 list에서 하나 꺼내고, 다음 list에서 요소 꺼내고, .. 쭉쭉 들어갑니다.
가지 치기로 중간에 조건에 맞지 않다면(중복 이름 있을 시) 해당 depth 끝까지 탐색하지 않습니다.
- ~~boolean 배열로 true/false 조작은 해봤지만 list의 index를 넘기면서는 처음 보는 형태라 다양한 방법으로 응용이 가능하다는 점을 알았네요 신기~~
fradi 시작 부분 생략

HashSet 주의 사항

HashSet에 요소를 넣고 depth 끝까지 방문하고 난 뒤 user를 빼주고 다음 반복에서 다시 넣어주는 등 Set을 계속 조작하고 있습니다.
이는 종료 조건에서 resultSet.add(currentSet);을 해줄 시 넣고자 하는 Set을 넣었지만 얕은 복사로 인해 원본 객체가 변경되면 계속 Set의 구성이 바뀝니다.
따라서 의도한 목적과 다른값이 들어가 테스트 케이스 3번이 실패합니다.
new HashSet<>(currentSet) 을 통해 깊은 복사를 통해 의도한 Set이 변경되지 않도록 수정하였습니다.