[JAVA]프로그래머스_땅따먹기

문제 : https://programmers.co.kr/learn/courses/30/lessons/12913

코딩테스트 연습 - 땅따먹기

 

문제 유형 :  구현, DP?

 

풀이 방식 

- 우선순위 큐를 이용해서 구현

- 메모이제이션 느낌이로다가 

   1. 행 마다 우선순위큐를 선언 

   2. i 번째 행의 값(land[i][j])과 인덱스(j)를 우선순위 큐에 offer 

   3. 제일 큰 값과 그 다음으로 큰 값을 poll (pq1, pq2)

   4. 조건[땅따먹기 게임에는 한 행씩 내려올 때, 같은 열을 연속해서 밟을 수 없는 특수 규칙이 있습니다.] 을 지키기 위해 i+1행(다음행)에는 최대값의 열이였던곳(pq1[1]) 즉, land[i+1][pq1[1]]은 였던 곳에는 pq2[0]을 더해준다. 그 외에는 pq[1](최대값)을 더하면 됩니다.

 

소스코드

package Programmers;

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

public class 땅따먹기 {

	public static void main(String[] args) {
		int[][] land = {{1,2,3,5}, {5,6,7,8}, {4,3,2,1}};
		System.out.println(solution(land));
	}
	static int solution(int[][] land) {
        int landLength = land.length;
        for (int i = 0; i < landLength-1; i++) {
            //1. 행 마다 우선순위큐를 선언 
        	PriorityQueue<int[]> pq = new PriorityQueue<int[]>(new Comparator<int[]>() {
				@Override
				public int compare(int[] o1, int[] o2) {
					return o2[0]-o1[0];
				}
			});
            
            //2. i 번째 행의 값(land[i][j])과 인덱스(j)를 우선순위 큐에 offer 
        	for (int j = 0; j < 4; j++) {
				pq.offer(new int[] {land[i][j], j});
			}
            
            //3. 제일 큰 값과 그 다음으로 큰 값을 poll (pq1, pq2)
        	int[] pq1 = pq.poll(); 
        	int[] pq2 = pq.poll(); 
        	int max1Value = pq1[0]; // 최대값
        	int max1Idx = pq1[1];   // 최대값 인덱스 
        	int max2Value = pq2[0]; // 최대값 전 최대값
        	
            //4. 조건[땅따먹기 게임에는 한 행씩 내려올 때, 같은 열을 연속해서 밟을 수 없는 특수 규칙이 있습니다.] 을 지키기 위해 i+1행(다음행)에는 최대값의 열이였던곳(pq1[1]) 즉, land[i+1][pq1[1]]은 였던 곳에는 pq2[0]을 더해준다. 그 외에는 pq[1](최대값)을 더하면 됩니다.
        	for (int j = 0; j < 4; j++) {
				if(j==max1Idx) {
					land[i+1][j] = land[i+1][j] + max2Value;
				}else {
					land[i+1][j] = land[i+1][j] + max1Value;
				}
			}
        	
		}
        int answer = -1;
        for(int i=0;i<4;i++) {
        	if(land[landLength-1][i]>answer) answer = land[landLength-1][i];
        }
        
        
        return answer;
    }
}