Problem statement #

1. 문제 개요
   머쓱이는 컴퓨터 바탕화면의 파일들을 한 번의 드래그로 모두 선택해 삭제하려고 합니다. 최소한의 이동거리로 드래그를 설정하는 방법을 구현합니다.¹

2. 바탕화면 설명

   • 컴퓨터 바탕화면은 격자판 형태로 구성됩니다.
   • 각 칸은 다음과 같은 값으로 표시됩니다:
     • 빈칸: "."
     • 파일이 있는 칸: "#"
   • 격자 좌표는 (세로, 가로) 형식으로 표현하며, (0, 0)이 바탕화면의 가장 왼쪽 위에 위치합니다.

3. 드래그 규칙

   • 드래그는 시작점 S(lux, luy)에서 끝점 E(rdx, rdy)까지 이동합니다.
   • 드래그 거리:
     [ |rdx - lux| + |rdy - luy| ]
   • 드래그 시, 시작점과 끝점이 각각 직사각형의 왼쪽 위와 오른쪽 아래를 형성하며, 이 내부의 모든 파일이 선택됩니다.

4. 입력

   • wallpaper: 문자열 배열로, 바탕화면 상태를 나타냅니다.

5. 출력

   • 최소 드래그로 모든 파일을 포함하는 직사각형의 시작점과 끝점을 정수 배열 [lux, luy, rdx, rdy]로 반환합니다.

6. 제약 사항

   • wallpaper는 최소 $1\times 1$에서 최대 $50\times 50$ 크기의 배열입니다.

Problem Dividing #

문제의 해결을 위해 4가지 단계를 생각했다.

1. std::vector<std::vector<int>> 타입으로 테이블 변경하기
2. 시작점(S) 구하기

• 최좌측 위치 구하기
• 최상단 위치 구하기

3. 종착점(E) 구하기

• 최우측 위치 구하기
• 최하단 위치 구하기

4. 시작점과 종착점을 answer에 넣기

Problem Solving #

최대한 문제를 잘게 나누고 가독성을 위해 함수를 작성하였다.

std::vector<std::vector<int>>  stringToIntWallpaper(std::vector<std::string> wallpaper);
std::pair<int, int> findStartPosition(std::vector<std::vector<int>> wallpaper);
std::pair<int, int> findLastPosition(std::vector<std::vector<int>> wallpaper);
void emplacePosition(std::vector<int>& answer, std::pair<int, int> position);

stringToIntWallpaper #

문제에서 제공되는 std::vector<std::string> wallpaper를 std::vector<std::vector<int>> wallpaper로 변경하기 위한 함수였다.

하지만 문제를 푸는데 있어서 위의 함수는 굳이 필요하지 않았다! 무의미한 함수였지만 일단은 기술하였고 마지막에 이 함수 없이 푸는 코드를 따로 올리겠다.

std::vector<std::vector<int>> stringToIntWallpaper(std::vector<std::string> wallpaper){
    std::vector<std::vector<int>> int_wallpaper;
    for(const auto line: wallpaper){
        std::vector<int> temp_vector;
        for(const auto sector: line){
            if(sector == '#'){
            	temp_vector.emplace_back(1);   
            }else{
                temp_vector.emplace_back(0);
            }
        }
       	int_wallpaper.emplace_back(temp_vector); 
    }
    return int_wallpaper;
}

string으로 이루어져 있는 .와 #의 집합을 0과 1로 이루어진 wallpaper로 변경하였다. 한 줄씩 반복하면서 #이 나오면 1을 .이 나오면 0을 입력하였다.

findStartPosition #

std::pair<int, int> findStartPosition(std::vector<std::vector<int>> wallpaper){
    bool left_flag = false;
    bool top_flag = false;
    int most_left = 0;
    int most_top = 0;
    for(int x = 0 ; x < wallpaper[0].size() ; x++){
        for(int y = 0 ; y < wallpaper.size() ; y++){
           if(wallpaper[y][x] == 1){
               most_left = x;
               left_flag = true;
               break;
           } 
        }
        if(left_flag) break;
    }
    for(int y = 0 ; y < wallpaper.size() ; y++){
        for(const auto item : wallpaper[y]){
            if(item == 1){
                most_top = y;
                top_flag = true;
                break;
            }
        }
        if(top_flag) break;
    }
    return {most_top, most_left};
} 

