뽀미의 개발노트

프로그래머스. 피로도 (자바) (미완성) 본문

Algorithm_Test

프로그래머스. 피로도 (자바) (미완성)

산타는 뽀미 2023. 8. 16. 21:54

[문제 설명]

XX게임에는 피로도 시스템(0 이상의 정수로 표현합니다)이 있으며, 일정 피로도를 사용해서 던전을 탐험할 수 있습니다. 이때, 각 던전마다 탐험을 시작하기 위해 필요한 "최소 필요 피로도"와 던전 탐험을 마쳤을 때 소모되는 "소모 피로도"가 있습니다. "최소 필요 피로도"는 해당 던전을 탐험하기 위해 가지고 있어야 하는 최소한의 피로도를 나타내며, "소모 피로도"는 던전을 탐험한 후 소모되는 피로도를 나타냅니다. 예를 들어 "최소 필요 피로도"가 80, "소모 피로도"가 20인 던전을 탐험하기 위해서는 유저의 현재 남은 피로도는 80 이상 이어야 하며, 던전을 탐험한 후에는 피로도 20이 소모됩니다.

이 게임에는 하루에 한 번씩 탐험할 수 있는 던전이 여러개 있는데, 한 유저가 오늘 이 던전들을 최대한 많이 탐험하려 합니다. 유저의 현재 피로도 k와 각 던전별 "최소 필요 피로도", "소모 피로도"가 담긴 2차원 배열 dungeons 가 매개변수로 주어질 때, 유저가 탐험할수 있는 최대 던전 수를 return 하도록 solution 함수를 완성해주세요.

[제한사항]

k는 1 이상 5,000 이하인 자연수입니다.
dungeons의 세로(행) 길이(즉, 던전의 개수)는 1 이상 8 이하입니다.
dungeons의 가로(열) 길이는 2 입니다.
dungeons의 각 행은 각 던전의 ["최소 필요 피로도", "소모 피로도"] 입니다.
"최소 필요 피로도"는 항상 "소모 피로도"보다 크거나 같습니다.
"최소 필요 피로도"와 "소모 피로도"는 1 이상 1,000 이하인 자연수입니다.
서로 다른 던전의 ["최소 필요 피로도", "소모 피로도"]가 서로 같을 수 있습니다.

[입출력 예]

k dungeons result
80 [[80,20],[50,40],[30,10]] 3

입출력 예 설명
현재 피로도는 80입니다.

만약, 첫 번째 → 두 번째 → 세 번째 던전 순서로 탐험한다면

현재 피로도는 80이며, 첫 번째 던전을 돌기위해 필요한 "최소 필요 피로도" 또한 80이므로, 첫 번째 던전을 탐험할 수 있습니다. 첫 번째 던전의 "소모 피로도"는 20이므로, 던전을 탐험한 후 남은 피로도는 60입니다.
남은 피로도는 60이며, 두 번째 던전을 돌기위해 필요한 "최소 필요 피로도"는 50이므로, 두 번째 던전을 탐험할 수 있습니다. 두 번째 던전의 "소모 피로도"는 40이므로, 던전을 탐험한 후 남은 피로도는 20입니다.
남은 피로도는 20이며, 세 번째 던전을 돌기위해 필요한 "최소 필요 피로도"는 30입니다. 따라서 세 번째 던전은 탐험할 수 없습니다.
만약, 첫 번째 → 세 번째 → 두 번째 던전 순서로 탐험한다면

현재 피로도는 80이며, 첫 번째 던전을 돌기위해 필요한 "최소 필요 피로도" 또한 80이므로, 첫 번째 던전을 탐험할 수 있습니다. 첫 번째 던전의 "소모 피로도"는 20이므로, 던전을 탐험한 후 남은 피로도는 60입니다.
남은 피로도는 60이며, 세 번째 던전을 돌기위해 필요한 "최소 필요 피로도"는 30이므로, 세 번째 던전을 탐험할 수 있습니다. 세 번째 던전의 "소모 피로도"는 10이므로, 던전을 탐험한 후 남은 피로도는 50입니다.
남은 피로도는 50이며, 두 번째 던전을 돌기위해 필요한 "최소 필요 피로도"는 50이므로, 두 번째 던전을 탐험할 수 있습니다. 두 번째 던전의 "소모 피로도"는 40이므로, 던전을 탐험한 후 남은 피로도는 10입니다.
따라서 이 경우 세 던전을 모두 탐험할 수 있으며, 유저가 탐험할 수 있는 최대 던전 수는 3입니다.

