[코테] 땅따먹기_2단계

 

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

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

 

 

 

---

1차 풀이

public class 땅따먹기1_이전인덱스와현재인덱스_비교구현 {

	public static void main(String[] args) {
		// TODO Auto-generated method stub

		System.out.print(solution(new int[][] {
			{1,2,3,5},
			{5,6,7,8},
			{4,3,2,1}
			}));
	}
	
	public static int solution(int[][] land) {
	        int answer = 0;
	        
	        // 1.이전 배열에서 몇 번째의 인덱스를 선택했는지
	        // 2.그 행에서, 제일 높은 값을 선택 (조건!! 이전꺼의 인덱스의 번째는 선택 못하고, 
	        //                               그 다음 큰수를 선택해야함)
	        // 3.선택한 값들을 계속 더하는 변수 하나 필요!!!!
	        
	        // 주의 - 이전 인덱스랑 같은 곳이면 안됨
	        
	        int currentIndex = -1; // 현재 인덱스 값
	        int tempIndex = 0; // 임시 인덱스 값 
	        int preIndex = 0; // 이전 인덱스 값 저장
	        int preIndexFirst = 0; // 첫번째 인덱스 값 저장
	        int firstV; // 각 행의 첫번째 값
	        int empV = 0; // 열에서 사용하는 임시값
	        int tempMaxValue = 0; // 각 행의 임시 최댓값
	        int rsHV = 0; // 각 행의 최종 최댓값
	        int tempMaxIndex = 0; // 각 행의 임시 최댓값의 인덱스
	        int rsLast=0; // 모두 더한 값
	        for(int i=0;i<land.length;i++) {   // 행 갯수
	        	for(int j=0; j<land[i].length-1;j++) {  // 제일 큰 수 구하기
	        		if(currentIndex==j) {	// 이전 인덱스랑 비교
	        			continue;
	        		}else {
	        			if(currentIndex == -1)
	        				currentIndex++;
	        			
	            		// 가장 큰 값
		        		if(land[i][j]<land[i][j+1]) {
		        			empV = land[i][j+1];
		        			currentIndex = j+1;
		        			
		        		}else {
		        			empV = land[i][j];
		        			currentIndex = j;
		        		}
		        		
		        		// -------------- 수정을 해야 하는 부분 ----------------------------------------------------
//		        		tempMaxValue = empV;         // 각 행의 임시 최댓값
//		        		tempMaxIndex = currentIndex; // 각 행의 임시 최댓값의 인덱스
		        		
//		        		if(rsHV < empV) {
//		        			rsHV = empV;             // 각 행의 최댓값
//		        			tempMaxValue = empV;         // 각 행의 임시 최댓값
//			        		tempMaxIndex = currentIndex; // 각 행의 임시 최댓값의 인덱스
//		        		}
//		        		
		        		
		        		rsHV = empV;    // 각 행의 최댓값
		        		
		        		
		        		// '현재 결과의 인덱스'를 '이전 인덱스'에 담습니다.
	            		if(i>0) {
	            			if(i==1) { // 첫번째 일때,
	            				if(preIndexFirst == currentIndex) {
	            					for(int a=0;a<land[i].length-1;a++) {
	            						if(land[i][a]<empV) {
	            							rsHV=land[i][a]; // 해당 전 값 다시 저장.
	            							preIndex=a; // 이전 인덱스 저장
	            						}
	            					}
	            						                		
	                			}
	            			}
	            			// 두번째 이상 부터,
	            			if(i>1) {
	            				if(currentIndex==preIndex) {
	            					for(int b=0;b<land[i].length-1;b++) {
	            						if(land[i][b]<empV) {
	            							rsHV=land[i][b]; // 해당 전 값 다시 저장.
	            							preIndex=b; // 이전 인덱스 저장
	            						}
	            					}
	            				}
	            			}
	            		}
		        		
//		        		// '이전 인덱스' 와 '현재 인덱스'와 같으면 '다음 작은 값' 이용하기
//		        		if(currentIndex == preIndex) {
//		        			
//		        		}
		        		
		        		// 첫번째 인덱스 구하기
		        		if(i==0) {
		        			tempIndex = currentIndex;
		        		}
	        		}
	        	}
	        	// 첫번째 인덱스 값 저장
	        	preIndexFirst = tempIndex;
	        	
	        	rsLast = rsLast +rsHV;
	        }
	        answer = rsLast;
	        
	        return answer;
	    }
}

미흡 부분 >

1. 각 행의 결과가 이전 인덱스하고 현재 인덱스가 같으면 안됨!!

2. 비교하는 과정 수정 해주어야함 ㅠㅜ

3. 결과가 어떤 것들 담아야할지 변수,,, 다시 선정해주어야 할 듯....

---

2차 풀이

package 프로그래머스_2단계;

public class 땅따먹기1_이전인덱스와현재인덱스_비교구현2 {

	public static void main(String[] args) {
		// TODO Auto-generated method stub

		System.out.print(solution(new int[][] {
			{1,2,3,5},
			{5,6,7,8},
			{4,3,2,1}
			}));
	}
	
