알고리즘(라면 공장, 가장 큰 정사각형 찾기)

[라면 공장]

 

* 로직

• stock 값보다 같거나 큰 날짜를 우선순위 큐에 집어넣는다
• 여기서 우선순위 큐 정렬 방식은 공급일이 긴 순으로 내림차순이다 (그래야 최소 일수로 채워나갈 수 있기 때문에)
• 큐에서 꺼내어 stock에 누적시켜주고, 답을 카운팅한다

 

import java.util.Comparator;
import java.util.PriorityQueue;

class Solution {
    public int solution(int stock, int[] dates, int[] supplies, int k) {
        int answer = 0;

        int idx=0;
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(Comparator.reverseOrder());
        while (stock < k) {
            for(int i=idx; i<dates.length; ++i) {
                if(dates[i] <= stock) {
                    priorityQueue.offer(supplies[i]);
                    idx = i+1;
                }
            }

            if(!priorityQueue.isEmpty()) {
                int q = priorityQueue.poll();
                stock += q;
                answer++;
            }
        }

        return answer;
    }
}

 

[가장 큰 정사각형 찾기]

 

* 로직

• (1,1)부터 기준점을 이동하며 2*2 사이즈의 사각형을 만들고, 현재칸을 제외한 (나머지칸 값 중 최솟값 + 1)을 현재 칸에 누적시킨다
•  즉, 각 칸의 값은 현재 위치에서 만들 수 있는 정사각형의 사이즈 크기가 담긴다고 생각하면 된다
• 기준점을 이동하며 이전에 만들 수 있는 정사각형 사이즈 값을 활용하기 때문에 DP라고 볼 수 있다
• 현재 칸의 값을 갱신할 때, answer에도 최솟값을 갱신해준다
• 한줄인 경우(1*N or N*1)에는 모든 칸을 한 칸씩 탐색하여 1*1 정사각형을 만들 수 있는지 판별한다

 

class Solution {
    
    public int solution(int [][]board) {
        int answer = 0;
        int N = board.length;
        int M = board[0].length;        
        
        // 1*1 정사각형만 만들 수 있는 경우
        if(N == 1 || M == 1) {
            for(int i=0; i<N; ++i) {
                for(int j=0; j<M; ++j){
                    if(board[i][j] == 1) {
                        return 1;
                    }
                }
            }        
        }
        
        else {
            for(int i=1; i<N; ++i) {
                for(int j=1; j<M; ++j) {
                    if(board[i][j] == 1){
                        board[i][j] = Math.min(board[i-1][j], Math.min(board[i][j-1], board[i-1][j-1])) + 1;
                        answer = Math.max(answer, board[i][j]);
                    }                    
                }                                
            }                        
        }        

        return answer*answer;
    }
}