[Java] 프로그래머스 : 구명보트(Greedy Algorithm)

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

코딩테스트 연습 - 구명보트

 

탐욕법을 통해 큰 수부터 제거하는 방식으로 코드 작성

 

 

 

문제

 ·  몸무게를 합쳤을때 limit내인 경우 answer++해준다. 

 

 · 8번 줄 : 배열을 내림차순 정렬하기 위해서 int를 integer타입으로 변형(int타입으론 내림차순 정렬이 안됨)

 · 9번 줄 : 내림차순 정렬

 · 첫번째 if문(13번 줄) 

    ① i번째와 j번째를 더했을때 limit보다 작으면 answer을 하나 추가해주고 

    ② i번째와 j번째는 0으로 만들어준다

    ③ 마지막으로 break를 사용함으로써 두번째 for문을 나가 첫번째 for문의 i를 돌려줌으로 다음 값을 찾는다

 · 두번째 if문(23번 줄)

    ① i번째와 j번째 합이 100이상일때 i번째가 0이 아닐 시 answer++해준다 

    ② 그리고 i번째를 0으로 바꿔준다

 

내가 작성한 코드(다른 코드들에 비해 길다....)

import java.util.*;

class Solution {
    public int solution(int[] people, int limit) {
        int i, j;
        int answer = 0;

        Integer[] peopl = Arrays.stream(people).boxed().toArray(Integer[]::new);
        Arrays.sort(peopl, Collections.reverseOrder());

        for(i = 0; i < peopl.length; i++) {
            for(j = i + 1; j < peopl.length; j++) {
                if(limit >= peopl[i] + peopl[j]) {
                    answer++;

                    peopl[i] = 0;
                    peopl[j] = 0;

                    break;
                }
            }		
            
                if(peopl[i] != 0) {
                    answer++;
                }				
                peopl[i] = 0;											
        }		
        return answer;		
    }
}

 

 

다른 블로그들 코드

class Solution {
    public int solution(int[] people, int limit) {
        int answer = 0;
        Arrays.sort(people);
        int index = 0;
        
        for (int i = people.length - 1; i >= index; i--) {
            if (people[i] + people[index] <= limit) {
                index++;
                answer++;
            }
            else {
                answer++;
            }
        }
        
        return answer;
    }
}