뚝딱뚝딱

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

💡 문제

FOOD_PRODUCT와 FOOD_ORDER 테이블에서 생산일자가 2022년 5월인 식품들의 식품 ID, 식품 이름, 총매출을 조회하는 SQL문을 작성해주세요. 이때 결과는 총매출을 기준으로 내림차순 정렬해주시고 총매출이 같다면 식품 ID를 기준으로 오름차순 정렬해주세요.

✅ 문제 풀이

• FOOD_PRODUCT와 FOOD_ORDER 테이블을 JOIN한다.

FOOD_PRODUCT A JOIN FOOD_ORDER B
ON A.PRODUCT_ID = B.PRODUCT_ID

• 두 테이블의 공통 속성인 PRODUCT_ID를 기준으로 JOIN한다.

• 생산일자가 2022년 5월인 식품을 추린다.

WHERE PRODUCE_DATE>='2022-05-01' AND PRODUCE_DATE<='2022-05-31'

• 제품 당 총매출을 구해야 하기 때문에, 제품 ID를 기준으로 그룹화한다.

GROUP BY A.PRODUCT_ID

• 조회할 정보를 가져온다.

SELECT A.PRODUCT_ID, A.PRODUCT_NAME, SUM(A.PRICE*B.AMOUNT) AS TOTAL_SALES

• 현재 PRODUCT_ID로 그룹화 되어 있기 때문에, SUM을 통해 같은 그룹 내 상품들의 매출을 더하여 총매출을 구할 수 있다.

• 조건에 따라 정렬한다.

ORDER BY TOTAL_SALES DESC, PRODUCT_ID ASC;

• 총매출을 기준으로 내림차순 정렬, 식품 ID를 기준으로 오름차순 정렬 해준다.

✏ 코드 전문

SELECT A.PRODUCT_ID, A.PRODUCT_NAME, SUM(A.PRICE*B.AMOUNT) AS TOTAL_SALES
FROM FOOD_PRODUCT A JOIN FOOD_ORDER B
ON A.PRODUCT_ID = B.PRODUCT_ID
WHERE PRODUCE_DATE>='2022-05-01' AND PRODUCE_DATE<='2022-05-31'
GROUP BY A.PRODUCT_ID
ORDER BY TOTAL_SALES DESC, PRODUCT_ID ASC;

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

💡 문제

CAR_RENTAL_COMPANY_CAR 테이블과 CAR_RENTAL_COMPANY_RENTAL_HISTORY 테이블과 CAR_RENTAL_COMPANY_DISCOUNT_PLAN 테이블에서 자동차 종류가 '세단' 또는 'SUV' 인 자동차 중 2022년 11월 1일부터 2022년 11월 30일까지 대여 가능하고 30일간의 대여 금액이 50만원 이상 200만원 미만인 자동차에 대해서 자동차 ID, 자동차 종류, 대여 금액(컬럼명: FEE) 리스트를 출력하는 SQL문을 작성해주세요. 결과는 대여 금액을 기준으로 내림차순 정렬하고, 대여 금액이 같은 경우 자동차 종류를 기준으로 오름차순 정렬, 자동차 종류까지 같은 경우 자동차 ID를 기준으로 내림차순 정렬해주세요.

문제의 조건

• CAR_TYPE 이 '세단' 또는 'SUV'
• 2022-11-01 부터 2022-11-30 까지 대여가능
• 30일간의 대여금액 >=500000 AND <2000000
• 위를 만족하는 자동차의 CAR_ID, CAR_TYPE, FEE 출력
• 단, 대여금액 기준 내림차순, 자동차 종류 기준 오름차순, 자동차 ID기준 내림차순 정렬

✅ 문제 풀이

• 대여 가능 여부를 판단한다.
  HISTORY 테이블에서 START_DATE와 END_DATE가 있다. 11월 달에 대여한 적이 있는지를 보려면, START_DATE는 11월 30일 이전이어야 하고, END_DATE는 11월 1일 이후여야 한다. SQL문으로 나타내면 다음과 같다.

