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

문제 이름 : 바탕화면 정리

1. 문제 설명

2. 중간에 막혔던 부분

#include <string>
#include <vector>

using namespace std;

vector<int> solution(vector<string> wallpaper) {
    vector<int> answer;
    int maxX = 0, maxY = 0, minX = wallpaper[0].length(), minY = wallpaper.size();
    
    for(int i=0;i<wallpaper.size();i++){
        for(int j=0;j<wallpaper[i].length();j++){
            if(wallpaper[i][j] == '#'){
                if(j < minX) minX = j;
                else if(j > maxX) maxX = j;
                if(i < minY) minY = i;
                else if(i > maxY) maxY = i;
            }
        }
    }
    
    answer = {minY, minX, maxY, maxX};
    return answer;
}

이 문제를 풀때 제일 처음에 작성했던 코드이다. 이 문제의 결과와 기댓값을 비교해보면 min값은 다 맞는데 max값이 전부 틀린 것을 볼 수 있다. 이 문제를 푸는 것이 가장 어려웠는데 우선 두가지의 잘못이 있었다. 우선 파일이 있는 것은 Grid안에 들어있는 것이고 이는 행렬로 나타낼 수 있다 하지만 드래그하는 바탕화면의 좌표계와 같은 좌표가 아니라는 점이다. 파일은 Grid안에 들어있고 Grid의 좌표는 파일의 네 꼭짓점 좌표를 표시할 수 있는 것이지 파일자체의 위치와는 다른 좌표이다. 굳이 따지면 파일의 좌측 상단 좌표와 같은 값을 가지는 것이다. 그리고 두번째 잘못은 위의 코드에선 min과 max를 else로 분리해놨는데 이는 잘못 된 코드이다. 그 이유는 만약 파일이 전체에서 하나만 존재한다면 그 파일은 min임과 동시에 max이기 때문이다.

3. Solution

#include <string>
#include <vector>

using namespace std;

vector<int> solution(vector<string> wallpaper) {
    vector<int> answer;
    int maxX = 0, maxY = 0, minX = wallpaper[0].length(), minY = wallpaper.size();
    
    for(int i=0;i<wallpaper.size();i++){
        for(int j=0;j<wallpaper[i].length();j++){
            if(wallpaper[i][j] == '#'){
                if(j < minX) minX = j;
                if(j+1 > maxX) maxX = j+1;
                if(i < minY) minY = i;
                if(i+1 > maxY) maxY = i+1;
            }
        }
    }
    
    answer = {minY, minX, maxY, maxX};
    return answer;
}

우선 구현 방식부터 살펴보면 max와 min 초기값은 결과에서 나올 수 있는 가장 낮은 값과 높은 값으로 설정하였다. 그리고 wallpaper를 2차원 배열이므로 이중 for문을 순회하면서 #을 찾는다. 그리고 #의 위치를 기반으로 min, max를 검사하는데 여기서 앞서 잘못된 점들을 고쳤다. 우선 첫번째 문제였던 좌표계의 차이이다. Grid 좌표에서 파일의 좌측상단의 좌표가 파일의 위치와 동일하다는 말을 했는데 이 말은 파일의 우측하단 좌표가 파일의 max 좌표가 된다는 말이다. 따라서 max를 비교할 때는 i와 j에 1을 더해주었다. 그리고 두번째 문제였던 파일이 하나인 경우에 min임과 동시에 max가 되므로 else를 없애고 모든 것을 if문으로 해주었다.

4. Review

이 문제는 얼핏보면 굉장히 쉬워보이는 문제이다. 하지만 파일의 위치와 Grid의 좌표계가 다르다는 점때문에 틀리는 사람들이 많았을 것 같다. 이런 사소한 부분 하나가 쉬워보이는 문제도 어렵게 만들 수 있고 이런 점들을 놓치면 안될 것이다.

 

GitHub - leejy811/AlgorithmStudy: 코딩 테스트 스터디