<프로그래머스 C++> 바탕화면 정리 풀이

문제

바탕화면의 상태를 나타낸 문자열 배열 wallpaper가 주어진다. #은 파일이 있는것. '.'은 파일이 없는 빈칸이다.

 

모든 파일을 한 번의 드래그로 선택할 수 있는 최소 이동거리의 시작점과 끝점을 [lux, luy, rdx, rdy]로 return하는 문제이다.

---

문제 흐름 파악

모든 #을 포함하는 최소 직사각형을 구하면 된다.

직사각형의 꼭짓점은 다음과 같다.

 

- 왼쪽 위 : (#의 최소 행, #의 최소 열)

- 오른쪽 아래 : (#의 최대 행 +1, #의 최대열 +1)

 

따라서 wallpaper를 전체 순회하면서 #이 발견될 때마다 minRow, minCol, maxRow, maxCol을 갱신하면 된다.

---

문제 풀이

#include <string>
#include <vector>
using namespace std;

vector<int> solution(vector<string> wallpaper) {
    int maxRow = 0, maxCol = 0;
    int minRow = wallpaper.size();
    int minCol = wallpaper[0].size();

    for(int i = 0; i < wallpaper.size(); ++i)
        for(int j = 0; j < wallpaper[i].size(); ++j)
            if(wallpaper[i][j] == '#')
            {
                minRow = min(minRow, i);
                minCol = min(minCol, j);
                maxRow = max(maxRow, i);
                maxCol = max(maxCol, j);
            }

    return {minRow, minCol, maxRow+1, maxCol+1};
}

---

코드 흐름

1. 초기값 설정

int maxRow = 0, maxCol = 0;
int minRow = wallpaper.size();
int minCol = wallpaper[0].size();

- minRow, minCol -> 가능한 최댓값으로 초기화

- maxRow, maxCol -> 0으로 초기화

 

초기값을 최댓값으로 잡아야 하는 이유는 min() 함수의 사용법에 있다.

예를 들어 열이 50개라고 하고 minCol=3으로 초기화 했다고 할 때,

#이 (0, 10)에 있다고 하면 min()함수 안에서 min(3, 10)으로 들어가게 되기 때문에 실제 최솟값을 잡을 수 없게 된다.

 

반대로 max()함수를 사용하는 maxRow와 maxCol도 가능한 낮은 값을 넣는 이유도 다음과 같다.

 

2. wallpaper 순회

if(wallpaper[i][j] == '#')
{
    minRow = min(minRow, i);
    minCol = min(minCol, j);
    maxRow = max(maxRow, i);
    maxCol = max(maxCol, j);
}

#이 발견될 때마다 4개의 값을 갱신한다.

 

3. 결과 반환

return {minRow, minCol, maxRow+1, maxCol+1};

오른쪽 아래 끝점은 #의 최대 좌표에 +1을 해야 한다.

드래그는 격자점 기준이기 때문에 #이 있는 칸을 포함하려면 한 칸 더 드래그해야 하기 때문이다.

---

핵심 포인트

1. 모든 #을 포함하는 최소 직사각형의 꼭짓점을 구한다.

 

2. min 계산 시 초기값을 반드시 가능한 최댓값으로 설정해야 한다.

 

3. 끝점은 maxRow +1, maxCol +1로 반환해야 한다.