CAR_RENTAL_COMPANY_RENTAL_HISTORY C 
    WHERE C.START_DATE<='2022-11-30' AND C.END_DATE>='2022-11-01'

• 그럼 이 날짜에 RENTAL한 적이 있는 자동차는 제외하면 된다. 
• 이렇게 생각할 수도 있다. 11월 달에 대여한 적 없는 자동차만 고르면 되는 거 아닌가? 로직을 어떻게 짜냐에 다르긴 하지만, 단순하게 각 레코드 마다 11월달에 대여한 적 없는 경우를 고른다면, 11월에도 대여했었지만 다른 날짜에도 대여했던 동일한 자동차도 포함되어 버릴 수 있기 때문에, 11월에 대여한 자동차의 ID 자체를 제외하는 식으로 접근하였다. 이는 NOT IN 연산자를 통해 제외할 수 있다.

A.CAR_ID NOT IN (
    SELECT DISTINCT C.CAR_ID 
    FROM CAR_RENTAL_COMPANY_RENTAL_HISTORY C 
    WHERE C.START_DATE<='2022-11-30' AND C.END_DATE>='2022-11-01'
)

• 첫 WHERE 조건을 하나 완성하였다.

• 30일간의 대여금액을 계산하기 위해 테이블을 조인한다.
  이를 구하기 위해서는 CAR_RENTAL_COMPANY_CAR 테이블과 CAR_RENTAL_COMPANY_DISCOUNT_PLAN 테이블을 INNER 조인해주어야 한다. 그래서 각 자동차마다 CAR_TYPE에 따라 DISCOUNT 정보를 갖도록 할것이다.

FROM CAR_RENTAL_COMPANY_CAR A JOIN CAR_RENTAL_COMPANY_DISCOUNT_PLAN B
ON A.CAR_TYPE=B.CAR_TYPE

• 두 테이블의 공통 속성인 CAR_TYPE을 기준으로 JOIN한다.

• 조건에 따라 WHERE 절에 조건을 추가로 작성해준다.

AND A.CAR_TYPE IN('SUV', '세단') 
AND B.DURATION_TYPE = '30일 이상' 
AND A.DAILY_FEE*30*(1-B.DISCOUNT_RATE*0.01)>=500000 
AND A.DAILY_FEE*30*(1-B.DISCOUNT_RATE*0.01)<2000000

• CAR_TYPE이 'SUV', '세단' 중에 해당하면 조회한다. IN 연산자를 사용하였다.
• 조인 후에는 각 자동차 마다 CAR_TYPE에 따라 3개의 DISCOUNT_RATE 정보가 엮여있을 것이다. 이 중에서 DURATION_TYPE이 '30일 이상' 인것 만 사용하도록 한다.
• 대여금액은 조건에 해당하는 자동차의 DAILY_FEE*30*할인률 이기 때문에, 이 값이 50만원 이상 200만원 미만인 것만 추리도록 한다.

• 필요한 정보를 출력한다.

SELECT A.CAR_ID, A.CAR_TYPE, CAST(A.DAILY_FEE*30*(1-B.DISCOUNT_RATE*0.01)AS SIGNED) AS FEE

• 위에 조건에 부합하는 자동차의 CAR_ID, CAR_TYPE, FEE를 조회하도록 한다.
• 이때 FEE의 경우 *0.01 때문에 소수점 이하 두자리 형태로 출력되게 되는데, 조건의 주의사항에서 FEE의 경우 정수 형태로 출력하도록 되어있기 때문에, CAST 연산자를 사용하여 정수형태로 출력하도록 한다. AS SIGNED는 소수점을 없애면서 부호는 그대로 유지한다는 것이다.

• 조회결과를 주어진 정렬 조건에 맞도록 설정하기

ORDER BY FEE DESC, CAR_TYPE ASC, CAR_ID DESC;

• 마지막에 ORDER BY 문을 통해서 FEE를 기준으로 내림차순, CAR_TYPE을 기준으로 오름차순, CAR_ID를 기준으로 내림차순 정렬하도록 해준다.

