프로그래머스 | 선인장 숨기기

문제

지문

m개의 행과 n개의 열로 구성된 격자가 주어지며, 이는 사막 지도를 나타냅니다. 사막 지도의 가장 왼쪽 위칸 좌표는 (0, 0), 오른쪽 아래칸 좌표는 (m-1, n-1)입니다. 이 사막 어딘가에 가로 w, 세로 h 크기의 선인장 구역을 조성하려 합니다. 선인장 구역은 격자 축에 맞춘 연속된 w × h 크기의 부분 격자이며, 회전할 수 없습니다.
.
비구름은 미리 정해진 순서대로 격자의 여러 칸에 비를 뿌립니다. 이때 빗방울이 처음으로 선인장 구역에 포함된 칸에 떨어졌을 때, 그 시점을 선인장이 처음으로 비를 맞는 순간으로 기록합니다. 당신은 선인장이 가능한 한 늦게 비를 맞도록, 선인장 구역의 위치를 정하려고 합니다.
.

• 선인장이 비를 맞지 않도록 선인장 구역의 위치를 정할 수 있다면 해당 위치가 가장 우선됩니다.
• 가능한 늦게 비를 맞는 선인장 구역 후보가 여러 개라면 그중 가장 위쪽 행, 그래도 여러 개면 가장 왼쪽 열에 위치한 구역을 선택합니다.
  주어진 조건을 만족하는 선인장 구역에 포함된 가장 왼쪽 위칸의 좌표를 정수 배열로 return 하도록 solution 함수를 완성해 주세요.

입력

격자의 세로 길이와 가로 길이를 나타내는 정수 m, n
선인장 구역의 세로 길이와 가로 길이를 나타내는 정수 h, w
빗방울이 떨어지는 순서대로 칸의 좌표를 담은 2차원 정수 배열 drops

출력

조건을 만족하는 선인장 구역의 가장 왼쪽 위칸 좌표 [r,c]

입출력 예시

[예시1 설명]

노란색으로 표시된 구역을 선인장 구역으로 두면, 6번째로 비가 떨어질 때 선인장이 처음 비를 맞게 되며, 이보다 더 늦게 젖도록 하는 배치는 존재하지 않습니다. 따라서 노란색 구역의 가장 왼쪽 위 좌표인 [2, 2]를 return 해야 합니다.

문제 정리

h × w 크기의 선인장 구역을 어디에 놓아야,
구역 내에서 가장 먼저 비를 맞는 시점(= 구역 내 최솟값)이 가장 늦어지는 위치를 찾아라
[종료조건]

• 구역 내 아무 칸도 비를 맞지 않는다면 → 즉시 해당 위치 반환 (최우선)
• 그 외 → 모든 후보 중 구역 내 최솟값이 가장 큰 위치 반환
  (행 우선 탐색이므로 동점 시 위쪽·왼쪽 자동 선택)

아이디어

초기 접근

모든 선인장 구역 후보 (i, j)를 순회하며, drops 배열을 처음부터 탐색해
해당 구역 안에 처음 떨어지는 빗방울 시점을 직접 찾는 방식
: 최악 500,000 × 500,000 → 시간 초과

[초기 아이디어 코드]

/*
 * 사막지도 map = int[m][n]
 * 선인장 구역 cactus = w*h
 * 비구름 : 순서대로 비 뿌림
 * 		이 때, 처음으로 선인장 구역 포함 칸에 떨어졌을 때 = 처음 비 맞는 순간
 * 최대한 늦게 비를 맞도록 구역 위치 정함
 * 		비 맞지 않을 수 있다면 정답
 * 		n개라면 가장 위, 가장 왼 쪽 선택
 *
 * 출력 : 선인장 구역에 포함된 가장 왼쪽 위칸의 좌표
 */

/*
 * 맵에서 h*w를 정해두고, 해당 칸에서의 가장 빠른 빗방울 시간을 기록하고 비교
 */

class Solution {
    public int[] solution(int m, int n, int h, int w, int[][] drops) {
        int[] answer = {};

        int[][] map = new int[m][n]; //사막 지도

        int dropsLen = drops.length;
        int bestDropTime = Integer.MIN_VALUE; //현재 최선 답안에 대한 빗방울 떨어진 시간


        for(int i = 0;i<=m-h;i++) {
            for(int j = 0;j<=n-w;j++) {
                //선인장 시작 구역 세팅
                int firstDrop = Integer.MIN_VALUE; //이 위치에서 처음 비 맞는 시간
                for(int t = 0;t<dropsLen;t++) {

                    int r = drops[t][0];
                    int c = drops[t][1];
                    //빗방울 위치

                    if(r>=i && r<i+h && c>=j && c<j+w) { //빗방울이 범위 내에 존재한다면
                        firstDrop = t+1;
                        break; //가장 처음 맞는 순간 기록 후 빠져나옴
                    }
                }

                if(firstDrop==Integer.MIN_VALUE) { //비 안 맞는 위치라면
                    return new int[]{i,j}; //바로 출력
                }

                if(firstDrop>bestDropTime) {
                    bestDropTime = firstDrop;
                    answer = new int[]{i,j};
                }

            }
        }

        return answer;
    }
}

