99클럽 코테 스터디 17일차 TIL 구명보트 feat. deque
https://school.programmers.co.kr/learn/courses/30/lessons/42885
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
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 느낌)
덱은 양쪽 끝에서 삽입과 삭제가 모두 가능한 자료 구조의 한 형태
두 개의 포인터를 사용하여, 양쪽에서 삭제와 삽입을 발생시킬 수 있다.
큐와 스택을 합친 형태!
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도 써보고 싶기도 했고..!
사실 정렬하고 다시 메모리 써주는 게 불편하긴 하지만 어때~ 해결하면 됐지 모..
너무 스파게티식 코드라서 좀 더 다듬어야겠다ㅠㅠㅠ
효율성 테스트 실패할줄 알고 우울했는데 프로그래머스가 좀 유해서 별로인데 좀 좋네 ?.. 나 너 좋아하냐 ?