카카오 코딩테스트 풀어보기

2022년 카카오 코딩테스트 문제인 신고 결과 받기를 풀어 보겠다

언어는 자바스크립트를 사용했고, 소요 시간은 38분이었다 파이썬이었으면

https://programmers.co.kr/learn/courses/30/lessons/92334?language=javascript

function solution(id_list, report, k) {
    let answer = new Array(id_list.length).fill(0); // 메일 수 저장용
    const filterSet = new Set(report);
    let _report = [...filterSet]; // 중복 제거로 동일한 신고 없애기
    let reportCount = new Array(id_list.length).fill(0); // 신고 횟수 저장용
    
    let len = _report.length;
    for(let i = 0; i < len; i++) {
        reportCount[id_list.indexOf(_report[i].split(" ")[1])] += 1;
    }

    reportCount.forEach((item, idx) => {
        if(item >= k) { // 만약 메일을 보낼 만큼의 신고를 받았다면
            _report.forEach((rep) => {
                if(rep.split(" ")[1] === id_list[idx]) { // _report에서 신고자 찾기
                    answer[id_list.indexOf(rep.split(" ")[0])] += 1;
                }
            })
        }
    })
    return answer;
}

동일한 신고는 모두 1회로 처리해야 하니 필터링 함수를 만들어 놓으려다가 집합을 사용해서 중복을 없애 주었다. 이용자 수와 같은 길이의 배열 reportCount 에 신고당한 횟수를 저장하고, reportCount 를 돌면서 각 이용자의 신고 수가 지정된 한계 k 를 넘어가면, 신고 내역에서 그 이용자를 신고한 사람을 찾아 그 사람에게 보낼 메일을 1개 추가한다.

바로 짠 코드인데 너무 완벽한 것 같다. 돌려 보니 시간 초과가 발생했다

forEach 가 느려서 그런 것 같으니 reportCount.forEach( ... ) 를 바꿔 주도록 하겠다.

function solution(id_list, report, k) {
    let answer = new Array(id_list.length).fill(0); // 메일 수 저장용
    const filterSet = new Set(report);
    let _report = [...filterSet]; // 중복 제거로 동일한 신고 없애기
    let reportCount = new Array(id_list.length).fill(0); // 신고 횟수 저장용
    
    let len = _report.length;
    for(let i = 0; i < len; i++) {
        reportCount[id_list.indexOf(_report[i].split(" ")[1])] += 1;
    }
    
    let countLen = reportCount.length;
    for(let i = 0; i < countLen; i++) {
        if(reportCount[i] >= k) {
            for(let j = 0; j < len; j++) {
                data = _report[j].split(" ")
                if(data[1] === id_list[i]) {
                    answer[id_list.indexOf(data[0])] += 1;
                }
            }
        }
    }
    return answer;
}

또 시간 초과다 정신 나갈 것 같다

아예 로직을 바꿔 봤다. 신고 횟수를 따로 저장하지 않고 key 에 신고당한 사람, value 에 신고한 사람을 저장하는 객체를 만들었다.

function solution(id_list, report, k) {
    let answer = new Array(id_list.length).fill(0); // 메일 수 저장용
    const filterSet = new Set(report);
    let _report = [...filterSet]; // 중복 제거로 동일한 신고 없애기
    let reported = {};
    
    id_list.map(name => {
        reported[name] = [];
    });
    
    _report.map((item) => { // reported key: 신고당한 사람, value: 신고한 사람
        let [first, second] = item.split(" ");
        if(first in reported[second] === false) {
            reported[second].push(first)
    }})
    
    Object.keys(reported).map((name) => {
        if(reported[name].length >= k) {
            reported[name].map((user) => {
                answer[id_list.indexOf(user)] += 1;
            })
        }
    })
    
    return answer;
}

신고 내역을 돌면서 reported 에 신고당한 사람과 신고한 사람의 배열을 저장하고 다시 reported 를 돌면서 신고한 사람의 배열, 즉 value 의 길이가 k 보다 크면 value 에 있는 사람들의 메일 수를 올려 준다.

결과는 100점 !

한창 백준 풀 때도 시간 초과 때문에 트라우마 생길 것 같았는데 여기서도 어김없이 시간 초과로 발목을 잡혔다. 하지만 코드 뒤엎기는 넘 재밌어