	public static int solution(int[][] land) {
	        int answer = 0;
	        
	        // 1.이전 배열에서 몇 번째의 인덱스를 선택했는지
	        // 2.그 행에서, 제일 높은 값을 선택 (조건!! 이전꺼의 인덱스의 번째는 선택 못하고, 
	        //                               그 다음 큰수를 선택해야함)
	        // 3.선택한 값들을 계속 더하는 변수 하나 필요!!!!
	        
	        // 주의 - 이전 인덱스랑 같은 곳이면 안됨
	        
	        int currentIndex = -1; // 현재 인덱스 값
	        int tempIndex = 0; // 임시 인덱스 값  (첫번째 인덱스를 구하기위한 임시 값)
	        int preIndex = 0; // 이전 인덱스 값 저장
	        int preIndexFirst = 0; // 첫번째 인덱스 값 저장
	        int firstV; // 각 행의 첫번째 값
	        int empV = 0; // 열에서 사용하는 임시값
	        int tempMaxValue = 0; // 각 행의 임시 최댓값
	        int rsHV = 0; // 각 행의 최종 최댓값
	        int rsLast=0; // 모두 더한 값
	        int tempSecond = 0; // 두번째로 큰값 저장
	        for(int i=0;i<land.length;i++) {   // 행 갯수
	        	for(int j=0; j<land[i].length-1;j++) {  // 제일 큰 수 구하기
	        		if(currentIndex==j) {	// 이전 인덱스랑 비교
	        			continue;
	        		}else {
	        			if(currentIndex == -1)
	        				currentIndex++;

	            		// 가장 큰 값
		        		if(land[i][j]<land[i][j+1]) {
		        			empV = land[i][j+1];
		        			currentIndex = j+1;
		        			if(preIndexFirst == currentIndex) {  // 이전 인덱스와 현재 인덱스가 같으면
		        				for(int e=0; e<land[i].length;e++) { // 현재 것보다 한단계 작은 값 찾고, 저장
		        					if(empV==land[i][e]) { // 값이 같으면, 그냥 넘기기
		        						System.out.print("값이 같음");
		        					}else if(empV>land[i][e]){ 
		        						if(tempSecond < land[i][e]) {
		        							tempSecond = land[i][e]; // 두번째로 큰값 저장
		        						}
		        					}
		        				}
		        			}
		        		}else {
		        			if(rsHV<land[i][j]) {
		        				empV = land[i][j];
			        			currentIndex = j;
			        			rsHV = empV;
		        			}
		        		}

		        	    // 각 행의 최댓값
		        		rsHV = empV;   
		        		
		        		// ------------------------------------------
		   		        		
		        		// '현재 결과의 인덱스'를 '이전 인덱스'에 담습니다.
	            		if(i>0) {
	            			// 첫번째 일때,
	            			if(i==1) {
	            				if(preIndexFirst == currentIndex) {
	            					for(int a=0;a<land[i].length-1;a++) {
	            						if(land[i][a]<empV) {
	            	
	            							rsHV=land[i][a]; // 해당 전 값 다시 저장.
	            							preIndex=a; // 이전 인덱스 저장
	            						}
	            					}
	            						                		
	                			}
	            			}
	            			// 두번째 이상 부터,
	            			if(i>1) {
	            				if(currentIndex==preIndex) {
	            					for(int b=0;b<land[i].length-1;b++) {
	            						if(land[i][b]<empV) {
	            							rsHV=land[i][b]; // 해당 전 값 다시 저장.
	            							preIndex=b; // 이전 인덱스 저장
	            						}
	            					}
	            				}
	            			}
	            		}
	        			
		        		// 첫번째 인덱스 구하기
		        		if(i==0) {
		        			tempIndex = currentIndex;
		        		}
	        		}
	        	} // ------------------------------------------
	        	
	        	// 첫번째 인덱스 값 저장
	        	preIndexFirst = tempIndex;
	        	
	        	// 최종 결과
	        	rsLast = rsLast +rsHV;
	        	answer = rsLast;
	        	
	        	// 초기화
				rsHV=0;
	        }  // ---------------------------------------------
	        
	        return answer;
	    }
}

통과는 했음,,,

하지만,,,

처리 시간이 개똥임,,,,,

 

 

---

아~~

시작 방향 잘 못 잡은 듯,,,, ㅠㅜ

 

 

 

이렇게 깔끔하게 코드를 짜다니,,,,,,,,

3차 풀이

package 프로그래머스_2단계;

import java.util.*;

public class 땅따먹기2 {

	public static void main(String[] args) {
		// TODO Auto-generated method stub

		System.out.print(solution(new int[][] {
			{1,2,3,5},
			{5,6,7,8},
			{4,3,2,1}
			}));
	}
	
	public static int solution(int[][] land) {
		
		for(int i = 1 ; i < land.length ; i++) {
			
			for(int j = 0 ; j < land[0].length ; j++) {
				
				int sum = 0;
				for(int k = 0; k < land[0].length ; k++) {
					
		    		if(k==j)
		    			continue;
		    		else
		    			sum = Math.max(sum, land[i-1][k]);
				}
				
				land[i][j] += sum;
			}
		}
	
		Arrays.sort(land[land.length-1]);
		
		return land[land.length-1][land[0].length-1];
	    }
	
}