[그리디] 프로그래머스 "구명보트"
2021. 6. 27. 13:51ㆍ알고리즘 문제분석
https://programmers.co.kr/learn/courses/30/lessons/42885
수행시간 : 30분 / 난이도 : 레벨 2
얼핏보면 일반적인 투포인터 문제라고 생각할 수 있다. 하지만 처음 로직을 짤 때, 문제에서 요구하는 그리디적인 로직이 필요하다.
우선, 소팅을 통해 가장 작은값부터 큰값까지 정렬을 한다.
처음 로직을 짰을때는, 정렬 후 가장 작은값부터 비교해가면서 i번째 + (i+1)번째 의 값이 limit를 초과하는 순간 pivot을 만들어 계산하는 로직을 생각했는데, 테스트케이스에서 반절이나 틀리는 것을 보고,
가장 작은 값부터 비교하는 것이 아닌 가장 작은 값과 가장 큰 값을 엮으면서 진행햐야됨을 깨닭았다.
그럼 가장 작은 값과 가장 큰값을 더해가면서 limit과 비교해주는 가장 대표적인 알고리즘인 "투포인터" 기법을 이용하면 된다. 다만, while문을 break 해줄때, min 값이 max 값보다 커질때 말고도, min값과 max값이 동일해지는 순간. 그 순간에 남은 인덱스는 people[max] = people[min] 값 하나이므로 answer+1 을 해준 상태로 while문을 탈출하면 구현 할 수 있다.
#include <string>
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int solution(vector<int> people, int limit) {
int answer = 0;
sort(people.begin(), people.end());
int min_val = 0;
int max_val = people.size()-1;
//cout << max_val;
while(min_val < max_val){
int sum = people[min_val] + people[max_val];
if(sum > limit){
max_val--;
}
else{
max_val--;
min_val++;
}
answer++;
if(max_val == min_val){
answer++;
break;
}
}
return answer;
}
'알고리즘 문제분석' 카테고리의 다른 글
[그래프&구현] 백준 2251번 물통 (0) | 2022.01.03 |
---|---|
[스택&구현] 프로그래머스 "짝지어 제거하기" (0) | 2021.06.26 |
[BFS] 프로그래머스 "카카오프렌즈 컬러링북" (0) | 2021.06.26 |
[백트래킹] 백준 1987 알파벳 (0) | 2021.06.24 |
[투포인터] 백준 3273 두 수의 합 (0) | 2021.06.24 |