[프로그래머스] 구명보트

프로그래머스 level 2 구명보트

 

시간초과로 시간이 거의 두 시간 가까이 걸렸던 것 같다...

정확성은 통과되기 어렵지 않았는데 효율성을 통과하기 어려웠다.

효율적인 코드를 짜는 것을 많이 연습해야할 듯 하다.

 

 

먼저 무게 오름차순으로 배열을 정렬하고,

제일 가벼운 사람과 제일 무거운 사람을 더해서 limit 내인지 보고

limit 내라면 보트 1개를 사용한다.

limit 를 초과한다면 제일 무거운 사람을 보트 1개에 태우고 제일 가벼운 사람과 제일 무거운 사람 다음으로 무거운 사람을 더하여 비교한다.

import java.util.Arrays;
class Solution {
	public static int solution(int[] people, int limit) {
    	int N = people.length;
		
		Arrays.sort(people);		
		int count = N;
		int answer = 0;
		int front = 0, end = N-1;
		while(count > 0) {
			if(people[front]+ people[end] > limit) {
				answer++;
				count--;
				end--;
			}
			else {
				answer++;
				count-=2;
				front++;
				end--;
			}
		}
    	
        return answer;
    }
}

 

---

아래 코드들은 정확성은 100%이지만 시간초과로 효율성테스트 0%... 

코드1은 이중포문으로 시간이 오래걸리고

코드2도 이중while과 list remove작업으로 시간이 오래걸린다.

 

시행착오 코드1

package programmers.level2;

public class 구명보트 {
	static boolean[] selected;
	public static int solution(int[] people, int limit) {
    	int N = people.length;
		selected = new boolean[N];
		
		int count = 0;
		int answer = 0;
		for (int i = answer; i < N; i++) {
			if(count == N) break;
			if(selected[i]) continue;
			count++;
			if(count == N) {	// 이걸로 그나마 시간 줄여질까 했는데 별로 영향 x
				selected[i] = true;
				answer++;
				break;
			}
			if(people[i] == limit) { // 이것도 시간 그나마 줄이려고 했는데 별로 영향 x
				selected[i] = true;
				answer++;
				continue;
			}
			int max = 0, idx = -1;
			int sum;
			for (int j = i+1; j < N; j++) {
				if(selected[j]) continue;
				sum = people[i]+people[j];
				if(sum <= limit && max < sum) {
					max = sum;
					idx = j;
				}
			}
			
			selected[i] = true;
			if(idx != -1) {
				selected[idx] = true;
				count++;
			}
			answer++;
		}
    	
        return answer;
    }
	
	public static void main(String[] args) {
		System.out.println(solution(new int[] {100, 80, 40, 20}, 100));
	}
}

 

시행착오 코드2

package programmers.level2;

import java.util.ArrayList;
import java.util.List;

public class 구명보트 {
	public static int solution(int[] people, int limit) {
    	int N = people.length;
		List<Integer> list = new ArrayList<>();
		for (int i = 0; i < N; i++) {
			list.add(i);
		}
		
		int answer = 0;
		while(list.size() > 0) {
			int i = 0;
			int max = 0, idx = -1;
			int sum;
			if(list.size() > 1) {
				for (int j = 1; j < list.size(); j++) {
					sum = people[list.get(i)]+people[list.get(j)];
					if(sum <= limit && max < sum) {
						max = sum;
						idx = j;
					}
				}
				if(idx != -1) {
					list.remove(idx);
				}
			}
			list.remove(i);
			answer++;
		}
    	
        return answer;
    }
	
	public static void main(String[] args) {
		System.out.println(solution(new int[] {100, 80, 40, 20}, 100));
	}
}