99클럽 코테 스터디 17일차 TIL 구명보트 feat. deque

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

프로그래머스

 

deque

 

 

1. 문제 및 접근

 

무인도에 갇힌 사람이 탈출하기 위해 구명보트 사용

구명 보트는 작아 2명밖에 못타고, 무게 제한도 있음

예를 들어, 사람들의 몸무게가 [70kg, 50kg, 80kg, 50kg]이고

구명보트의 무게 제한이 100kg이라면 2번째 사람과 4번째 사람은 같이 탈 수 있지만

1번째 사람과 3번째 사람의 무게의 합은 150kg이므로 구명보트의 무게 제한을 초과하여 같이 탈 수 없습니다.

 

최대한 적게 구명보트 사용해서 탈출

사람들의 몸무게를 담은 배열 people과 구명보트의 무게 제한 limit가 매개변수로 주어짐

 

투포인터로 ?  안되면 deque 써서 직관적으로 해결해보자

 

 

 

제한 사항

 

 

 

 

 

2. 풀이

 

private int solution(int[] people, int limit) {

        Arrays.sort(people);
        int count = 0;
        Deque<Integer> deque = new ArrayDeque<>();
        for (int i = 0; i < people.length; i++) {
            deque.add(people[i]);
        }
        while (!deque.isEmpty()) {


            int start = deque.getFirst();
            int end = deque.getLast();

            if (deque.size() == 1) {
                deque.removeFirst();


                return ++count;

            }

            if (start + end <= limit) {

                deque.removeFirst();
                deque.removeLast();
                count++;


            } else if (start + end > limit) {


                deque.removeLast();
                count++;
            }}





//        int start = 0;
//        int end = people.length - 1;
//        while (start != end) { // 이러면 그 수 하나를 세어주지 못한다..
//            if (end - start == 1) {
//                count++;
//                return count;
//            }
//            if (people[start] + people[end] > limit) {
//                end--;
//                count++;
//
//            }
//            else {
//                start++;
//                count++;}
//
//        }

        return count;


    }

 

전체풀이

 

 

2-1 투포인터 느낌(실패)

 

처음에 생각한 게 투포인터 느낌으로 서로를 움직여가며 같거나 작으면 빼주는 형태다

 

정렬되어 있는 상태라면, 가능할 것이라고 생각했으나 진짜 투포인터를 사용하는 게 아니라 해결될 것 같으면서

마지막 한 수가 남았을 때의 경우가 애매해져서 포기 (될 것 같은데..)

 

 

2-2 deque

 

발음은 항상 어렵다.. 덱, 데크라고 불리고

Duoble-Ended Queue의 줄임말이며,queue 양쪽에서 접근이 가능하다 ! (queue + stack 느낌)

 

덱은 양쪽 끝에서 삽입과 삭제가 모두 가능한 자료 구조의 한 형태

두 개의 포인터를 사용하여, 양쪽에서 삭제와 삽입을 발생시킬 수 있다.

 

큐와 스택을 합친 형태!

 

 

https://hbase.tistory.com/128

 

 

 

 

 

 

2-3 deque 선언

 

 

 

 

 

먼저 제일 중요한 정렬이다.

포인터를 이동하며 빼줄 생각이니까..

 

보통 deque는 ArrayDeque or LinkedList로 구현한다.

 

조금 무식해보이긴 하는데.. 정렬된 배열을 deque에 넣어준다.

 

 

2-4 deque 활용 1

 

 

 

내 생각엔 deque를 빼주면서 그 수를 세어줄껀데

while문으로 빌때까지 반복하고 deque의 장점인 앞 수를 getFirst(), 뒷 수 getLast()로 정해주고,

 

 

예외를 먼저 둔다.

deque의 size가 1이 되면 뽑아오면 같은 수 일텐데 내 조건문을 보면 first와 end의 합이 "limit보다 크냐 or 작거나 같냐" 르수

밑에 보면 알겠지만 남은 수가 limit의 절반의 수라면 두개를 뺴주게 되는데 그때 예외가 발생할 수 있다.

 

IF) Limit은 100이며, 50이 남았고, size가 1일 때 나는 앞 뒤수를 같이 빼주고 count 해주는 로직이라 size1인 deque에서 2번 빼는 에러가 발생할 수 있다.

 

그래서 1이 남으면 그냥 그 수 하나만 빼주고 끝!

 

 

2-5 deque 활용2

 

 

 

정해진 두 수를 limit과 비교해서 작거나 같음 or 크거나로 나뉜다.

 

1. start + end가 작거나 같은 경우

 

정렬된 배열에서 두 수가 같다면 둘다 한번에 배에 태울 수 있다는 뜻이기에 두 수를 빼주고

count++

 

(이렇게 짠 코드 때문에 size가 1이고, 그 수가 limit보다 작으면 size 1인 deque에서 두번 빼려고 해서 위 예외처리)

 

 

 

2. start + end가 클 경우

 

같은 수를 만들기 위해선 정렬된 배열에서 start 고정 후 end를 줄이면 다음 두 합은 limit안에 들어갈 수 있을 가능성이 있기에

뒷 수를 하나만 빼주고

 

(어차피 뒷 수로는 2명을 태울 수 없다  start가 현재 배열에서 가장 작은 수라)

 

count++

 

반복!

 

 

 

성공~

 

 

 

3. 마무리

 

 

 

내가 처음에 활용한 걸로 가능할 것 같긴 한데.. 직관적이지 않아서 deque로 풀어서 해결했다

 

deque도 써보고 싶기도 했고..!

 

사실 정렬하고 다시 메모리 써주는 게 불편하긴 하지만 어때~ 해결하면 됐지 모..

 

너무 스파게티식 코드라서 좀 더 다듬어야겠다ㅠㅠㅠ

 

 

효율성 테스트 실패할줄 알고 우울했는데 프로그래머스가 좀 유해서 별로인데 좀 좋네 ?..  나 너 좋아하냐 ?