[문제 해결 과정]

일단 현재 피로도가 던전의 최소 필요 피로도보다 작다면 그 던전은 못 들어감! 유저는 최대한 많은 던전을 탐험해야 하므로 자기 현재 피로도로 갈 수 있는 던전 중에서 소모 피로도가 적은 순으로?? 가면 좋을까?
그럼 테스트 케이스로 따지면 현재 피로도 80이므로 세 던전 모두 갈 수 있고, 소모 피로도가 제일 적은 세번째 던전 먼저 간다면?
80 -> 70 이 되고, 그 다음 소모 피로도가 적은 첫번째 던전을 그 다음으로 간다면
못간다... 3번째 던전을 제일 먼저 가면 던전 간 횟수가 3번이 될 수가 없는것!


던전은 1개에서 8개까지 주어진다.
1. 그럼 일단 던전의 길이만큼 반복문을 돌린다. 이차원 배열에서 던전의 길이는 던전의 갯수와 같다.
2. 최소 필요 피로도가 현재 피로도보다 작은 던전 중에서, 피로 소모도가 가장 작은 던전을 우선으로 들어간다.
3. 그럼 현재 피로도에서 피로 소모도만큼 깎는다.
4. 그 다음 남은 던전들 중에서 위 2~3번 과정을 반복한다.

음 그러려면 피로 소모도가 작은 순서대로 2차원 배열을 다시 재배열 해야하나?
그것도 모든 던전이 아니라 최소 필요 피로도가 현재 피로도보다 작은 던전들만!
아니지!!! 다시 생각해보기.
던전들 중에서 최소 필요 피로도가 높은데를 먼저 가는게 유리하므로
정렬을 최소 필요 피로도 내림차순, 그리고 그 안에서 소모 필요도가 낮은 순으로 정렬??
근데 그러면 그냥 주어진 테스트 케이스 배열이랑 똑같은데... 이게 아닌가
음.. 정렬을 하는게 답이 아닌가아..

일단 어떤 던전에 들어가서 걔의 피로 소모도 만큼 내 현재 피로도가 깎인다면,
그 깎인 피로도를 가지고 다른 던전들을 바라본다. 남은 던전들의 최소 어쩌구가 내 현재 피로도보다 다 작다고 해도
아무곳이나 들어가면 안된다.... 그 경우를 어떻게 전부 다 해보지?
전부다 들어가서 들어갈 수 있는 던전수 전부다 세서 그중 제일 많은거??? 아니지..
그럼 던전 8개라고 했을 때 8개를 줄 세우는 방법은 8!인데.. 그 경우의 수를 다 계산하는건 너무 비효율적..
그러니까 지금 내 현재피로도보다 최소 어쩌구가 작기만 하면.. 그 다음으로 어떤 던전을 들어가는게 유리할까?

최소필요도는 최대한 크면서 소모 필요도는 작은 던전일수록 유리한건가??
일단 지금 주어진 테스트 케이스로는 그래보이긴 하는데...
왜냐면 첫번째 던전은 두 수의 차이 60, 두번째 던전은 10, 세번째 던전은 20이니까...
아 테스트 케이스 좀 많이 좀 주지ㅠㅠ

어떤 던전을 들어가던지 간에.. 
걔를 갔다가 나온 다음 나의 현재 피로도가 다른 모든 던전들의 최소 필요 피로도보다 크면 가장 유리하다...
첫번째 던전을 제일 먼저 가면 남은 피로도 60, 이걸로 다른 던전 두 곳 다 갈수 있음
두번째 던전을 제일 먼저 가면 남은 피로도 40, 이걸로는 남은 한곳만 갈 수 있음
세번째 던전을 제일 먼저 가면 남은 피로도 70, 이걸로도 남은 한곳만 갈 수 있음...

