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

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

프로그래머스

 

목차

• 문제
• 풀이
• 코드

문제

입력

wallpaper (컴퓨터 바탕화면의 격자판. '#'는 파일 존재, '.'는 파일 없음을 나타낸다.)

 

출력

[행의 최솟값, 열의 최솟값, 행의 최댓값, 열의 최댓값]

 

제한사항

• 1 ≤ wallpaper의 길이 ≤ 50
• 1 ≤ wallpaper[i]의 길이 ≤ 50
  • wallpaper의 모든 원소의 길이는 동일합니다.
• wallpaper[i][j]는 바탕화면에서 i + 1행 j + 1열에 해당하는 칸의 상태를 나타냅니다.
• wallpaper[i][j]는 "#" 또는 "."의 값만 가집니다.
• 바탕화면에는 적어도 하나의 파일이 있습니다.
• 드래그 시작점 (lux, luy)와 끝점 (rdx, rdy)는 lux < rdx, luy < rdy를 만족해야 합니다.

 

풀이

드래그를 해서 구할 수 있는 최소 직사각형을 구하는 문제이다. 이차원 배열이 주어지고 왼쪽과 위쪽에서 '#'이 있는 최소 위치를 구하고 마찬가지로 오른쪽과 아래쪽에서 '#'이 있는 최대 위치를 배열에 저장하면 된다. (이 때, 최대 위치는 조심해서 구해야 한다.)

가령, 아래의 표처럼 3*3의 정사각형 타일에 '#'이 가장 처음에 있다고 가정해보자. 최소 위치는 '#'이 있는 시작점인 [0, 0]이지만 최대 위치는 [1, 1]이다.

최소 위치와 최대 위치

 

처음에는 어떻게 하면 시간 복잡도를 줄일까 고민했다. 이차원 배열이니 최소 행, 최소 열, 최대 행, 최대 열을 그냥 구하면 되지 않을까 고민했다. 그러나 최소와 최대 행을 구할 수 있었지만 결국 최소, 최대 열을 구하려면 모든 배열을 한 번 다 돌아야 하는 시간 복잡도 O(n*m)이 필요했다.

 

따라서 이중 for문을 사용하여 '#', 그러니까 파일이 있는 경우를 순회해야 했다. 정답을 쉽게 구하기 위해 미리 answer = [50, 50, 0, 0] 배열을 선언하였고 answer[0], answer[1]에는 최솟값이 들어가도록, 그리고 answer[2]와 answer[3]에는 최댓값이 들어가도록 하였다.

이때 Math 객체를 이용하여 최솟값, 최댓값으로 갱신해서 넣는다.

코드

명령형 프로그래밍으로 풀었다.

시간 복잡도는 이차원 배열를 모두다 순회하는 경우이므로 O(n*m)이다.

공간 복잡도는 정답을 저장하는 배열 하나이므로 O(1)이다.

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

 

선언형으로 풀기 위해서 알아보았으나 배열 두 개를 선언해야 하고 각각의 배열에 파일이 있는 모든 위치를 넣은 후에 최소와 최대를 구하는 구조였기에 시간 복잡도, 공간복잡도도 처음 풀이보다 컸기에 생략한다.