99클럽 코테 스터디 3일차 TIL - 바탕화면 정리

https://school.programmers.co.kr/learn/courses/30/lessons/161990#

접근 방식

문제 요약: 바탕화면에서 모든 파일('#')을 포함하는 최소한의 드래그 영역 [lux, luy, rdx, rdy]를 구하는 문제이다.

각 좌표의 의미를 아래와 같이 sudo 코드로 작성해 둔 후 문제 풀이를 시작했다.

• lux: wallpaper 배열에서 '#'을 가진 가장 첫 번째 행의 인덱스
• rdx: wallpaper 배열에서 '#'을 가진 가장 마지막 행의 인덱스 + 1
• luy: wallpaper의 각 행에서 발견된 '#'의 가장 왼쪽 위치 (최소 열 인덱스)
• rdy: wallpaper의 각 행에서 발견된 '#'의 가장 오른쪽 위치 (최대 열 인덱스) + 1

구현

우선 sudo 코드를 그대로 코드로 옮겼다.

function solution(wallpaper) {
    const hasFile = wallpaper.map(s => s.includes('#'));
    const lux = hasFile.indexOf(true);
    const rdx = hasFile.lastIndexOf(true) + 1;
    
    const luy = wallpaper.reduce((acc, cur) => {
        const idx = cur.indexOf('#')
        return idx >= 0 ? Math.min(acc, idx) : acc;
    }, wallpaper[0].length);
    const rdy = wallpaper.reduce((acc, cur) => Math.max(acc, cur.lastIndexOf('#')), 0) + 1;
      
    return [lux, luy, rdx, rdy];
}

최적화 시도

한 번 순환할 때 모든 좌표를 업데이트하면 좋을 것 같아서 아래와 같이 작성해 보았다.

function solution(wallpaper) {
    const result = [wallpaper.length, wallpaper[0].length, 0, 0];
    
    for (let i = 0; i < wallpaper.length; i++) {
        for (let j = 0; j < wallpaper[0].length; j++) {
            if (wallpaper[i][j] === '#') {
                result[0] = Math.min(i, result[0]);
                result[1] = Math.min(j, result[1]);
                result[2] = Math.max(i + 1, result[2]);
                result[3] = Math.max(j + 1, result[3]);
            }
        }
    }
      
    return result;
}

하지만 매번 m * n번의 반복문 순회가 필요해 첫 번째 코드보다 실행시간이 오래걸렸다.

최종 최적화

한 번 순회할 때 모든 좌표를 처리하지만, 파일('#')이 포함된 행만 처리해 불필요한 연산을 제거했다.
indexOf와 lastIndexOf를 사용해 첫 번째와 마지막 파일 위치를 효율적으로 찾을 수 있다.
위의 코드와 마찬가지로 시간복잡도는 O(n*m)이지만 특히 파일이 드물게 분포된 경우 실제 실행 시간은 훨씬 효율적이다.

결과적으로, 파일이 없는 행을 건너뛰고, 각 행에서 indexOf와 lastIndexOf로 파일 범위를 빠르게 찾는 방식이 가장 효율적이었다.

function solution(wallpaper) {
    let lux = wallpaper.length;
    let luy = wallpaper[0].length;
    let rdx = 0;
    let rdy = 0;
    
    for (let i = 0; i < wallpaper.length; i++) {
        if (!wallpaper[i].includes('#')) continue;
        
        lux = Math.min(lux, i);
        rdx = Math.max(rdx, i + 1);
        luy = Math.min(luy, wallpaper[i].indexOf('#'));
        rdy = Math.max(rdy, wallpaper[i].lastIndexOf('#') + 1);
    }
      
    return [lux, luy, rdx, rdy];
}

실행 속도 비교

구현 방식	실행 시간	메모리 사용량
첫 번째 코드	0.31ms	33.4MB
두 번째 코드	0.59ms	33.5MB
세 번째 코드	0.23ms	33.4MB