📝 최소직사각형
문제 설명
최소직사각형
해결 방법
지갑을 가로, 세로로 자유롭게 수납할 수 있다.
각 지갑의 가로 길이(sizes[i][0]), 세로 길이(sizes[i][1]) 중 더 큰 값을 가로길이로 swap 함수를 이용해서 변경한다.
가로 길이 중 최댓값을 구해서 w에 넣고, 세로 길이 중 최댓값을 구해서 h에 넣고 곱한 값(w*h)을 return한다.
💻소스코드
#include <string>
#include <vector>
using namespace std;
int solution(vector<vector<int>> sizes) {
int answer = 0;
int w = 0, h = 0; // width, height
// 가로, 세로 길이 중 더 큰 값을 가로길이로 변경.
for (int i = 0; i < sizes.size(); i++){
if (sizes[i][0] < sizes[i][1])
swap(sizes[i][0], sizes[i][1]);
}
for (int i = 0; i < sizes.size(); i++){
if (w < sizes[i][0])
w = sizes[i][0];
if (h < sizes[i][1])
h = sizes[i][1];
}
answer = w * h;
return answer;
}# 관점의 전환
📝 폰켓몬
문제 설명
폰켓몬
해결 방법
문제가 길긴 하지만, 주어진 배열 크기의 1/2 보다 작거나 같은 선에서 중복되지 않는 요소의 최대 개수를 구하는 문제로 해석했다.
1. nums 배열의 요소들을 오름차순 정렬한다.
2. nums 배열의 중복되는 요소들을 제거한다.
3. 변경된 nums 배열의 크기보다 작으면서(&&) 원래 nums 배열의 1/2 보다 작거나 같은 범위에서 요소들의 개수를 구하면 가장 많은 종류의 폰켓몬 개수를 return 하게 된다.
💻소스코드
#include <vector>
#include <algorithm>
using namespace std;
int solution(vector<int> nums)
{
int answer = 0;
int size = nums.size(); // 변경 되기 이전의 nums 배열 크기
sort(nums.begin(), nums.end()); // nums 배열의 요소들을 오름차순 정렬
nums.erase(unique(nums.begin(), nums.end()), nums.end()); // nums 배열의 중복되는 요소들 모두 제거
int i = 0;
// 선택할 수 있는 폰켓몬 종류 개수의 최댓값 구하기
while ((i < size / 2) && (i < nums.size())){
i++;
answer++;
}
return answer;
}# unique 함수의 적용
📝 예산
문제 설명
예산
해결 방법
정해진 예산으로 최대한 많은 부서를 지원을 해줘야 한다. 소요되는 예산이 적은 부서들부터 지원하면 최대한 많은 부서들을 지원해줄 수 있을 것이다. 그리디 알고리즘 문제인 것 같다.부서별로 신청한 금액이 들어있는 d 배열을 오름차순으로 정렬한다. budget이 부서들을 다 지원해주고도 남을 수 있지만 딱 맞을 수도 있고 부족할 수도 있다. sum 변수에 각 부서마다 필요한 예산들을 적은 부서들부터 더한다. 더할때마다 지원하는 부서 수를 세기 위해 카운팅해준다. sum 이 budget을 초과하게 된다면 break; 를 통해 반복문을 빠져나온다.
💻소스코드
#include <iostream>
#include <stdio.h>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
int solution(vector<int> d, int budget) {
int answer = 0;
int sum = 0;
sort(d.begin(), d.end());
for (int i = 0; i < d.size(); i++){
sum += d[i];
if (sum > budget)
break;
answer++;
}
return answer;
}# 문제를 해석하여 간단하게 만드는 방법
📝 2016년
문제 설명
2016년
해결 방법
문제에서 2016년 1월 1일이 금요일이라고 알려줬다. 이를 이용해서 1월 2일은 토요일이고, 1월 3일은 일요일이고 . . . 반복하다보면 2016년 12월 31일이 무슨 요일인지 알 수 있을 것이다.
day_cnt를 선언해서 입력받은 날짜수를 계산해서 할당해준다. 이 때 months 배열을 선언해서 각 월별 날짜수로 초기화해줬다. days 배열에 각각의 요일들로 초기화하고, (day_cnt - 1) % 7 로 인덱싱을 하게 되면 해당하는 날짜의 요일을 구할 수 있다.
💻소스코드
#include <string>
#include <vector>
using namespace std;
string solution(int a, int b) {
string answer = "";
string days[7] = { "FRI", "SAT", "SUN", "MON", "TUE", "WED", "THU" };
int months[12] = { 31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
int day_cnt = 0;
for (int i = 0; i < a - 1; i++){
day_cnt += months[i];
}
day_cnt += b;
answer = days[(day_cnt - 1) % 7];
return answer;
}# const 배열로 묶어서 처리하는 방법
📝 최대공약수와 최소공배수
문제 설명
- 두 수를 입력받아 두 수의 최대공약수와 최소공배수를 반환하는 함수, solution을 완성해 보세요.
- 배열의 맨 앞에 최대공약수, 그다음 최소공배수를 넣어 반환하면 됩니다.
- 예를 들어 두 수 3, 12의 최대공약수는 3, 최소공배수는 12이므로 solution(3, 12)는
[3, 12]를 반환해야 합니다.
제한 사항
- 두 수는 1이상 1000000이하의 자연수입니다.
해결 방법
최대공약수 구하는 알고리즘인 유클리드 호제법을 사용했다. 최소공배수는 (구하고자 하는 두 수의 곱 / 최대공약수)이다.
💻소스코드
#include <string>
#include <vector>
using namespace std;
vector<int> solution(int n, int m) {
vector<int> answer;
int i = 1;
int gcd = 1, lcm; // greatest common divisor, least common multiple
// O(n)
//while (i <= n && i <= m){
// if ((n % i == 0) && (m % i == 0))
// gcd = i;
// i++;
//}
// 유클리드 호제법 O(log n)
int a = n, b = m;
if (n > m){
while (1){
int r = a % b; // n > m
if (r == 0){
gcd = b;
break;
}
a = b;
b = r;
}
} else {
while (1){
int r = b % a; // n < m
if (r == 0){
gcd = a;
break;
}
b = a;
a = r;
}
}
answer.push_back(gcd);
answer.push_back((n*m)/gcd);
return answer;
}# 최소공배수 구하는 방법과 유클리드 호제법
📝 3진법 뒤집기
문제 설명
3진법 뒤집기
해결 방법
- 숫자 n을 k진법으로 변환하는 방법
1) n을 k로 나눈 나머지를 k진법으로 변환한 숫자의 오른쪽부터 채워감
2) n을 k로 나눈 몫을 n에 저장
3) n이 0이 될 때까지 1~2를 반복벡터 num을 선언해서 n을 3으로 나눴을 때 나머지를 num에 push_back하고 n을 3으로 나눠주는 과정을 반복하면, 3진법이 반전된 상태로 num 배열에 들어가게 된다. 이를 다시 10진법으로 나타내기 위해 3의 제곱 수를 나타낼 pow 변수와 num 배열의 맨 뒤에서부터 인덱싱할 idx 변수를 선언하고 초기화한다. answer += num[idx] * pow, pow 는 3씩 곱해주고 idx는 하나씩 줄여주면서 idx가 -1이 될 때까지 반복하면 3진법을 10진법으로 변환한 결과를 얻을 수 있다.
💻소스코드
#include <string>
#include <vector>
using namespace std;
int solution(int n) {
int answer = 0;
vector<int> num;
while (n){
num.push_back(n % 3);
n /= 3;
}
int idx = num.size() - 1;
int pow = 1;
while (idx > -1){
answer += num[idx] * pow;
idx--;
pow *= 3;
}
return answer;
}# 진법 변환 및 계산 방법
📝 하샤드 수
문제 설명
- 양의 정수 x가 하샤드 수이려면 x의 자릿수의 합으로 x가 나누어져야 합니다.
- 예를 들어 18의 자릿수 합은 1+8=9이고, 18은 9로 나누어 떨어지므로 18은 하샤드 수입니다.
- 자연수 x를 입력받아 x가 하샤드 수인지 아닌지 검사하는 함수, solution을 완성해주세요.
해결 방법
문제 설명에서 나왔듯이 우선 sum 변수를 선언해서 양의 정수 x의 모든 자릿수의 합을 구한다
x를 sum으로 나눴을 때 나누어 떨어지지 않으면 false를 반환한다
💻소스코드
#include <string>
#include <vector>
using namespace std;
bool solution(int x) {
bool answer = true;
int sum = 0; // 자릿수의 합
int result = x; // x값 변경 방지
// add all digits of x
while (result > 0){
sum += result % 10;
result /= 10;
}
if ((x % sum) != 0)
answer = false;
return answer;
}# 각각의 자릿수를 다루는 방법