✏ 코드 전문

SELECT A.CAR_ID, A.CAR_TYPE, CAST(A.DAILY_FEE*30*(1-B.DISCOUNT_RATE*0.01)AS SIGNED) AS FEE 
FROM CAR_RENTAL_COMPANY_CAR A JOIN CAR_RENTAL_COMPANY_DISCOUNT_PLAN B
ON A.CAR_TYPE=B.CAR_TYPE
WHERE A.CAR_ID NOT IN (
    SELECT DISTINCT C.CAR_ID 
    FROM CAR_RENTAL_COMPANY_RENTAL_HISTORY C 
    WHERE C.START_DATE<='2022-11-30' AND C.END_DATE>='2022-11-01'
)
AND A.CAR_TYPE IN('SUV', '세단') 
AND B.DURATION_TYPE = '30일 이상' 
AND A.DAILY_FEE*30*(1-B.DISCOUNT_RATE*0.01)>=500000 
AND A.DAILY_FEE*30*(1-B.DISCOUNT_RATE*0.01)<2000000
ORDER BY FEE DESC, CAR_TYPE ASC, CAR_ID DESC;

https://www.acmicpc.net/problem/1149

💡 RGB거리

[문제]
RGB거리에는 집이 N개 있다. 거리는 선분으로 나타낼 수 있고, 1번 집부터 N번 집이 순서대로 있다.집은 빨강, 초록, 파랑 중 하나의 색으로 칠해야 한다. 각각의 집을 빨강, 초록, 파랑으로 칠하는 비용이 주어졌을 때, 아래 규칙을 만족하면서 모든 집을 칠하는 비용의 최솟값을 구해보자.1번 집의 색은 2번 집의 색과 같지 않아야 한다.N번 집의 색은 N-1번 집의 색과 같지 않아야 한다.i(2 ≤ i ≤ N-1)번 집의 색은 i-1번, i+1번 집의 색과 같지 않아야 한다.

[입력]
첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 같은 자연수이다.

[출력]
첫째 줄에 모든 집을 칠하는 비용의 최솟값을 출력한다.

✅ 문제 풀이

이 문제는 전형적인 DP 문제이다.

집은 R,G,B 세 색상 중 하나로 칠할 수 있는데, 인접한 집끼리는 색이 겹쳐서는 안된다.

그렇게 칠했을 때 모든 집을 칭하는 최소 비용을 구한다.

일단 입력으로 주어지는 각 집당 페인트 비용을 저장하기 위해서 2차원 배열을 사용해보자.

문제에서 주어진 예시를 사용할 것이다.

행은 집의 번호, 열은 각 집의 R,G,B 비용이다.

첫번째 집까지 칠했을 때는 첫번째 집에서 고른 비용이 저장되는 것이고, 두번째 집까지 칠했을 때는 첫번째 집까지 쓰인 비용+두번째 집에서 고른 비용으로 값이 정해진다. 따라서 다음과 같은 점화식을 따른다.

d[i]=d[i-1]+a[i]

그런데, 비용을 최소로 한다고 해서 모든 집에서 가장 작은 비용을 선택해버린다면, 위 예에 따르면 26, 49, 13이 가장 최소가 되어버리고, 모두 빨간색으로만 칠하게 되어버린다. 이는 조건을 위배하게 된다.

따라서 이전 집에서 어떤 색을 칠했는지에 따라서 이번 집에 칠할 수 있는 색이 2개로 추려져야 한다.

그러므로 이전 집을 R로 칠했을때, G로 칠했을때, B로 칠했을때를 모두 계산하고 나서, 최종 집까지 칠했을때 세 값중 최소값이 답이 될 수 있다.

이때 현재 집(i번 집)에 R을 칠하고자 한다면 이전집(i-1)이 G또는 B가 칠해졌어야 하고, 이 둘 중 최소 비용에 현재 집의 R 비용을 더한 값이 d[i][0]이 될 수 있다.

이를 점화식으로 나타내면 다음과 같다.

