코딩테스트 - 정수삼각형

프로그래머스 코딩테스트 정수삼각형을 풀어봤습니다

 

문제는 아래와 같습니다

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

코딩테스트 연습 - 정수 삼각형

 

아래로 내려오면서 순서대로 계산만 잘 해주면 됩니다.

 

아래는 제가 짠 코드입니다.

 

public class 정수삼각형 {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int[][] triangle= {{7}, {3, 8}, {8, 1, 0}, {2, 7, 4, 4}, {4, 5, 2, 6, 5}};
		System.out.println("answer : "+solution(triangle));
	}

	//배열 확인용 메소드
	public static void printArr(int[][] arr,String arrName) {
		System.out.println(arrName);
		for(int i=0;i<arr.length;i++) {
			for(int j=0;j<arr[i].length;j++) {
				System.out.print(arr[i][j]+" ");
			}
			System.out.println();
		}
		System.out.println("------------------------");
	}
	
    public static int solution(int[][] triangle) {
        int answer = 0;
        
        int length = triangle.length;
        
        int[][] tempArr=new int[length][length];
             
        int first = triangle[0][0];
        //최초계산
        tempArr[1][0]=first+triangle[1][0];
        tempArr[1][1]=first+triangle[1][1];

        for(int firstIdx=1;firstIdx<length-1;firstIdx++){
            for(int secondIdx=0;secondIdx<triangle[firstIdx].length;secondIdx++){
                int bottomFirstIdx = firstIdx+1;
                int bottomSecondIdx = secondIdx;
                //맨앞에계산 
                if(secondIdx==0) {
                	//어차피 맨처음에 계산하기 때문에 크기비교가 필요없음.
                	tempArr[bottomFirstIdx][bottomSecondIdx]=tempArr[firstIdx][secondIdx]+triangle[bottomFirstIdx][bottomSecondIdx];
                	tempArr[bottomFirstIdx][bottomSecondIdx+1]=tempArr[firstIdx][secondIdx]+triangle[bottomFirstIdx][bottomSecondIdx+1];
                }else if(secondIdx == triangle[firstIdx].length-1) { //맨뒤의 경우 계산
                	tempArr[bottomFirstIdx][bottomSecondIdx+1]=tempArr[firstIdx][secondIdx]+triangle[bottomFirstIdx][bottomSecondIdx+1];
                	//크기비교를 해주어야함.
                	if(tempArr[bottomFirstIdx][bottomSecondIdx]<tempArr[firstIdx][secondIdx]+triangle[bottomFirstIdx][bottomSecondIdx])
                		tempArr[bottomFirstIdx][bottomSecondIdx]=tempArr[firstIdx][secondIdx]+triangle[bottomFirstIdx][bottomSecondIdx];
                }else { //중간자리 계산.
                	//중간자리의 경우 앞뒤에 이미 계산된 값이 있기때문에 비교가 꼭 필요함.
                	if(tempArr[bottomFirstIdx][bottomSecondIdx+1]<tempArr[firstIdx][secondIdx]+triangle[bottomFirstIdx][bottomSecondIdx+1])
                		tempArr[bottomFirstIdx][bottomSecondIdx+1]=tempArr[firstIdx][secondIdx]+triangle[bottomFirstIdx][bottomSecondIdx+1];
                	if(tempArr[bottomFirstIdx][bottomSecondIdx]<tempArr[firstIdx][secondIdx]+triangle[bottomFirstIdx][bottomSecondIdx])
                		tempArr[bottomFirstIdx][bottomSecondIdx]=tempArr[firstIdx][secondIdx]+triangle[bottomFirstIdx][bottomSecondIdx];
                }
            }
            printArr(tempArr,"tempArr");
        } 
        for(int idx=0;idx<length;idx++){
            if(answer<tempArr[length-1][idx])
                answer=tempArr[length-1][idx];
        }
        
        return answer;
    }
}

 

저의 경우 tempArr배열을 임의로 만들어줘서 배열을 순회하면서 tempArr배열에 계산된 값을 넣어줬습니다.

 

이때 가장큰값을 찾는게 목표이므로 크기비교를 해주는게 중요합니다.

그리고 저의경우 인덱스가 많이 햇갈려서 변수이름이 길어지더라도 명확히 알 수 있는 변수명으로 해줬습니다

(이차원배열 첫번째 인덱스 : firstIdx,

이차원배열 두번째 인덱스 : secondIdx,

이차원배열 아래의 첫번째 인덱스 : bottomFirstIdx,

이차원배열 아래의 두번째 인덱스 : bottomSecondIdx)

 

문제자체가 어려운 수학적지식이나 컴퓨터지식을 요구하는편이 아니라서 이해만 하신다면 차근차근 정리하면서 쉽게 푸실수 있을겁니다~