개선된 접근

내 접근이 틀렸구나! 그런데 어떻게 해야하지? -> 시간을 단축할 수 있는 방법은?
=> 슬라이딩 윈도우를 쓰자.

슬라이딩 윈도우

[아이디어]
각 칸에 빗방울이 몇 번째로 떨어지는지를 map[r][c] = i+1로 미리 저장해두고,
h × w 구역 내 최솟값을 빠르게 구하기 위해 슬라이딩 윈도우 + 덱 활용
[로직]

• 맵 세팅
  • drops[i] 순서대로 map[r][c] = i+1 저장 (비 안 맞는 칸은 0 유지)
• 가로 슬라이싱
  • 행 방향 크기 w 윈도우 최솟값 → rowSlicing[m][n-w+1]
  • 각 행에 대해 덱으로 크기 w 슬라이딩 윈도우의 최솟값 계산
    • map[i][j] == 0 (비 안 맞음) → INF로 처리 (순서 비교 시 최하위)
  • 덱에는 값이 아닌 인덱스 저장
    • 덱 앞쪽 = 현재 윈도우 최솟값 인덱스
• 세로 슬라이싱
  • 열 방향 크기 h 윈도우 최솟값 → colSlicing[m-h+1][n-w+1]
  • rowSlicing 결과를 입력으로, 동일한 덱 패턴을 열 방향으로 적용
  • colSlicing[i][j] = 좌상단 (i, j)인 h × w 구역 내 빗방울 최솟값
• 결과 탐색

코드

전체 코드

import java.util.ArrayDeque;
import java.util.Deque;

class Solution {
    public int[] solution(int m, int n, int h, int w, int[][] drops) {
        int[] answer = {};

        int[][] map = new int[m][n]; // 전체 맵 세팅
        for (int i = 0; i < drops.length; i++) {
            int r = drops[i][0];
            int c = drops[i][1];
            map[r][c] = i+1; //빗방울 순서 1부터 저장
        }

        int INF = Integer.MAX_VALUE;
        // 가로 슬라이싱. 구역 내 최솟값 저장
        int[][] rowSlicing = new int[m][n-w+1];

        for(int i=0;i<m;i++){
            Deque<Integer> deque = new ArrayDeque<>(); //앞쪽 값이 항상 최솟값
            //이 deque은 값이 아니라 인덱스가 저장됨

            for(int j=0;j<n;j++){
                int now = map[i][j]==0 ? INF : map[i][j]; //비 안 맞았다면 INF.(번째 순서 비교 위함)

                while(!deque.isEmpty()){
                    int last = deque.peekLast(); //덱의 맨 뒤 인덱스
                    int lastVal = map[i][last]==0 ? INF : map[i][last]; //해당 칸이 비 안 맞는다면 INF, 아니면 순서

                    if(lastVal>=now) deque.pollLast(); //현재값보다 크거나 같으면 제거
                    else break; //현재보다 작으면 중단

                }
                deque.offerLast(j); //현재 인덱스 덱 뒤에 추가
                if(deque.peekFirst()<=j-w) deque.pollFirst(); //윈도우 범위 벗어남 = 맨 왼쪽 인덱스보다 작다면 제거
                if(j>=w-1){ //윈도우가 w칸 채워진 경우에만 저장
                    rowSlicing[i][j-w+1]=map[i][deque.peekFirst()]; //해당 윈도우 내 최솟값
                }
            }
        }

        // 세로 슬라이싱
        int[][] colSlicing = new int[m - h+1][n - w+1];
        for (int j = 0; j < n-w+1; j++) {
            Deque<Integer> deque = new ArrayDeque<>();//앞쪽 값이 항상 최솟값
            //이 deque은 값이 아니라 인덱스가 저장됨
            for (int i = 0; i < m; i++) {
                int now = rowSlicing[i][j]==0 ? INF : rowSlicing[i][j];
                while(!deque.isEmpty()){
                    int last = deque.peekLast(); //덱 마지막 인덱스
                    int  lastVal = rowSlicing[last][j]==0 ? INF : rowSlicing[last][j]; //덱 마지막 인덱스가 0이면 값은 무한
                    if(lastVal>=now) deque.pollLast(); //현재 값보다 크거나 같으면 제거
                    else break; //덱 마지막 값이 현재보다 작으면 중단
                }
                deque.offerLast(i); //현재 인덱스 덱 뒤에 추가
                if(deque.peekFirst()<i-h+1)  deque.pollFirst(); //윈도우 범위 벗ㅇ어남 = 맨 왼쪽 인덱스보다 작다면 제거
                if(i>=h-1){
                    colSlicing[i-h+1][j]=rowSlicing[deque.peekFirst()][j]; //해당 윈도우 내 최솟값
                }
            }
        }

        //결과 계산
        int bestTiming = Integer.MIN_VALUE;

        for (int i = 0; i < m - h+1; i++) {
            for (int j = 0; j < n - w+1; j++) {
                int tempTiming = colSlicing[i][j];
                if(tempTiming==0){
                    answer= new int[]{i,j};
                    return answer;

                }else if(tempTiming>bestTiming){
                    bestTiming = tempTiming;
                    answer= new int[]{i,j};
                }


            }
        }

        return answer;
    }
}

