아래 모든 문제들은 프로그래머스에서 제공 되는 문제를 이용하였습니다, 감사합니다.
- 모두 풀었음.
1. 구명보트
문제 설명
무인도에 갇힌 사람들을 구명보트를 이용하여 구출하려고 합니다. 구명보트는 작아서 한 번에 최대 2명씩 밖에 탈 수 없고, 무게 제한도 있습니다.
예를 들어, 사람들의 몸무게가 [70kg, 50kg, 80kg, 50kg]이고 구명보트의 무게 제한이 100kg이라면 2번째 사람과 4번째 사람은 같이 탈 수 있지만 1번째 사람과 3번째 사람의 무게의 합은 150kg이므로 구명보트의 무게 제한을 초과하여 같이 탈 수 없습니다.
구명보트를 최대한 적게 사용하여 모든 사람을 구출하려고 합니다.
사람들의 몸무게를 담은 배열 people과 구명보트의 무게 제한 limit가 매개변수로 주어질 때, 모든 사람을 구출하기 위해 필요한 구명보트 개수의 최솟값을 return 하도록 solution 함수를 작성해주세요.
제한사항
- 무인도에 갇힌 사람은 1명 이상 50,000명 이하입니다.
- 각 사람의 몸무게는 40kg 이상 240kg 이하입니다.
- 구명보트의 무게 제한은 40kg 이상 240kg 이하입니다.
- 구명보트의 무게 제한은 항상 사람들의 몸무게 중 최댓값보다 크게 주어지므로 사람들을 구출할 수 없는 경우는 없습니다.
입출력 예
풀이
#include <string>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
bool compare (int a, int b)
{
return a > b;
}
int solution(vector<int> people, int limit) {
int answer = 0;
int aa = 0;
sort(people.begin(), people.end(), compare);
for (int i = 0; i < people.size(); i++)
{
if (people[i] == -1)
continue;
else if ((people[i] + people[(people.size() - aa - 1)]) <= limit)
{
people[(people.size() - aa - 1)] = -1;
aa++;
}
answer += 1;
}
return answer;
}설명
- 이문제의 포인트는 최대 두명만 보트를 탈수있다.
- 두명만 보트를 탈 수 있을떄 최대한 효율적으로 보트를 타는 방법은,
- 남은 사람중 몸무게가 가장 많이 나가는 사람을 가장 적게 나가는 사람과 태웠을때 탈수있으면 태워보내는것이다.
- 그리고 태워 보낸 사람은 표시할려고 -1로 바꾸어 주었다.
2. 위장
문제 설명
스파이들은 매일 다른 옷을 조합하여 입어 자신을 위장합니다.
예를 들어 스파이가 가진 옷이 아래와 같고 오늘 스파이가 동그란 안경, 긴 코트, 파란색 티셔츠를 입었다면 다음날은 청바지를 추가로 입거나 동그란 안경 대신 검정 선글라스를 착용하거나 해야 합니다.
스파이가 가진 의상들이 담긴 2차원 배열 clothes가 주어질 때 서로 다른 옷의 조합의 수를 return 하도록 solution 함수를 작성해주세요.
제한사항
- clothes의 각 행은 [의상의 이름, 의상의 종류]로 이루어져 있습니다.
- 스파이가 가진 의상의 수는 1개 이상 30개 이하입니다.
- 같은 이름을 가진 의상은 존재하지 않습니다.
- clothes의 모든 원소는 문자열로 이루어져 있습니다.
- 모든 문자열의 길이는 1 이상 20 이하인 자연수이고 알파벳 소문자 또는 '_' 로만 이루어져 있습니다.
- 스파이는 하루에 최소 한 개의 의상은 입습니다.
입출력 예
풀이
#include <string>
#include <vector>
#include <iostream>
#include <map>
using namespace std;
int solution(vector<vector<string>> clothes) {
int answer = 1;
map<string, int> um;
// um[au[1]] = 0;
for (auto au : clothes)
{
um[au[1]]++;
// um[au[1]] = um[au[1]] + 1;
}
for (auto au : um)
{
answer *= au.second + 1;
}
return answer - 1;
}설명
- 카테고리 별로 카운트를 해서 비교를 해야하는 문제였다.
- 맵을 써서 헤시 테이블을 생성하고, 카테고리별로 카운터해서 쉽게 해결해 주었다.
3. 카펫
문제 설명
Leo는 카펫을 사러 갔다가 아래 그림과 같이 중앙에는 노란색으로 칠해져 있고 테두리 1줄은 갈색으로 칠해져 있는 격자 모양 카펫을 봤습니다.
Leo는 집으로 돌아와서 아까 본 카펫의 노란색과 갈색으로 색칠된 격자의 개수는 기억했지만, 전체 카펫의 크기는 기억하지 못했습니다.
Leo가 본 카펫에서 갈색 격자의 수 brown, 노란색 격자의 수 yellow가 매개변수로 주어질 때 카펫의 가로, 세로 크기를 순서대로 배열에 담아 return 하도록 solution 함수를 작성해주세요.
제한사항
- 갈색 격자의 수 brown은 8 이상 5,000 이하인 자연수입니다.
- 노란색 격자의 수 yellow는 1 이상 2,000,000 이하인 자연수입니다.
- 카펫의 가로 길이는 세로 길이와 같거나, 세로 길이보다 깁니다.
입출력 예
풀이
#include <string>
#include <vector>
#include <iostream>
using namespace std;
vector<int> solution(int brown, int yellow) {
vector<int> answer;
vector<int> value;
for (int i = 1; i * i <= yellow; i++)
{
if(yellow % i == 0)
value.push_back(i);
}
for (int j = 0; j < value.size(); j++)
{
if (brown == (value[j] * 2) + 2 * ((yellow / value[j]) + 2))
{
answer.push_back((yellow / value[j]) + 2);
answer.push_back(value[j] + 2);
break;
}
}
return answer;
}설명
- 그림을 보면, 노란색 직사각형 가로의 길이 +2를 한 값이 갈색 가로의 길이이다.
- 세로의 길이또한 +2를 하면 같다.
- yellow의 1부터 i*i까지 나누어 떨어지는 값들을 구해서 가로 세로를 구하고, brown값과 일치하게 나오는 값을 구해 반환해주었다.
