(프로그래머스)동적계획법 - 정수삼각형 풀이

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

 

 

풀이: hashmap 과 class 를 이용해서 메모이제이션을 했다.(실패: 시간초과) 

 

int 로 배열을 만들어서 메모이제이션을 쓰고싶었다. 종만북에서는 2차원 배열을 만들어서 메모이제이션을 구현했다. 

그럼 나도 2차원 배열로 하면 되는데, 문제는 종만북이 C++ 이라, C++ 을 모르는 나는 지레 겁먹고, java 로 구현한 사람들을 찾아 나섰다. -> 그냥 구현 하면 되는데. C++ 에서 참조형 변수(int &ret)를 쓰길래 뭔가 있나보다하고 회피했다. -> 이 회피로 하루를 낭비하게된다. 

 

java로 풀이 한 것들을 찾아보다가 hashmap 으로 한 개발자가 있어서 참조했고, 

내 문제에 맞게 2차원 배열과 해당 하는 값을 표현하기 위해 class<Integer,Integer>로 인덱스 하나를 표현했다. 지금 보면 정말 쓸데없는 메모리 낭비다.. 

 

결과는 처참했다. 

완전탐색으로 푼 것: 정확도 50% 였는데, 

메모이제이션을 썼음에도 불구하고 

정확도 32.1% 에 그외는 시간초과로 다 실패했다. 

풀이 접근 방식은 종만북 방식과 동일했다. 

1. 메모이제이션으로 각 부분문제당 1번만 풀도록 하였다. 

2. 입력 정리 : make_sum의 입력중 dp 도 포함되어있었는데, hashmap 이 public 인데 굳이 함수 실행될때마다 넘겨줄 필요가 없어서 없앴다. 

 

하지만, 시간초과가 계속나서 멘붕상태로 하루를 보냈다. 

 

 

hashmap 과 class 로 메모이제이션 한 코드: 실패..(정확도 32.1%)

import java.util.HashMap;

public class Solution3_1 {
// int[] 를 쓰고싶은데 방법을 몰라서 클래스로 정의했다. 
	public static class index {
 	    public int x;
 	    public int y;

 	    public index(int x, int y) {
 	        this.x = x;
 	        this.y = y;
 	    }
 	}
	 public HashMap<index,Integer> dp = new HashMap<index,Integer>();
	 public int solution(int[][] triangle) {
		    return make_sum(triangle,0,0);
		}
	 //최대 값만 찾아서 반환해주는 함수  - 이 코드는 사실상 삼각형의 거꾸로 실행된다. 토너먼트 식 
	 public int make_sum(int[][] triangle,int x,int y) {
			if(x==triangle.length-1) { 
				return triangle[x][y];
				}
			if(dp.containsKey(new index(x,y))) {
				return dp.get(new index(x,y));
			}
			int value = Math.max(make_sum(triangle,x+1,y),make_sum(triangle,x+1,y+1))+ triangle[x][y];
			dp.put(new index(x,y),value);
			return value;
		}
}

 

다음날, 풀이 방식 자체는 문제가 없는데, 생각해보니 2차원배열로 메모이제이션을 그냥 해도 될거 같다는 생각이들었다. 

 

2차원 배열로 메모이제이션한 코드: 성공!! 

// 시간이 너무 오래걸리는게 hash 와 index 클래스 때문인거 같아서 
// 그냥 배열로 선언해보았다. 문제 제한상 삼각형 높이가 500이므로 500,500 으로 설정한다. 

public class Solution3_2 {
	
	 int [][] matrixmap =new int[500][500];
	 public int solution(int[][] triangle) {
		    return make_sum(triangle,0,0);
		}
	 //최대 값만 찾아서 반환해주는 함수  - 이 코드는 사실상 삼각형의 거꾸로 실행된다. 토너먼트 식 
	 public int make_sum(int[][] triangle,int x,int y) {
			if(x==triangle.length-1) { 
				return triangle[x][y];
				}
			if(matrixmap[x][y]!= 0) {
				return matrixmap[x][y];
			}
			int value = Math.max(make_sum(triangle,x+1,y),make_sum(triangle,x+1,y+1))+ triangle[x][y];
			matrixmap[x][y]=value;
		
			return value;
		}
}

 문제 조건 따라 배열을 500,500 으로 설정했다.

• 삼각형의 높이는 1 이상 500 이하입니다.