최좌상단의 값을 찾기 위해 (0,0)위치에서 반복문을 통해 우하단으로 내려가도록 하였다. 이 때 계속 값이 업데이트되지 않게 하기 위해서 break와 flag를 통해 값이 들어오면 바로 멈출 수 있도록 하였다.

findLastPosition #

std::pair<int, int> findLastPosition(std::vector<std::vector<int>> wallpaper){
    int most_right = 0;
    int most_bottom = 0;
    for(int x = 0 ; x < wallpaper[0].size() ; x++){
        for(int y = 0 ; y < wallpaper.size() ; y++){
           if(wallpaper[y][x] == 1){
               most_right = x;
           } 
        }
    }
    for(int y = 0 ; y < wallpaper.size() ; y++){
        for(const auto item : wallpaper[y]){
            if(item == 1){
                most_bottom = y;
            }
        }
    }
    return {most_bottom+1, most_right+1};
}

findStartPosition함수와 다르게 stop하지 않고 계속 순회하면서 모든 순회가 끝날 때 즉 가장 나중에 update된 최우하단의 값을 넣는다 또한 드래그는 각 섹션의 우측 하단의 값을 넣게 되므로 위치에 각각 1을 더해준다.

emplacePosition #

void emplacePosition(std::vector<int>& answer, std::pair<int, int> position){
	answer.emplace_back(position.first);
    answer.emplace_back(position.second);
}

vector를 reference로 전달하여 원본에 vector에 position들을 추가할 수 있도록 하였다.

Code Refactoring #

정답을 맞춘 뒤 프로그래머스에서 제공하는 다른 사람의 코드를 참고하여 리팩토링을 하여 코드의 완성도를 높인다.

개선점

1. 굳이 2중 int 벡터로 바꾸어야 했을까?
2. starting point와 end point를 굳이 따로 순회하면서 찾아야 했을까?

위의 개선점들을 생각해볼 수 있었다. 이를 개선하기 위해서 다른 사람들의 코드를 비교해보며 나의 코드의 문제점을 찾아나가보겠다.

wallpaper의 경우 std::vector<std::string>을 그대로 사용해도 무리가 없을것 같다. 그러므로 stringToIntWallpaper 함수는 제거한다.

Starting point와 End point를 구하는 경우 앞의 함수를 설명하면서 순회하며 업데이트한다. 즉 최좌측값은 x의 값이 가장 작으면서 #인 경우, 최상단의 값은 y값이 가장 작으면서 #인 경우가 된다. 이와 같이 End point의 경우 x값이 가장 크면서 #인 경우이며 최하단의 경우 y값이 가장 크면서 #인 경우에 각각 +1을 해주면 된다.

따라서 아래와 같이 코드를 다시 작성할 수 있었다.

#include <bits/stdc++.h>

std::vector<int> solution(std::vector<std::string> wallpaper) {
    // 상 좌 하 우
    std::vector<int> answer {100,100,-100,-100};
    for(auto i = 0 ; i < wallpaper.size() ; i++){
        for(auto j = 0 ; j < wallpaper[0].size() ; j++){
            if(wallpaper[i][j] == '#'){
                answer[0] = std::min(answer[0],i); // 최상점
                answer[1] = std::min(answer[1],j); // 최좌점
                answer[2] = std::max(answer[2],i); // 최하점
                answer[3] = std::max(answer[3],j); // 최우점
                
            }
        }
    }
    answer[2]++;
    answer[3]++;
    return answer;
}

결국 x축과 y축의 값을 계속 업데이트 하되 최저점과 최고점을 나누어 따로 업데이트를 시키면 되는 것이었다. 2중 for문 한번으로 상하좌우의 최소, 최댓값을 모두 찾아내고 이를 이용하여 드래그의 시작점과 드래그의 끝점을 구할 수 있었다.

Reference #