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

바탕화면 정리

문제 링크

바탕화면 정리

분석

가장 적은 이동의 드래그는 가장 작은 X에서 가장 큰 X로, 가작 작은 Y에서 가장 큰 Y로 할 수 있습니다.
즉, ‘#’ 글자가 등장하는 가장 작은 행과 열, 가장 큰 행과 열의 인덱스를 찾아야합니다.
이 값은 4개의 변수로 각각 관리해야합니다.

풀이

#include <string>
#include <vector>

using namespace std;

vector<int> solution(vector<string> wallpaper) {
    vector<int> answer;
    
    // 드래그 시작 위치와 끝 위치를 저장할 변수
    int startX = 50, startY = 50;
    int endX = 0, endY = 0;
    
    // wallpaper 순회
    for (int i = 0; i < wallpaper.size(); ++i)
    {
        // wallpaper[i]순회
        for (int j = 0; j < wallpaper[i].length(); ++j)
        {
            // 현재 글자가 '#'인 경우
            if (wallpaper[i][j] == '#')
            {
                // 현재 파일이 드래그를 어디서 어디까지 해야할지 변수 수정
                startY = (startY > i) ? i : startY;
                startX = (startX > j) ? j : startX;
                endY = (endY < i + 1) ? i + 1 : endY;
                endX = (endX < j + 1) ? j + 1 : endX;
            }
        }
    }
    
    answer = {startY, startX, endY, endX};
    
    return answer;
}

startX와 startY는 드래그가 시작될 위치로, 파일 위치 중 최대한 작은 값이 들어와야 합니다.
endX와 endY는 드래그가 끝날 위치로, 파일 위치 중 최대한 큰 값이 들어와야 합니다.

성능 요약

시간 복잡도는 $O(nm)$입니다.

• wallpaper를 순회하는 반복문 $O(n)$
• wallpaper[i]를 순회하는 반복문 $O(m)$
• $O(n) \times O(m)$

공간 복잡도는 $O(1)$입니다.

• X축과 Y축의 최대값, 최소값을 저장하는 변수 4개 $O(4) \approx O(1)$
• 결과를 저장하는 answer $O(4) \approx O(1)$

테스트 1 〉 통과 (0.01ms, 4.21MB)
테스트 2 〉 통과 (0.01ms, 4.14MB)
테스트 3 〉 통과 (0.01ms, 4.02MB)
테스트 4 〉 통과 (0.01ms, 4.21MB)
테스트 5 〉 통과 (0.01ms, 4.15MB)
테스트 6 〉 통과 (0.01ms, 4.21MB)
테스트 7 〉 통과 (0.01ms, 4.04MB)
테스트 8 〉 통과 (0.01ms, 3.67MB)
테스트 9 〉 통과 (0.02ms, 3.58MB)
테스트 10 〉 통과 (0.02ms, 4.13MB)
테스트 11 〉 통과 (0.01ms, 4.17MB)
테스트 12 〉 통과 (0.01ms, 4.21MB)
테스트 13 〉 통과 (0.01ms, 4.2MB)
테스트 14 〉 통과 (0.01ms, 4.27MB)
테스트 15 〉 통과 (0.02ms, 4.2MB)
테스트 16 〉 통과 (0.02ms, 4.13MB)
테스트 17 〉 통과 (0.01ms, 4.2MB)
테스트 18 〉 통과 (0.02ms, 4.45MB)
테스트 19 〉 통과 (0.01ms, 4.24MB)
테스트 20 〉 통과 (0.02ms, 3.67MB)
테스트 21 〉 통과 (0.01ms, 4.13MB)
테스트 22 〉 통과 (0.01ms, 4.14MB)
테스트 23 〉 통과 (0.01ms, 4.21MB)
테스트 24 〉 통과 (0.01ms, 4.15MB)
테스트 25 〉 통과 (0.01ms, 4.21MB)
테스트 26 〉 통과 (0.01ms, 4.14MB)
테스트 27 〉 통과 (0.01ms, 4.2MB)
테스트 28 〉 통과 (0.01ms, 3.58MB)
테스트 29 〉 통과 (0.01ms, 4.2MB)
테스트 30 〉 통과 (0.01ms, 4.15MB)
테스트 31 〉 통과 (0.02ms, 4.14MB)