그러니까 어느 던전을 갔다 나온 다음 나의 피로도가 다른 던전들의 최소 필요 피로도보다 커야된다...
그럼 이걸 비교를 어케 하징... 너무 어렵땅....

일단 여기까지 50분 걸림.. 일단 너무 어려우므로 운동장 몇바퀴 뛰고 오겟음...

A FEW DAYS LATER...

자... 다시 생각해보자
1) 만약 소모를 기준으로 오름차순 배열한 뒤 그 순서대로 간다면??
-> 반례가 있음. 현재 80이고 [30, 10] 짜리를 먼저 간다면 [80,20] 짜리를 갈 수 없을 것임
2) 만약 최소를 기준으로 내림차순 배열한 뒤 그 순서대로 간다면??
-> 반례가 있음. [80,20]에 먼저 가서 60 됐으면 [50, 40]을 먼저 가는 것보다 [30,10]을 먼저 가는게 나음.
3) 그럼 혹시 (최소 - 소모) 순으로 내림차순 해서 그 순서대로 가는건가...?
-> [100, 20], [30, 20], [70, 50], [10, 5], [50, 10] 이 새로운 테스트 케이스를 보면
최소 - 소모는 80, 10, 20, 5, 40 이고 놀랍게도 이대로 내림차순을 해서 그 순서대로 가면
제일 많은 던전을 갈 수 있기는 함...
음.. 이게 맞는지는 모르겠지만 일단 해볼까? 그럼 어떻게 배열을 정렬한다고 하면 될까..
일단 만약 최소-소모를 해서 그 차이가 똑같은게 있으면 일단 최소가 높은거가 더 앞으로 나오게..?

2차원 배열을 정렬해야 할 것 같다. 찾아보니 자바에서 2차원 배열을 정렬하려면
Comparable 또는 Comparator를 써야한다고 한다.

참고 블로그
https://st-lab.tistory.com/243

 

자바 [JAVA] - Comparable 과 Comparator의 이해

아마 이 글을 찾아 오신 분들 대개는 Comparable과 Comparator의 차이가 무엇인지 모르거나 궁금해서 찾아오셨을 것이다. 사실 알고보면 두 개는 그렇게 어렵지 않으나 아무래도 자바를 학습하면서 객

st-lab.tistory.com

음 그럼 이차원 배열에서 뒤에 숫자를 하나 더 추가해볼까?
그래야 걔 기준으로 내림차순 정렬할 수 있으니까!!
arr[0][0] = 100, arr[0][1] = 20, arr[0][2] = 80
arr[1][0] = 30, arr[1][1] = 20, arr[1][2] = 10 이런식으로?
그럼 반복문을 돌면서 일단 arr[][2] 에 값을 넣어주자!

[처음 풀어낸 코드, 근데 테스트 케이스 몇개는 실패함]

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

