[프로그래머스] 바탕화면 정리

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

프로그래머스

---

접근방법

그림을 그려가며 생각했을때, 최소한의 이동거리로 드레그를 한다면

[왼쪽 위의 x, 왼쪽위의 y, 오른쪽 아래의 x + 1, 오른쪽 아래의 y + 1] 로 접근해야겠다고 판단했다.

1차 제출

function solution(wallpaper) {
    let lux = 0;
    let luy = 0;
    let rdx = 0;
    let rdy = 0;
    
    let temp = wallpaper.map(item => item.split("").findIndex(item2 => item2 == "#")).sort((a, b) =>  a - b);
    let temp2 = wallpaper.map(item => item.split("").findLastIndex(item2 => item2 == "#")).sort((a, b) =>  a - b);
    
    lux = temp.findIndex(value => value >= 0);
    luy = temp[lux];
    rdx = temp2.findLastIndex(value => value >= 0);
    rdy = temp2[rdx] + 1;
    
    return [lux,luy,rdx+1,rdy];
}

- wallpaper를 배열화 시킨 뒤, "#"값을 앞에서 / 뒤에서 부터 검색하여 정렬한다. 그 뒤 각 배열의 최소값, 최대값의 index와 값을 담은 배열은 return 한다.

- 이 방법은 4건의 입출력예로 테스트했을때는 정상 동작하였으나 프로그래머스의 node.js 버전과 호환되지 않아 제출이 불가능했다.

 

2차 제출

function solution(wallpaper) {
    let lux,luy,rdx,rdy = 0;
    
    let temp = wallpaper.map(item => item.split("").indexOf("#")).sort((a, b) =>  a - b);
    let temp2 = wallpaper.map(item => item.split("").lastIndexOf("#")).sort((a, b) => a - b);
    
    lux = temp.findIndex(value => value >= 0);
    luy = temp[lux];
    rdx = temp2.length;
    rdy = temp2.slice(-1)[0];
    
    return [lux,luy,rdx,rdy + 1];
}

- 결과 : 67.7점

- 분석 : 위의 코드로는, 제공된 입출력예 4건에 대해서는 정상동작하였으나 아래와 같은 경우에는 잘못된 값이 나온다는 것을 확인했다.

1. 중간에 '#'가 없는 행이 포함된 경우
	const wallpaper = ["...", ".#.", "...", "###"];

    잘못된 결과 : [2, 0, 4, 3]
	올바른 결과 : [1, 1, 4, 3]

2. 모든 '#'이 한 행에 몰려있는 경우
	const wallpaper = ["...", "###", "..."];

	잘못된 결과 : [2, 0, 3, 3]
	올바른 결과 : [1, 0, 2, 3]
    
3. 비연속적인 '#'의 분포
    const wallpaper = ["#..", "...", "..#"];
    
    잘못된 결과 : [1, 0, 3, 3]
	올바른 결과 : [0, 0, 3, 3]

 

3차 제출

이와같은 반례를 방지하기위해 #의 위치를 정확히 추적하면서 최소/최대 값을 계산하는 방식으로 로직을 변경해야 했다.

function solution(wallpaper) {

	# 최소값과 최대값을 비교할 때 초기값으로 설정하기 위해 Infinity 사용
    let lux = Infinity, luy = Infinity; let rdx = -Infinity, rdy = -Infinity;

    for (let i = 0; i < wallpaper.length; i++) {
        for (let j = 0; j < wallpaper[i].length; j++) {
            if (wallpaper[i][j] === '#') {
                lux = Math.min(lux, i);
                luy = Math.min(luy, j);
                rdx = Math.max(rdx, i);
                rdy = Math.max(rdy, j);
            }
        }
    }
    
    return [lux, luy, rdx + 1, rdy + 1];
}

- 결과 : 100점

- 분석 : 2중 루프를 사용하여 최소 및 최대 좌표를 업데이트 하는 방법으로 수정하였으며, rdx와 rdy값은 반환값 + 1을 적용해주었다.

 

 

---

* Infinity 추가 공부

* Infinity는 최소값과 최대값을 비교할 때 초기값으로 설정하기 위해 사용됩니다.

이는 일반적으로 배열을 순회하면서 최소값 또는 최대값을 계산할 때 매우 유용합니다.

 

* 왜 Infinity를 쓰는가?

 1. 초기값으로 적합

   최소값을 찾으려면 초기값이 충분히 큰 값이어야 합니다.

   이 값이 모든 가능한 값보다 크면 배열의 첫 번째 값과 비교했을 때 바로 업데이트됩니다.

   최대값을 찾으려면 초기값이 충분히 작은 값이어야 하고, -Infinity를 사용하면 동일한 이유로 작동합니다.

 2. 모든 값과 비교 가능

   JavaScript에서 Infinity는 어떤 숫자와 비교해도 항상 크기 관계를 명확히 합니다.

   Math.min(Infinity, x) → x (x가 Infinity보다 작기 때문)

   Math.max(-Infinity, x) → x (x가 -Infinity보다 크기 때문)