알고리즘 문제 풀어보기 - 백준 #11497번: 통나무 건너뛰기 (JAVA)

 

 

https://www.acmicpc.net/problem/11497

11497번: 통나무 건너뛰기

 

어려웠는데 생각보다 간단한 문제.

이런 느낌으로 세우면 되는건 알겠는데

그걸 어떻게 구하냐...에서 막힌듯

 

만약 저 그림 처럼 정렬이 되어있다면..

1. 가장 큰 요소는 왼쪽과 오른쪽을 모두 검사,

 

2. 그렇지 않은 요소들은 자신의 옆에있는 요소만 검사

 

3. 가장 작은 요소는 돌아가서 맨 첫번째or 마지막에 있는 요소를 검사

 

겠지만 저렇게 정렬을 하는게 쉽지 않다..

 

그러나 오름차순 혹은 내림차순 정렬이 되어 있다면?

1. 가장 큰 요소는 왼쪽과 오른쪽을 모두 검사

=> 가장 마지막 요소로 부터 1칸옆에 있는 요소와 2칸 옆에 있는 요소를 검사한다.

 

2. 그렇지 않은 요소들은 자신의 옆에있는 요소만 검사

=> 자신의 2칸 옆에 있는 요소와 검사한다.

 

3. 가장 작은 요소는 돌아가서 맨 첫번째or 마지막에 있는 요소를 검사

=> 가장 작은 요소와 그다음 작은 요소를 검사한다.

 

 

import java.util.Scanner;

public class log_11497 {
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		
		//몇개의 배열을 입력할지 입력받는다
		int n=scanner.nextInt();
		int[] count= new int[n]; 
		int[] result=new int[n]; //결과값
	 
		// n번 동안 반복한다.
		for(int k=0;k<n;k++) {
			//각 배열의 길이를 입력받는다.
			count[k]=scanner.nextInt();
			int length=count[k]; //편의상 length로 두기
			int array[]=new int[length]; //새로운 배열 생성
			//배열 요소를 입력받는다.
			for(int j=0;j<length;j++) {
				array[j]=scanner.nextInt();
			}		
			
			//입력받는 배열 array 정렬(오름차순 정렬)
			//선택 정렬 방식
			int temp=0;
			int index=0;
			for( int i=0; i<length;i++) {	
				int min=100001; // (1 ≤ Li ≤ 100,000)
				for(int j=i;j<length;j++) {
					if(min>array[j]) {
						min=array[j];
						index=j;
					}
				}
				temp=array[i];
				array[i]=array[index];
				array[index]=temp;				
			}
			

			int difficulty=0; //난이도
			int top=length-1; //마지막 요소 인덱스
			int height=0; //따로 높이차를 보관.
			int height_a=0;int height_b=0;
			//높이차를 비교한다.
			for(int f=top;f>=1;f--) {
				if(f==top) { //top일때는
					height_a=array[f]-array[f-1]; //왼쪽과
					height_b=array[f]-array[f-2]; //오른쪽을 
					//모두 비교해야한다.
					//비교 후 차이가 더 큰 쪽을 난이도로 둔다,
					if(height_a>height_b) {
						difficulty=height_a;
					}
					else {
						difficulty=height_b;
					}
				}
				else if(f==1) { //array[1]을 비교할때는  
					//바로 다음 요소만 비교해야한다.
					height=Math.abs(array[1]-array[0]); 
					
					//저장된 난이도보다 더 크면 그것을 난이도로 친다.
					if(difficulty<height) {
						difficulty=height;
					}		
				}
				else { //그외의 경우에는
					height=array[f]-array[f-2]; 
					//왼쪽으로 2칸 차이 요소랑 비교한다.
					
					//저장된 난이도보다 더 크면 그것을 난이도로 친다.
					if(difficulty<height) {
						difficulty=height;
					}
				}							
			}
			result[k]=difficulty; //k번째 배열의 결과를 저장한다.
				
			
		}
		//결과 출력
		for (int j=0;j<n;j++) {
			System.out.println(result[j]);	
		}
	}
}

느낀점: 코드가 너무 길다... 아직 풀이를 하나도 안보고 푸는걸 잘 못한다. 최소 1시간 이상 고민해보기.