상세 코드

가로 슬라이싱

// 가로 슬라이싱. 구역 내 최솟값 저장
        int[][] rowSlicing = new int[m][n-w+1];

        for(int i=0;i<m;i++){
            Deque<Integer> deque = new ArrayDeque<>(); //앞쪽 값이 항상 최솟값
            //이 deque은 값이 아니라 인덱스가 저장됨

            for(int j=0;j<n;j++){
                int now = map[i][j]==0 ? INF : map[i][j]; //비 안 맞았다면 INF.(번째 순서 비교 위함)

                while(!deque.isEmpty()){
                    int last = deque.peekLast(); //덱의 맨 뒤 인덱스
                    int lastVal = map[i][last]==0 ? INF : map[i][last]; //해당 칸이 비 안 맞는다면 INF, 아니면 순서

					//덱 오름차순 유지
                    if(lastVal>=now) deque.pollLast(); //현재값보다 크거나 같으면 제거
                    else break; //현재보다 작으면 중단

                }
                deque.offerLast(j); //현재 인덱스 덱 뒤에 추가
                if(deque.peekFirst()<=j-w) deque.pollFirst(); //이 윈도우에서의 최솟값이 범위 내인지 판단. 
                // 윈도우 범위 벗어남 = 맨 왼쪽 인덱스가 시작점보다 작다면 제거
                if(j>=w-1){ //윈도우가 w칸 채워진 경우에만 저장
                    rowSlicing[i][j-w+1]=map[i][deque.peekFirst()]; //해당 윈도우 내 최솟값
                }
            }
        }

• map == 0 (비 안 맞음) → INF 처리 → 최솟값 비교 시 우선순위 최하위
• 각 행에 대해 크기 w 슬라이딩 윈도우 내 최솟값의 인덱스를 덱에 저장
• 덱은 인덱스를 저장하며, 앞쪽이 항상 현재 윈도우의 최솟값 인덱스
• 뒤부터 비교하며 현재값 이상인 원소 제거 → 단조 증가(오름차순) 덱 유지
  • 결국 덱에는 지금보다 앞서 탐색한 값들이 저장되어있는데, 최솟값을 저장해야하는 상황에서 나보다 큰 값은 poll해도 상관없다.

세로 슬라이싱

// 세로 슬라이싱
        int[][] colSlicing = new int[m - h+1][n - w+1];
        for (int j = 0; j < n-w+1; j++) {
            Deque<Integer> deque = new ArrayDeque<>();//앞쪽 값이 항상 최솟값
            //이 deque은 값이 아니라 인덱스가 저장됨
            for (int i = 0; i < m; i++) {
                int now = rowSlicing[i][j]==0 ? INF : rowSlicing[i][j];
                while(!deque.isEmpty()){
                    int last = deque.peekLast(); //덱 마지막 인덱스
                    int  lastVal = rowSlicing[last][j]==0 ? INF : rowSlicing[last][j]; //덱 마지막 인덱스가 0이면 값은 무한
                    if(lastVal>=now) deque.pollLast(); //현재 값보다 크거나 같으면 제거
                    else break; //덱 마지막 값이 현재보다 작으면 중단
                }
                deque.offerLast(i); //현재 인덱스 덱 뒤에 추가
                if(deque.peekFirst()<i-h+1)  deque.pollFirst(); //윈도우 범위 벗ㅇ어남 = 맨 왼쪽 인덱스보다 작다면 제거
                if(i>=h-1){
                    colSlicing[i-h+1][j]=rowSlicing[deque.peekFirst()][j]; //해당 윈도우 내 최솟값
                }
            }
        }

위에서 계산한 가로 슬라이싱을 기준으로 방향만 바꿔 계산

결과 계산

		int bestTiming = Integer.MIN_VALUE;

        for (int i = 0; i < m - h+1; i++) {
            for (int j = 0; j < n - w+1; j++) {
                int tempTiming = colSlicing[i][j];
                if(tempTiming==0){
                    answer= new int[]{i,j};
                    return answer;

                }else if(tempTiming>bestTiming){
                    bestTiming = tempTiming;
                    answer= new int[]{i,j};
                }


            }
        }

정리

• 문제를 보고 나이브하게 접근하는게 정답이 아닌 경우가 대부분이다.
• 문제 조건을 보고 시간복잡도를 먼저 계산한 후 아슬아슬하다면 다른 방법을 고안하자
• 알고리즘을 떠올리는 것부터 어려웠다.
• 슬라이딩 윈도우를 드디어 이해한 것 같다.
• 2차원 배열에서의 슬라이딩 윈도우를 풀어봤다.
• 다만, 합을 구하는 문제가 아니라 구역 내 최솟값을 갱신하며 풀어야했기에 한 번 더 꼰 문제라고 느껴졌다
• 문제 선정 후 약 5일동안 공부를 하며 푼 문제다
• 다시 나오면 내가 풀 수 있을까...