섬 연결하기 - 프로그래머스 LV3 JAVA

프로그래머스

 

해당 문제는 프로그래머스에서 탐욕법(Greedy) 카테고리 안에 있는 문제이다.

탐욕 알고리즘은 정리해 두었던 내용이다 ( 링크 )

 

---

 

 

문제 풀이

---

 

아직 익숙치않은 Comparator 인터페이스로 이중배열인 costs의 값을 cost순으로 오름차순 했다는 것 정도다

Comparator의 사용법은 간단히 정리 해 두었다 ( 링크 )

 

알고리즘 활용에 미숙해서인지 모르겠지만

내 생각엔 탐욕법이나 기타 알고리즘들을 사용해서 푼 것 같지는 않다

물론 이게 어떤 알고리즘이라고 한다면 공부를 더 깊게 해야 할 것 같다

 

1. 섬의 갯수는 n개이니 섬을 연결하는 다리는 n-1개가 있을 것이라 생각했다

2. 다리를 n-1만큼 놓았을 때 최소비용을 구해야 했기 때문에 문제에서 주어진 costs배열을 costs순으로 오름차순 했다

3. (0)ㅡ>(1)이면 0번 섬에서 1번 섬으로 다리를 놓는 것이기 때문에 1을 0으로 초기화시켜주었고

    초기화 시키기 전에 0번배열의 costs값은 가져간 채로 시작해야 하기 때문에 미리 조건을 지정해주었다

 

보통 프로그래머스 LV3짜리 문제를 푸는 데 몇시간 ~ 며칠을 붙잡고 풀 정도의 실력인데

이번 문제는 유독 LV3중에서 술술 잘 풀렸던 것 같다

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

class Solution {
    int solution(int n, int[][] costs) {		
		
		Arrays.sort(costs, new Comparator<int[]>() {

			@Override
			public int compare(int[] o1, int[] o2) {
				return o1[2]-o2[2];
			}
		});
		
		int tmp = 0;
		int length = 0;
		int answer = 0;		
	
		for(int i=0; i<costs.length; i++) {
			if(length==n-1) break;
			
			if(costs[i][0]!=costs[i][1]) {
				answer += costs[i][2];
			}
			
			int cnt = 0;
			tmp=costs[i][1];
			costs[i][1]=costs[i][0];
			
			while(true) {
				if(costs[cnt][0]==tmp) costs[cnt][0]=costs[i][0];
				if(costs[cnt][1]==tmp) costs[cnt][1]=costs[i][0];
				cnt++;
				
				if(cnt==costs.length) break;			
			}			
			
		}			
		return answer;
	}
}