public class Main {
	public static void main(String[] args) {

		// int[][] dungeons = new int[][] {{80, 20}, {50, 40}, {30, 10}};
		int[][] dungeons = new int[][] {{100, 20}, {30, 20}, {70, 50}, {10, 5}, {50, 10}};
		// 던전들의 최소 필요 피로도와 소모 피로도
		
		int k = 120;
		// 현재 피로도
		
		System.out.println(dungeons.length);
		
		int[][] plus_diff = new int[dungeons.length][3];
		// 던전 갯수는 똑같은데 칸 하나 더 추가될 배열 새롭게 만들기
		
		for(int dunNum = 0 ; dunNum < dungeons.length ; dunNum++) {
			plus_diff[dunNum][0] = dungeons[dunNum][0];
			plus_diff[dunNum][1] = dungeons[dunNum][1];
			plus_diff[dunNum][2] = dungeons[dunNum][0] - dungeons[dunNum][1];
			// 마지막 칸에는 (최소 필요 피로도 - 소모 피로도)를 적을 것임
		}
		
		System.out.println(Arrays.deepToString(plus_diff));
		
		Arrays.sort(plus_diff, Comparator.comparingInt((int[] o) -> o[2]).reversed());
		// 배열의 세번째 숫자 기준으로 내림차순 정렬하기
		
		System.out.println(Arrays.deepToString(plus_diff));
		
		int answer = 0;
		// 탐험할 수 있는 최대 던전 수
		
		for (int dunNum = 0 ; dunNum < plus_diff.length ; dunNum++) {
			if (k >= plus_diff[dunNum][0]) {
				k -= plus_diff[dunNum][1];
				answer++;
				// 내 현재 피로도가 최소 필요 피로도 이상이면
				// 그 던전의 소모 필요도만큼 내 현재 피로도 감소
				// 탐험한 던전 수는 1 증가 
			} else {
				continue;
				// 차이가 똑같아도 최소 필요 피로도에 따라
				// 다음 던전을 갈 수도 있고 안 갈 수도 있기 때문에
				// 만약 현재 피로도가 최소 필요 피로도보다 낮으면
				// 일단 다음 던전으로 넘어갈 것임
			}
		}
		
		System.out.println("탐험한 던전 수 : " + answer);
		
	}
}

왜 틀렸을까?? 테스트 케이스 19개 중 3개만 실패하고 나머지는 패스했다... 왜지........

arr[][2] 값이 똑같을때는 arr[][1]값 기준으로 내림차순 하고 싶은데!!
정렬 조건 하나 더 추가해주자!!!

[정렬 기준 추가해서 푼 코드, 근데 테스트 케이스 또 실패함]

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

public class Main {
	public static void main(String[] args) {

		// int[][] dungeons = new int[][] {{80, 20}, {50, 40}, {30, 10}};
		// int[][] dungeons = new int[][] {{100, 20}, {30, 20}, {70, 50}, {10, 5}, {50, 10}};
		int[][] dungeons = new int[][] {{80, 30}, {50, 40}, {30, 10}, {20, 10}};
		// 던전들의 최소 필요 피로도와 소모 피로도
		
		int k = 80;
		// 현재 피로도
		
		System.out.println(dungeons.length);
		
		int[][] plus_diff = new int[dungeons.length][3];
		// 던전 갯수는 똑같은데 칸 하나 더 추가될 배열 새롭게 만들기
		
		for(int dunNum = 0 ; dunNum < dungeons.length ; dunNum++) {
			plus_diff[dunNum][0] = dungeons[dunNum][0];
			plus_diff[dunNum][1] = dungeons[dunNum][1];
			plus_diff[dunNum][2] = dungeons[dunNum][0] - dungeons[dunNum][1];
			// 마지막 칸에는 (최소 필요 피로도 - 소모 피로도)를 적을 것임
		}
		
		System.out.println(Arrays.deepToString(plus_diff));
		
		Arrays.sort(plus_diff, new Comparator<int[]>() {
			// comparator 익명 클래스 구현
			// compare() 메서드를 오버라이드하여 원하는 정렬 기준 명시하면됨
			
			@Override
			public int compare(int[] o1, int[] o2) {
				if(o1[2] != o2[2]) {
					return o2[2] - o1[2];
					// 세번째 숫자 기준 내림차순
				} else {
					return o2[1] - o1[1];
					// 세번째 숫자 같으면 두번째 숫자 기준 내림차순
				}
			}
		});
		
		System.out.println(Arrays.deepToString(plus_diff));
		
		int answer = 0;
		// 탐험할 수 있는 최대 던전 수
		
		for (int dunNum = 0 ; dunNum < plus_diff.length ; dunNum++) {
			if (k >= plus_diff[dunNum][0]) {
				k -= plus_diff[dunNum][1];
				answer++;
				// 내 현재 피로도가 최소 필요 피로도 이상이면
				// 그 던전의 소모 필요도만큼 내 현재 피로도 감소
				// 탐험한 던전 수는 1 증가 
			} else {
				continue;
				// 차이가 똑같아도 최소 필요 피로도에 따라
				// 다음 던전을 갈 수도 있고 안 갈 수도 있기 때문에
				// 만약 현재 피로도가 최소 필요 피로도보다 낮으면
				// 일단 다음 던전으로 넘어갈 것임
			}
		}
		
		System.out.println("탐험한 던전 수 : " + answer);
		
	}
}

