문제 161990. 바탕화면 정리

문제 링크

https://school.programmers.co.kr/learn/courses/30/lessons/161990

프로그래머스

 

 

난이도 : Lv.1 

 

문제 요약 설명

바탕화면에 있는 파일들을 한 번의 드래그로 전부 지울려고 합니다. 각 파일들이 (x, y)위치에 존재할 때, 멘헤튼 거리를 기준으로 최소 거리를 이동하여 모든 파일들을 지울 수 있는 드래그의 시작점과 끝점을 담은 정수 배열을 return하는 solution 함수를 작성해 주세요. 

입력

• 컴퓨터 바탕화면의 상태를 나타내는 문자열 배열 wallpaper

입력 제한

• 1 ≤ wallpaper의 길이 ≤ 50
• 1 ≤ wallpaper[i]의 길이 ≤ 50
• wallpaper의 모든 원소의 길이는 동일합니다.
• wallpaper[i][j]는 바탕화면에서 i + 1행 j + 1열에 해당하는 칸의 상태를 나타냅니다.
• wallpaper[i][j]는 "#" 또는 "."의 값만 가집니다.
• 바탕화면에는 적어도 하나의 파일이 있습니다.
• 드래그 시작점 (lux, luy)와 끝점 (rdx, rdy)는 lux < rdx, luy < rdy를 만족해야 합니다.

입력 예제

// input
[".#...", "..#..", "...#."]
// ans
[0, 1, 3, 4]

 

풀이 방식

드래그 시작 점은 (모든 파일들의 좌표 중 가장 왼쪽인 x 좌표, 모든 파일들의 좌표 중 가장 위인 y 좌표),

드래그 끝 점은 (모든 파일들의 좌표 중 가장 오른쪽인 x 좌표, 모든 파일들의 좌표 중 가장 아래인 y 좌표)가 되면 된다. 

2차원 배열을 좌측 상단을 시작으로 아래 또는 오른쪽으로 이동할수록 x, y좌표의 값이 증가함으로, 드래그 시작 점과 드래그 끝 점의 좌표은 다음과 같이 표현된다.

드래그 시작 점: ( min(x1, x2, ... xn), min(y1, y2, ... yn) )

드래그 끝 점: ( max (x1, x2, ... xn), max(y1, y2, ... yn) )

 

따라서, 모든 x, y좌표를 각 리스트에 추가하고, 리스트를 통해 드래그 시작 점과 끝점을 찾아 저장한 후 반환하면 된다.

 

정답 코드 

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

vector<int> solution(vector<string> wallpaper) {
    vector<int> answer;
    
    vector<int> pos_x_list;
    vector<int> pos_y_list;
    
    for(int i = 0; i < wallpaper.size(); i++){
        for(int j = 0; j < wallpaper[0].size(); j++){
            if(wallpaper[i][j] == '#'){
                pos_x_list.push_back(i);
                pos_x_list.push_back(i+1);
                pos_y_list.push_back(j);
                pos_y_list.push_back(j+1);
            }
        }
    }
    int min_x = *min_element(pos_x_list.begin(), pos_x_list.end());
    int max_x = *max_element(pos_x_list.begin(), pos_x_list.end());
    int min_y = *min_element(pos_y_list.begin(), pos_y_list.end());
    int max_y = *max_element(pos_y_list.begin(), pos_y_list.end());
    
    answer = {min_x, min_y, max_x, max_y};
    return answer;
}