[241017 TIL] 본캠프 12일차 ('영화 사이트 만들기' 프로젝트 3일차)

 알고리즘 문제 풀이 

프로그래머스

 

1차 시도

• 코드 흐름
  1. Set 객체를 이용해서 중복 데이터 제거
  2. 유저 목록을 순회하면서 i번째 유저가 신고한 내역 추출
  3. 2번에서 추출한 내역을 순회하면서 j번째 유저가 신고 당한 횟수 추출
  4. 3번에서 추출한 횟수가 k번 이상일 경우 i번째 유저에게 메일 발송
• 실행 결과
  • 일부 테스트 케이스에서 시간 초과 발생
• 예상 원인 
  • filter()의 경우, 배열 요소를 하나하나 순회하면서 조건에 맞는 요소를 추출하는 방식이기 때문에 최대 200,000의 길이를 가진 report 배열을 매번 순회하는 것은 바람직하지 않음

function solution(id_list, report, k) {
    // id_list와 동일한 길이의 배열 선언 및 모든 요소를 0으로 초기화
    let result = Array.from({ length: id_list.length }, () => 0);

    // 중복 신고 제거 (한 유저가 동일한 유저를 여러번 신고해도 1회로 처리)
    report = Array.from(new Set(report));

    for (let i = 0; i < id_list.length; i++) {
        // id_list[i] 유저가 신고한 내역
        const userReport = report.filter((item) => item.split(' ')[0] === id_list[i]);

        for (let j = 0; j < userReport.length; j++) {
            // id_list[i] 유저가 신고한 j번째 유저가 신고 당한 횟수
            const reportCount = report.filter((item) => {
                return item.split(' ')[1] === userReport[j].split(' ')[1];
            });

            // 신고 당한 횟수가 k번 이상일 경우
            if (reportCount.length >= k) {
                result[i]++;
            }
        }
    }

    return result;
}

 

 

2차 시도 (해결)

• 코드 흐름
  1. Set 객체를 이용해서 중복 데이터 제거
  2. 유저 목록을 순회하면서 사용자가 신고한 내역 추출
  3. 신고 목록을 순회하면서 사용자가 신고 당한 횟수 추출
  4. 유저 목록을 순회하면서 2번과 3번에서 추출한 데이터를 바탕으로 사용자에게 메일 발송
• 해결 방법 
  • filter()경우, 배열의 용량이 커질수록 시간 복잡도가 증가하여 overflow 발생
  • filter() 대신 forEach()를 사용함으로써 시간 복잡도를 낮춰줌

function solution(id_list, report, k) {
    // 중복 신고 제거 (한 유저가 동일한 유저를 여러번 신고해도 1회로 처리)
    report = Array.from(new Set(report));

    const send = {}; // 신고한 내역 { 신고한 user : [신고 당한 user1, 신고 당한 user2, ...] }
    const receive = {}; // 신고 당한 내역 { 신고 당한 user : 신고 당한 횟수 }
    const result = {}; // 결과 데이터 { user : 처리 결과 메일을 받은 횟수 }

    id_list.forEach((id) => {
        send[id] = [];
        receive[id] = 0;
        result[id] = 0;
    });

    report.forEach((repo) => {
        send[repo.split(' ')[0]].push(repo.split(' ')[1]);
        receive[repo.split(' ')[1]]++;
    });

    id_list.forEach((id) => {
        for (let i = 0; i < send[id].length; i++) {
            receive[send[id][i]] >= k && result[id]++;
        }
    });

    return Object.values(result);
}

 

---

 

 [영화 사이트 만들기] 프로젝트 

 

현재 구현된 기능

• 영화 목록
• 영화 상세 정보 modal 창
• 북마크

보완이 필요한 부분

• 영화 목록
  • 현재 → 최초 한 번 20개의 영화 데이터를 받아와서 화면에 보여줌
  • 보완 → 화면의 최하단으로 내려갈 때마다 20개의 영화 데이터를 추가로 받아와서 목록에 추가해줌