😊
불량 사용자 [Lv3]
March 07, 2023
1. 문제소개
2. 문제풀이
생각보다 까다로운 문제였으며 DFS로 문제를 해결하는 경우 ”****“이 존재할 때가 최대의 시간복잡도를 가지게 된다. 해당 경우에 대한 예외처리가 필요하다. 우선 문제에 대한 조각을 나눠야 한다.
- 두개의 문자열에 대한 banned 여부를 파악
- 파악된 결과를 바탕으로 possible_banned_list를 작성해야 한다.
- possible_banned_list를 이용하여 dfs를 통해 answer_array 를 생성한다.
- 3번의 경우 복잡도가 크게 증가 할 수 있으며, 중복을 제거하며 앞서서 언급된 string은 제거한다.
3. 코드
function solution(user_id, banned_id) {
var answer = [];
const possible_banned_list = [];
// [[ ... , ... , ] , [ .... , ... , ...] , [ .... , ...]]
for (let i = 0; i < banned_id.length; i++) {
possible_banned_list.push([]);
for (let j = 0; j < user_id.length; j++) {
if (isBannedId(user_id[j], banned_id[i])) {
possible_banned_list[i].push(user_id[j]);
}
}
}
// [ [ 'frodo', 'crodo' ], [ 'frodo', 'crodo' ], [ 'abc123', 'frodoc' ] ]
// 위와 같이 만들어진다.
const dfs = (curId, index, curArray) => {
// 종료 조건
if (index === banned_id.length - 1) {
answer.push(curArray.sort().join(","));
return;
}
// 다음 조건
// includes를 이용하면 배열내부의 요소를 손쉽게 찾을 수 있다.
// 같은 기능으로 indexOf를 통해 -1의 요소를 확인하는것 또한 방법이다.
for (let i = 0; i < possible_banned_list[index + 1].length; i++) {
if (!curArray.includes(possible_banned_list[index + 1][i])) {
// 포함하고 있지 않다면
dfs(possible_banned_list[index + 1][i], index + 1, [
...curArray,
possible_banned_list[index + 1][i],
]);
}
}
};
for (let i = 0; i < possible_banned_list[0].length; i++) {
dfs(possible_banned_list[0][i], 0, [possible_banned_list[0][i]]);
}
return [...new Set(answer)].length; // 여기서 중복을 제거하고 그 개수를 확인한다.
}
function isBannedId(userId, bannedId) {
// 두개의 문자열이 bannedId가 될수 있는지 확인한다.
if (userId.length !== bannedId.length) {
return false;
}
for (let i = 0; i < userId.length; i++) {
if (userId[i] !== bannedId[i] && bannedId[i] !== "*") {
return false;
}
}
return true;
}
Reference
아직 배움의 단계라 정확한 정보가 아닐 수 있습니다.😂
피드백은 seoungin1228@gmail.com 으로 부탁드리겠습니다☺️