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

문제 설명

컴퓨터 바탕화면이 격자 형태로 주어집니다.

• 격자에는 파일이 있는 칸과 빈 칸이 존재합니다.
• 모든 파일을 최소한의 이동 거리로 선택하려고 합니다.
• 드래그는 바탕화면의 왼쪽 위 시작점과 오른쪽 아래 끝점을 선택해 직사각형으로 파일을 포함하는 방식입니다.

제약 조건

1. 바탕화면 크기
   • 세로 크기는 1 이상 50 이하입니다.
   • 가로 크기는 1 이상 50 이하입니다.
   • 모든 행의 길이는 동일합니다.
2. 격자 내용
   • 파일이 최소 1개 이상 포함됩니다.
   • 드래그 범위는 시작점이 끝점보다 왼쪽 위에 있어야 합니다.

해결 방법

알고리즘: 시뮬레이션

1. 최소와 최대 좌표 계산
   • 격자를 탐색하며 파일이 위치한 가장 위, 왼쪽, 아래, 오른쪽 좌표를 찾습니다.
   • 시작점은 가장 위와 가장 왼쪽의 좌표입니다.
   • 끝점은 가장 아래와 가장 오른쪽의 좌표입니다.
2. 격자 탐색
   • 이중 반복문을 사용해 모든 칸을 순회하며 파일이 있는지 확인합니다.
   • 파일을 찾을 때마다 최소 좌표와 최대 좌표를 갱신합니다.
3. 결과 반환
   • 계산된 시작점과 끝점을 반환합니다.

시간 복잡도

1. 격자 탐색은 행과 열의 곱에 비례합니다.
2. 따라서 시간 복잡도는 O(n × m)입니다.

구현 코드

function solution(wallpaper) {
  let minX = Infinity;
  let minY = Infinity;
  let maxX = -Infinity;
  let maxY = -Infinity;

  const rows = wallpaper.length;
  const cols = wallpaper[0].length;

  for (let i = 0; i < rows; ++i) {
    for (let j = 0; j < cols; ++j) {
      if (wallpaper[i][j] === "#") {
        minX = Math.min(minX, i);
        minY = Math.min(minY, j);
        maxX = Math.max(maxX, i + 1);
        maxY = Math.max(maxY, j + 1);
      }
    }
  }

  return [minX, minY, maxX, maxY];
}