d[i][0] = min(d[i - 1][1], d[i - 1][2]) + a[i][0]; 
d[i][1] = min(d[i - 1][0], d[i - 1][2]) + a[i][1];
d[i][2] = min(d[i - 1][0], d[i - 1][1]) + a[i][2];

점화식에 따르면 위 표와 같이 정리될 수 있고, 이는 i번째 집까지 칠했을 때의 비용을 나타낸다.

따라서 위 예시의 답은 3번째 집까지 칠했을 때의 비용 96,172,146 중에 최소값인 96이 되는 것이다.

min(min(d[t][0], d[t][1]), d[t][2])

이 식을 통해서 답을 구할 수 있다. (t는 마지막 집의 번호이다)

✏ 코드 전문

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int t;
	cin >> t;

	vector<vector<int>> d(t + 1, vector<int>(3, 0));
	vector<vector<int>> a(t + 1, vector<int>(3, 0));

	for (int i = 1; i <= t; i++) {
		cin >> a[i][0] >> a[i][1] >> a[i][2];
		d[i][0] = min(d[i - 1][1], d[i - 1][2]) + a[i][0];
		d[i][1] = min(d[i - 1][0], d[i - 1][2]) + a[i][1];
		d[i][2] = min(d[i - 1][0], d[i - 1][1]) + a[i][2];
	}

	int answer = min(min(d[t][0], d[t][1]), d[t][2]);

	cout << answer;

	return 0;
}

https://swexpertacademy.com/main/code/problem/problemDetail.do?problemLevel=3&contestProbId=AV139KOaABgCFAYh&categoryId=AV139KOaABgCFAYh&categoryType=CODE&problemTitle=&orderBy=INQUERY_COUNT&selectCodeLang=ALL&select-1=3&pageSize=10&pageIndex=1

✅ 문제 풀이

• 상자의 높이를 입력 받은 벡터에서, 가장 큰 값은 1 줄이고, 가장 작은 값은 1 늘리는 식으로 평탄화할 수 있다.
• 한번 덤프를 수행하고 날 때마다, 최소의 상자 높이와 최대의 상자 높이를 갖는 벡터의 위치가 달라진다.
• 이를 쉽게 찾기 위해서 매 덤프마다 벡터를 오름차순 정렬하고 시작하기로 했다.
• 그렇게 하면 벡터의 0번은 항상 가장 작고, 99번은 항상 가장 크기 때문이다.
• 따라서 정렬 후, 벡터의 99번째와 0번째의 차이가 1 또는 0이라면 더이상 상자를 옮기지 않아도 되기 때문에, break문으로 덤프를 멈추도록 한다. 그렇지 않다면, 평탄화가 이루어 져야 하므로 99번째 상자는 하나 줄이고, 0번째 상자는 하나 높여준다.
• 그럼 다음 덤프에서 다시 오름차순 정렬되고, 위의 과정을 반복하면 된다.
• 덤프를 모두 수행하고 나서는, 최종적으로 한번더 오름차순 정렬해준 뒤, 99번째에서 0번째 값을 뺀 값을 출력하도록 하면 된다.

=> 굉장히 naive한 방법이지만, c++ 기준 시간은 10초까지 인정되므로 pass되는 코드이다.

✏ 코드 전문

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	for (int i = 1; i <= 10; i++) {
		int n;
		cin >> n;
		vector<int> arr(100);
		for (int j = 0; j < 100; j++) {
			cin >> arr[j];
		}
		
		int answer;
		for (int j = 0; j < n; j++) {
			sort(arr.begin(), arr.end());
			if (((arr[99] - arr[0]) == 1) || ((arr[99] - arr[0]) == 0)) {
				break;
			}
			else {
				arr[99]--;
				arr[0]++;
			}
		}
		sort(arr.begin(), arr.end());
		answer = arr[99] - arr[0];
		cout << "#" << i << " " << answer << "\n";
	}
	return 0;
}

