Portfolio

문제

풀이

은찬


const solution = (user_id, banned_id) => {
    let answer = 0;
    const list = [];
    const strings = new Map();
    
    const dfs = (index, map) => {
        if(index === list.length){
            if(map.size === list.length){
                const string = [];
                
                for(const [k, _] of map){
                    string.push(k);
                }
                
                string.sort();
                
                const word = string.join("");
                
                if(!strings.get(word)){
                    strings.set(word, true);
                    answer++;
                }
            }
            return;
        }
        
        for(let i = 0; i < list[index].length; i++){
            if(!map.get(list[index][i])){
                map.set(list[index][i], true);
                dfs(index + 1, map);
                map.delete(list[index][i]);
            }
        }
        
    }
    
    user_id.sort();
    banned_id.sort();
    
    for(let i = 0; i < banned_id.length; i++){
        const bannedId = banned_id[i];
        const candidates = [];
        
        for(let j = 0; j < user_id.length; j++){
            const userId = user_id[j];
            const length = userId.length;
            let keep = true;
            
            if(bannedId.length !== userId.length){
                continue;
            }
            
            for(let k = 0; k < length; k++){
                if(bannedId[k] === "*"){
                    continue;
                }
                
                if(bannedId[k] !== userId[k]){
                    keep = false;
                    break;
                }
            }
            
            if(keep){
                candidates.push(userId);
            }
        }
        
        candidates.sort();
        list.push(candidates);
    }
    
    for(let i = 0; i < list[0].length; i++){
        const map = new Map();
        
        map.set(list[0][i], true);
        dfs(1, map);
    }
    
    return answer;
}

재영

set 대신 object로 푸는 게 더 깔끔한 거 같네용!


function solution(user_id, banned_id) {
    const q = [[[], [...user_id], [...banned_id]]]; // [현재 조건에 맞는 애들], [지금 남은 유저 애들], [지금 남은 밴 조건들]
    const obj = {};
    const resLength = banned_id.length;
    while (q.length) {
        const [cases, users, banUsers] = q.shift();
        if (!banUsers.length) { // [밴 조건이 없는 경우]
            const nowResult = cases.sort().join(''); // set을 위한 것
            obj[nowResult] = true;
            continue;
        }
        const banId = banUsers.pop();
        const nowUsers = [...users];
        nowUsers.forEach(userId => {
            let flag = true;
            if (userId.length !== banId.length) return;
            for (let i = 0; i < banId.length; i += 1) {
                if (flag && banId[i] !== '*' && banId[i] !== userId[i]) {
                    
                    flag = false;
                }
            }
            if (flag) {
                q.push([[...cases, userId], nowUsers.filter(id => userId !== id), [...banUsers]])
            }
        })
    }

    return Object.keys(obj).length
}

효성

첫 번째 풀이 - `실패`

재귀함수가 필요하다는 걸 인지하지 못했음.

그저 banned_id에 해당하는 id만 구하면 될 줄 알고 풀이를 시작한 게 미스.

로직이 복잡해질 땐 과감히 풀이를 버리고 새로 생각하는 방식도 써보기! 기존 코드는 주석처리!


function solution(user_id, banned_id) {
    const same = [], cnt = [];
    let sameCnt;
    for(let i=0; i<banned_id.length; i++) {
        const splitBanned = banned_id[i].split('');
        sameCnt = 0;
        for(let j=0; j<user_id.length; j++) {
            const splitUser = user_id[j].split('');               
            if(banned_id[i].length === user_id[j].length) {
            	if(isSame(splitBanned, splitUser)) {
                    sameCnt++;
                	same.push(user_id[j]);
            	}
            }
        }
        cnt.push(sameCnt);
    }
    console.log(same)
    console.log(cnt)
}

function isSame(banned, user) {
    for(let k=0; k<banned.length; k++) {
        if(banned[k] === '*') {
            continue;
        }
        if(banned[k] !== user[k]) {
            return false;
        }
    }      
    return true;
}

참고한 풀이


function solution(user_id, banned_id) {
	let visit = [], set = new Set();
    
    const isSame = (ban, user) => {
        for(let i=0; i<ban.length; i++) {
            if(ban[i] !== '*' && ban[i] !== user[i]) return false;
        }
        return true;
    }
    
    const bfs = (idx, count, str) => {
        if(banned_id.length === count) {
            let arr = str.split(" ");
            arr.shift();
            arr.sort();
            let newStr = arr.join("");
            set.add(newStr);
        }
        if(idx >= user_id.length) return;
        
        for(let i=idx; i<banned_id.length; i++) {
            for(let j=0; j<user_id.length; j++) {
                if(visit[j]) continue;
                if(banned_id[i].length !== user_id[j].length) continue;
                if(!isSame(banned_id[i], user_id[j])) continue;
                visit[j] = true;
                bfs(i+1, count+1, str+" "+user_id[j]);
                visit[j] = false;
            }
        }
    }
    bfs(0,0,"");
    return set.size;
}

불량 사용자

문제

풀이

첫 번째 풀이 - 실패

참고한 풀이

첫 번째 풀이 - `실패`