이번에는 19개 중에서 4개 실패함.. 왜지.. 왜일까.. 어떤 반례를 놓친걸까.. 아니 프로그래머스는 테스트 케이스를 조금 더 다양하게 주지 않고!! 왜 내가 생각하게 만드는거야??

계속 오류 나서 못 함ㅠㅠㅠ

새로운 접근방법

완전탐색을 알게 되었다!! 이중 Brute-force 알고리즘으로 해보자
던전이 세개라면 던전 가는 방법은
123, 132
213, 231
312, 321
이렇게 6가지다 즉 3! 가지인거지
지금 던전이 아주 많이 주어지지는 않고 최대 8개만 주어진다.
그럼 컴퓨터는 최대 8! = 40320번만 계산 하면 된다는것!!!
그럼 저 줄세우기 순열을 for문으로 어떻게 나타낼지만 잘 생각해보자...

[두번째 풀이 -> 실패]

import java.util.Arrays;

public class Main {
	
	static int[][] dungeons = new int[][] {{80, 20}, {50, 40}, {30, 10}};
	// static int[][] dungeons = new int[][] {{100, 20}, {30, 20}, {70, 50}, {10, 5}, {50, 10}};
	// static int[][] dungeons = new int[][] {{50, 40}, {80, 30}, {30, 10}, {20, 10}};
	// 던전들의 최소 필요 피로도와 소모 피로도
	
	static boolean[] visited;
	// 방문 여부 확인
	
	static int k;
	// 현재 피로도
	
	static int answer;
	// 탐험할 수 있는 최대 던전 수
	
	static int[] dunNum = new int[dungeons.length]; 
	
	public static void main(String[] args) {
		
		for(int j = 0 ; j < dungeons.length ; j++) {
			k = 80;
			answer = 0;
			visited = new boolean[dungeons.length];
			visitDungeon(j);
			
			dunNum[j] = answer;
			
			System.out.println("탐험한 던전 수 : " + answer);
			System.out.println("====");
		}
		
		System.out.println("탐험한 던전 수 모음 : " + Arrays.toString(dunNum));
		
		Arrays.sort(dunNum);
		
		System.out.println("탐험한 던전 수 최댓값 : " + dunNum[dungeons.length-1]);
		
	}

	static void visitDungeon(int dungeonIndex) {
		
		if(k >= dungeons[dungeonIndex][0]) {
			// 현재 피로도가 최소 필요 피로도보다 크고 방문된 적이 없으면?
			
			visited[dungeonIndex] = true;
			// 그럼 방문 처리
			
			k -= dungeons[dungeonIndex][1];
			// 현재 피로도 - 소모 피로도
			
			answer++;
			// 던전 방문 수 1 증가
			
			System.out.printf("탐험한 던전 : %d번째 던전\n", dungeonIndex);
			System.out.printf("현재 피로도 : %d\n", k);
			System.out.printf("던전 방문 수 : %d번\n", answer);
			
			for (int i = 0 ; i < dungeons.length ; i++) {
				if(!visited[i]) {
					visitDungeon(i);
				}
			}
		}
	}

}

 

'Algorithm_Test' 카테고리의 다른 글

인프런 9-2. 회의실 배정 (자바)  (0) 2023.08.28
인프런 9-1. 씨름선수 (자바)  (2) 2023.08.28
프로그래머스. 구명보트 (자바)  (0) 2023.08.16
sw 2005. 파스칼의 삼각형 (자바)  (0) 2023.08.11
sw 1961. 숫자 배열 회전 (자바)  (0) 2023.08.11
'Algorithm_Test' Related Articles more