99클럽 코테 스터디 3일차 TIL + 바탕화면 정리

✔️ 오늘의 키워드

• 바탕화면 정리 (프로그래머스)

 

✔️ 문제 개요

프로그래머스의 "바탕화면 정리" 문제는 컴퓨터 바탕화면에 있는 파일들을 한 번의 드래그로 모두 선택하는 방법을 찾는 문제이다. 바탕화면은 격자 형태로 표현되며, 파일이 있는 칸은 "#", 빈칸은 "."으로 표시됩니다. 이때 모든 파일을 선택할 수 있는 가장 작은 사각형의 시작점과 끝점 좌표를 찾아야 하는 것이 목적이다.

 

✔️ 문제 해결 과정

1. 어떤 문제가 있었고, 나는 어떤 시도를 했는지

• 처음에 이 문제를 접했을 때, 바탕화면 전체를 탐색하면서 파일("#")의 위치를 모두 찾아야 한다는 것을 파악했다. 하지만 두 가지 고민이 있었다:

1. 어떻게 시작점과 끝점을 효율적으로 결정할 수 있을까?
   • 모든 파일 위치를 배열에 저장한 후 계산할지
   • 탐색하면서 바로 계산할지
2. 초기값을 어떻게 설정해야 할까?
   • 최소값과 최댓값을 찾기 위한 적절한 초기값 설정이 필요했다.

처음에는 모든 파일 위치를 저장한 후 계산하는 방식을 생각했지만, 바로 최소/최대 좌표를 업데이트하는 방식이 더 메모리 효율적일 것이라고 판단했다.

 

2. 어떻게 해결했는지

문제 해결을 위해 다음과 같은 접근법을 사용했다:

1. 최소 행(lux), 최소 열(luy), 최대 행(rdx), 최대 열(rdy)을 저장할 변수 초기화
   • 최솟값은 가능한 큰 값(50)으로 초기화 -> 아니면 INT_MAX로 해도 될 듯. 하지만 제한 사항에 wallpaper의 길이가 ≤ 50 되어있으니 50으로 함
   • 최댓값은 가능한 작은 값(-1)으로 초기화
2. 바탕화면의 모든 칸을 순회하면서:
   • 파일("#")을 발견하면 해당 위치의 행과 열을 사용하여 최소/최대 좌표 업데이트
   • 최대 행과 열은 드래그 끝점이 포함되지 않기 때문에 +1을 해준다.
3. 최종적으로 [minRow, minCol, maxRow, maxCol] 형태로 결과 반환해 준다.

#include <string>
#include <vector>

using namespace std;

vector<int> solution(vector<string> wallpaper) {

    // 최소값과 최대값을 저장할 변수 초기화
    int minRow = 50;    // lux 가장 위쪽 행
    int minCol = 50;    // luy 가장 왼쪽 열
    int maxRow = -1;    // rdx 가장 아래쪽 행
    int maxCol = -1;    // rdy 가장 오른쪽 열

    // 바탕화면의 모든 위치를 확인  
    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+1); // +1 하는 이유는 드래그 영역은 끝점을 포함하지 않음
                maxCol = max(maxCol, j+1);
            }
        }
    }

    return {minRow, minCol, maxRow, maxCol};

}

 

3. 무엇을 새롭게 알았는지

이 문제를 통해 다음과 같은 내용을 새롭게 알게 되었다:

1. 최소/최댓값 찾기 패턴
   • 최솟값을 찾을 때는 가능한 큰 값으로 초기화(INT_MAX) or 제한 사항에 맞게 초기화
   • 최댓값을 찾을 때는 가능한 작은 값으로 초기화(-1)
2. 인덱스와 경계 처리
   • 끝점이 포함되지 않는 경우(exclusive) +1을 해주는 것의 중요성
   • 문제의 조건을 정확히 이해하고 구현하는 것의 중요성

 

✔️ 결론

이 문제는 복잡한 알고리즘을 요구하지 않지만, 기본적인 개념(최소/최댓값 찾기, 2차원 배열 탐색)을 정확히 이해하고 구현하는 능력을 원한 것 같다. 경곗값 처리와 초기값 설정의 중요성을 배울 수 있었다.

코딩테스트에서는 이렇게 기본적인 알고리즘과 데이터 구조를 정확하게 이해하고 활용하는 능력이 중요하다는 것을 다시 한번 알게 되었다.