안녕하세요. 오늘은 프로그래머스의 불량 사용자 문제를 풀어보겠습니다. 이 문제는 2019년 카카오 인턴십에서 출제되었습니다.
1) 문제 링크
https://programmers.co.kr/learn/courses/30/lessons/64064
2) 문제 풀이
✔ user_id 배열을 dfs 돌기: 불량사용자로 가능한 모든 경우의 수 세팅하기
문제에서 주어진 user_id와 banned_id는 배열 원소들의 갯수가 모두 8이하로 적습니다. 따라서 모든 경우를 돌면서 탐색합니다.
user_id에 저장된 사용자의 수가 8이고, banned_id에 저장된 불량 사용자 아이디 수가 4이면, user_id에서 4개를 뽑으면 됩니다.
이 때 user_id에서 a, a, a, a나 a, b, c, c처럼 같은 사용자의 아이디를 중복해서 뽑지 않도록 주의합니다.
✔ 경우의 수 세팅 완료 후: 해당 경우의 수가 "불량 사용자들 모임"인지 확인하기
경우의 수가 세팅되면, 해당 경우의 수가 "불량 사용자들 모임"인지 확인합니다. 불량 사용자들 모임이라면, 해당 Set을 새로운 Set에 저장합니다.
3) 전체 코드
import java.util.*;
class Solution {
private Set<Set<String>> result; //불량 사용자들의 모임(Set<String>)을 저장
public int solution(String[] user_id, String[] banned_id) {
result = new HashSet<>();
dfs(user_id, banned_id, new LinkedHashSet<>());
return result.size();
}
//dfs 돌면서 불량사용자로 가능한 모든 경우의 수 세팅
private void dfs(String[] user, String[] banned, Set<String> set) {
if (set.size() == banned.length) {
if (isBannedUsers(set, banned)) {
result.add(new HashSet<>(set));
}
return;
}
for (String userId : user) {
if (!set.contains(userId)) {
set.add(userId);
dfs(user, banned, set);
set.remove(userId);
}
}
}
//불량 사용자들 모임인지 확인하는 함수
private boolean isBannedUsers(Set<String> set, String[] banned) {
int i = 0;
for (String user : set) {
if (!isSameString(user, banned[i++])) {
return false;
}
}
return true;
}
private boolean isSameString(String a, String b) {
if (a.length() != b.length()) {
return false;
}
char[] aArr = a.toCharArray();
char[] bArr = b.toCharArray();
for (int i = 0; i < a.length(); i++) {
if(aArr[i] != bArr[i] && bArr[i] != '*') {
return false;
}
}
return true;
}
}4) 틀린 이유
✔ 풀이 순서의 문제
몇 시간에 걸쳐 문제를 풀었지만, 결국 틀렸습니다. 해답을 보니 문제를 푸는 방식은 같았지만(비슷한 역할의 함수를 설정한 점, dfs를 이용한 점) 풀이 순서에 문제가 있었습니다.
문제를 풀기 위해 선언한 함수를 역할을 기준으로 축약시켜보면 다음과 같이 두 가지로 나뉩니다.
- 불량 사용자를 찾기
- 전체 사용자 셋 만들기(dfs 돌기)
저는 불량 사용자를 먼저 찾은 후 HashMap에 저장하고, 이 결과를 가지고 dfs를 돌아야겠다고 생각했습니다. 이 방법이 뭔가 더 효율이 좋을 것이라고 생각했습니다.
그렇지만, 답을 본 후 다시 생각해보니 효율에 눈이 멀어 자료구조는 생각하지 않은 방식이었습니다.
불량 사용자를 먼저 찾고, Key가 String이고 Value가 List인 HashMap에 저장하게 되면, HashMap에 저장된 List의 size가 다 달라서 dfs를 돌리기가 어려웠습니다.
결국 답을 보니, dfs로 모든 경우를 먼저 찾고 불량사용자 여부를 확인했습니다.
문제에서 주어진 banned_id와 user_id의 최대 크기는 모두 8로 크지 않습니다. 모든 경우의 수를 탐색해도 된다는 의미이며, 이를 먼저 생각하고 풀이 순서를 잡았어야 했는데 생각이 짧았습니다.
5) 느낀점
그렇게 어렵지는 않았는데 풀이 순서를 확실히 결정해야 했었던 문제였습니다. 그리고 세 가지를 생각해 볼 수 있었습니다.
✔ LinkedHashSet
답에서는 LinkedHashSet을 사용했는데, 제가 자주 사용하지 않았던 자료구조라 생소했습니다. HashSet과 동일한 구조를 가지지만, 순서를 관리하지 않는 HashSet과는 다르게 LinkedHashSet은 삽입된 순서를 기억하고 있습니다. HashSet과 마찬가지로 중복 값을 허용하지 않으므로, HashSet의 특징을 사용하고 싶지만 순서도 저장해야 할 때 유용하게 사용할 듯 합니다.
✔ dfs: 갯수가 정형화되어 있을 때 쓰기 더 편하다
이번에 문제를 풀 때 size가 각기 다른 List들에서 dfs를 사용해보았습니다. 제가 dfs를 잘 활용하지 못해서인지 정말 어려웠고, 헷갈렸습니다. 그리고 dfs는 배열처럼 갯수가 정확히 정해져있을 때 사용하기 편하다라는 생각이 들었습니다.
✔ 어떤 자료구조를 사용할 지 결정 == 풀이순서만큼 중요
무작정 문제를 풀기보다, 자료구조의 특징에 따라, 그리고 문제에서 요구하는 사항에 따라 어떤 자료구조가 가장 편리할지 생각해둬야함을 느꼈습니다. 문제를 풀 때 1) 함수 구조를 어떻게 짤지 2) 문제 풀이 순서 정하기 3) 적절한 자료구조 사용 이 세 가지를 고려하여 틀을 잡아야 쉽고 빠르게 풀 수 있다는 사실을 다시 느꼈습니다.
[참고한 곳]
https://bcp0109.tistory.com/186
https://crazykim2.tistory.com/582
오오오오~~