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

bepyan·2021년 6월 24일
0

알고리즘

목록 보기
16/16

문제 링크

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

1차 해결 코드

  1. banned_id의 유저 후보를 구한다.
  2. DFS를 활용하여 한 배열에 중복없이 정답 후보를 탐색한다.
  3. 정답 후보가 중복되지 않게 처리한다 (순서가 상관 없다)
function solution(user_id, banned_id) {
    // 1
    const candi = banned_id.map(banned => user_id.filter(id => {
        if (banned.length !== id.length) return false;
        for (var i = 0; i < banned_id.length; i++)
            if (banned[i] !== '*' && banned[i] !== id[i])
                return false;
        return true
    }))

    let ans = 0;
    const ansList = [];
    const choose = (idx, choosed) => {
        // 3
        if (idx === candi.length) {
            choosed.sort();
            if (!ansList.some(v => JSON.stringify(v) === JSON.stringify(choosed))) {
                ansList.push(choosed)
                ans++;
            }
            return
        }
        // 2
        candi[idx].forEach(s => {
            if (!choosed.includes(s))
                choose(idx + 1, [...choosed, s])
        })
    }
    choose(0, [])

    // 결과
    return ans;
}

같은 요소의 배열을 비교하는 법 ->> 클릭

개선한 코드

  • ansList를 Array 대신에 Object를 활용한다.
    string으로 전환하여 Set 처럼 사용 (string이 엄청 길어지면 이게 괜찮을까...)
  • JSON.stringify() 대신 join('') 사용 (배열의 특권 ㅎㅎ)
  • choose 시작 값을 인수에서 바로 지정.
function solution(user_id, banned_id) {
    // 후보지 리스트
    const candi = banned_id.map(banned => user_id.filter(id => {
        if (banned.length !== id.length) return false;

        for (var i = 0; i < banned_id.length; i++)
            if (banned[i] !== '*' && banned[i] !== id[i])
                return false;

        return true
    }))

    const ansList = {};
    const choose = (idx = 0, choosed = []) => {
        if (idx === candi.length) {
            choosed.sort();
            ansList[choosed.join('')] = true;
            return
        }

        candi[idx].forEach(s => {
            if (!choosed.includes(s))
                choose(idx + 1, [...choosed, s])
        })
    }
    choose()
    return Object.keys(ansList).length;
}
profile
쿠키 공장 이전 중 🚛 쿠키 나누는 것을 좋아해요.

0개의 댓글