https://swexpertacademy.com/main/code/problem/problemDetail.do?problemLevel=3&contestProbId=AV134DPqAA8CFAYh&categoryId=AV134DPqAA8CFAYh&categoryType=CODE&problemTitle=&orderBy=INQUERY_COUNT&selectCodeLang=ALL&select-1=3&pageSize=10&pageIndex=1

난이도 D3 ⭐⭐⭐

✅ 문제 풀이

• 처음 두 건물과, 마지막 두 건물은 항상 높이가 0이다.
• 따라서 세번째 건물부터 기준으로하여, 앞에 두 건물과 뒤에 두 건물 보다 큰지 확인한다.
• 앞 뒤로 총 4개의 건물보다 크다면, 기준이 되는 현재 건물의 높이에서 4개 건물 중 가장 큰 건물의 높이를 뺀 값이 뷰를 확보할 수 있는 세대 수가 된다.
• 이를 모든 건물에 대해서 반복하며 세대 수를 누적해가면, 각 테스트케이스의 답이 된다.

✏ 코드 전문

#include<iostream>
#include<vector>
#include<algorithm>
 
using namespace std;
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("input.txt", "r", stdin);
    for (int i = 1; i <= 10; i++) {
        int n;
        cin >> n;
        vector<int> arr;
        for (int j = 0; j < n; j++) {
            int temp;
            cin >> temp;
            arr.push_back(temp);
        }
 
        int count = 0;
        for (int j = 2; j < n-2; j++) {
            int cent = arr[j];
            if (arr[j - 2] < cent && arr[j - 1] < cent && arr[j + 1] < cent && arr[j + 2] < cent) {
                int m1 = max(arr[j - 2], arr[j - 1]);
                int m2 = max(arr[j + 1], arr[j + 2]);
                count += cent - (max(m1, m2));
            }
        }
 
        cout << "#" << i << " " << count << "\n";
    }
    return 0;
}

https://www.acmicpc.net/problem/1764

💡 듣보잡

김진영이 듣도 못한 사람의 명단과, 보도 못한 사람의 명단이 주어질 때, 듣도 보도 못한 사람의 명단을 구하는 프로그램을 작성하시오.

[입력]
첫째 줄에 듣도 못한 사람의 수 N, 보도 못한 사람의 수 M이 주어진다. 이어서 둘째 줄부터 N개의 줄에 걸쳐 듣도 못한 사람의 이름과, N+2째 줄부터 보도 못한 사람의 이름이 순서대로 주어진다. 이름은 띄어쓰기 없이 알파벳 소문자로만 이루어지며, 그 길이는 20 이하이다. N, M은 500,000 이하의 자연수이다.듣도 못한 사람의 명단에는 중복되는 이름이 없으며, 보도 못한 사람의 명단도 마찬가지이다.

[출력]
듣보잡의 수와 그 명단을 사전순으로 출력한다.

✅ 문제 풀이

• set 자료구조에 입력받은 이름들을 저장할건데, 듣도 못한 사람들을 입력받고 저장해둔다.
• 그리고 보도 못한 사람들을 입력받을 때마다, set의 find함수를 사용해서, 보도 못한 사람이 있는지 확인하고, 있으면 vector에 저장한다.
• 마지막에 vector의 크기를 출력하고, 사람을 사전 순으로 출력해야 하므로 sort함수를 통해 오름차순 정렬한다.
• 그리고 정렬된 vector의 내용을 모두 출력한다.

✏ 코드 전문

#include<iostream>
#include<string>
#include<vector>
#include<set>
#include<algorithm>

using namespace std;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int n, m;
	cin >> n >> m;

	set<string> arr;
	for (int i = 0; i < n; i++) {
		string str;
		cin >> str;
		arr.insert(str);
	}

	vector<string> answer;

	for (int i = 0; i < m; i++) {
		string str;
		cin >> str;
		
		auto it = arr.find(str);
		if (it != arr.end()) answer.push_back(str);
	}

	cout << answer.size() << "\n";
	
	sort(answer.begin(), answer.end());

	for (int i = 0; i < answer.size(); i++) {
		cout << answer[i] << "\n";
	}

	return 0;
}