뚝딱뚝딱

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://www.acmicpc.net/problem/1026

💡 보물

옛날 옛적에 수학이 항상 큰 골칫거리였던 나라가 있었다. 이 나라의 국왕 김지민은 다음과 같은 문제를 내고 큰 상금을 걸었다.
길이가 N인 정수 배열 A와 B가 있다. 다음과 같이 함수 S를 정의하자.
S = A[0] × B[0] + ... + A[N-1] × B[N-1]
S의 값을 가장 작게 만들기 위해 A의 수를 재배열하자. 단, B에 있는 수는 재배열하면 안 된다.
S의 최솟값을 출력하는 프로그램을 작성하시오.

첫째 줄에 N이 주어진다. 둘째 줄에는 A에 있는 N개의 수가 순서대로 주어지고, 셋째 줄에는 B에 있는 수가 순서대로 주어진다. N은 50보다 작거나 같은 자연수이고, A와 B의 각 원소는 100보다 작거나 같은 음이 아닌 정수이다.

첫째 줄에 S의 최솟값을 출력한다.

✅ 문제 풀이

크기가 각각 N인 A와 B배열을 입력받은 뒤, B는 그대로 두고, A만 재정렬 하여 A와 B의 원소를 각각 곱해서 최소의 값이 되도록 하는것이다.

여기서 구하고자 하는 것은 그때의 최소값이다.

따라서 A와 B가 어떻게 정렬이 되어 있던 간에, 결국 최소 값을 구하기 위해서는 한쪽은 가장 큰 값, 다른 한쪽은 가장 작은 값을 곱한 것이 최소가 된다.

따라서 A를 오름차순 정렬하고, B를 내림차순 정렬한 후에 각각의 원소끼리 차례로 곱한 값들을 더해주면 최소값이 나오게 된다.

B는 그대로 두되, A를 "재정렬" 하라는 말에 너무 초점을 맞추게 되면, 생각이 많아질 수 있으나, 목적인 최소값을 생각하면 쉽게 해결하는 문제이다.

☑ 코드 전문

#include<iostream>
#include<algorithm>

using namespace std;

bool compare(int a, int b) {
	return a > b;
}

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

	int N;
	cin >> N;

	int *A = new int[N];
	int *B = new int[N];
	
	for (int i = 0; i < N; i++) {
		cin >> A[i];
	}
	for (int i = 0; i < N; i++) {
		cin >> B[i];
	}

	sort(A, A + N);//오름차순
	sort(B, B + N, compare);//내림차순

	int answer = 0;
	for (int i = 0; i < N; i++) {
		answer += A[i] * B[i];
	}
	
	cout << answer;

	return 0;

}

소프티어 lv2 "금고 털이" 문제 풀이 중 pair vector와 sort사용이 익숙치 않아 정리하는 글이다.

pair vector

vector<pair<int, int>> v;

vector에서는 한 요소에 두가지 값을 함께 넣으려면, 위와 같이 pair로 묶어서 정의해 주어야 한다.

"금고 털이" 문제에서 첫번째 int 요소에는 금속의 무게를 , 두번째 int 요소에는 금속의 가치를 저장해주었다.

각각의 값에 접근하려면, v.first, v.second로 접근할 수 있다.

sort

algorithm에서 정의한 정렬 함수 sort이다.

기본적으로 오름차순 정렬이고, pair vector의 경우 첫번째 값을 기준으로 오름차순 한다.

sort(v.begin(), v.end());

이렇게 하면 vector v를 첫번째 값인 금속 무게에 대해서 오름차순 정렬해준다.

그런데 나는 금속의 가치인 두번째 값에 대해서 내림차순 정렬하고 싶었다.

그래서 sort함수에, 따로 정의한 비교함수를 인자로 넣어, 이 기준으로 정렬해 주세요~라고 요청했다.

bool compare(const pair<int, int> &a, const pair<int, int> &b){
	return a.second>b.second;
}

 위와 같은 compare 함수를 정의해 주었다.

내가 헷갈렸던 점은, 부등호의 방향이다. 

처음에는 b쪽에 크다고 했는데, 이유는 정렬할 때 뒤에 있던게 컸었다..라고 생각한 것이다. 아무튼 나의 착각이고..

내림차순이 앞이 큰거니까, 먼저 위치한 a가 클 때 true로 정의해 주는 것이다.

반대로 오름차순이면? b쪽으로 부등호가 향해야 할 것이다.

이렇게 해서 기본 of 기본인 pair vector와 sort함수에 대해 정리해보았다.

다음에는 버벅거리지 않고 바로 구현하길~

https://softeer.ai/practice/6288

💡 금고 털이

• 무게가 W인 배낭, N개의 금속 종류가 있다.
• 최대의 가치를 갖도록 금속을 담는데, 무게 W를 넘지 않아야 한다.
• 금속은 1g당 가치를 갖는다.
• 따라서 높은 가치를 갖는 순서대로 배낭에 담아야 한다.
• 금속의 무게와 가치를 갖는 pair 벡터를 이용하였다.
• pair 벡터에서 두번째 요소인 가치에 따라 내림차순 정렬 하기 위해, 비교함수인 compare를 정의해주었다.
• 내림차순 정렬 후, 각 금속에 대해서, 무게가 현재의 W를 넘지 않으면, 그 무게만큼 넣고, 그렇지 않으면 W만큼 떼어다 넣기로 한다. 넣은 무게만큼 W에서 차감하는 방식이다.

전체 코드는 아래와 같다.

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

using namespace std;

bool compare(const pair<int, int> &a, const pair<int, int> &b){
  return a.second>b.second;
}//두번째 요소를 기준으로 내림차순 하도록..

int main(int argc, char** argv)
{
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  
  int W,N;
  cin>>W>>N;

  vector<pair<int, int>> v(N);
  for(int i=0; i<N; i++){
    cin>>v[i].first>>v[i].second;
  }

  sort(v.begin(), v.end(), compare);//두번째 요소를 통해 compare 하도록 비교함수 정의
  
  int value=0;
  for(int i=0; i<N; i++){
    if(W==0) break;
    int used=(v[i].first<=W)?v[i].first:W;
    value+=used*v[i].second;
    W-=used;
  }
  
  cout<<value;
  
   return 0;
}

pair 벡터 정렬만 할 줄 알면 되므로, 아주 쉽다.

해결한 방식을 사용하기 전 생각 했던 접근 방식은 다음과 같았다.

1. 맨 앞 수만 가지고 정렬 한다음, 가장 큰 수를 포함하는 숫자를 answer에 저장한다
-> 이렇게 할 경우 가장 큰수에 해당하는 숫자들에 대해서는 언제까지 비교할 것인가? 이게 문제

2. 숫자를 앞 글자부터 버킷에 넣어가는 식으로 비교한다.

-> 그 개수를 모르기 때문에 언제까지 비교? 어디에 넣을것인가? 마땅히 생각나는 자료구조가 없어서 실패

여러가지로 짱구를 돌려봤지만, 모두 복잡한 풀이가 이어질 것으로 예상되어서(2시간 붙잡음..) 힌트를 확인했다.

사실 문제에서는 힌트를 줬다.

"문자열로 출력하세요."

우리가 숫자 그 자체로 두고 비교를 하려니 해결되지 않았던 것이다.

지난 포스팅에서도, 문자 형태의 숫자를 sort하면 숫자 자체가 아닌, 숫자 자체가 사전식으로 큰지를 판단해서 정렬함을 배웠다.(이래서 복습이 중요하다!!!!!!)

1. 그러므로 먼저 배열을 string형태로 변환하는 과정이 필요하다.
2. 하지만 여기서 끝이 아니다. string의 정렬에서는 30,3 과 같은 경우 더 긴 쪽을 크다고 판단한다.
   이런 경우를 대비해서 sort함수의 정렬 기준을 바꾸어 주어야 한다.
   두 문자열을 받았을 때 문자열을 303으로 붙였을 때와 330으로 붙였을 때 어느 쪽이 더 큰가? 
   후자가 더 크다.
   따라서 그렇게 정렬해주면 자동으로 숫자가 큰쪽으로 정렬이 된다.
   이를 위해서 Arrays.sort함수 인자안에서 람다식을 이용해 기준을 설정해 주었다.
3. Arrays.sort(nums, (o1, o2)->(o2+o1).compareTo(o1+o2));
   두번째 인자가 람다식을 통해 기준을 설정해준 것인데, 인자로 받은 string o1, o2에 대해서 o2+o1 순으로 더했을 때의 값과 o1+o2순으로 더했을 때의 값을 비교한 결과가 양수이면 정렬을 결과가 큰 쪽으로 하겠다는 의미이다.
4. 위의 간단한 람다식을 통해 정렬을 했으면, 이제 정렬 결과에 대해 예외를 생각해야 한다.
   만약 숫자 배열에 0밖에 없었다면?
   당연히 결과는 0이어야 한다. 000....은 0이기 때문이다.
   따라서 이런경우에는 "0"을 바로 return 하도록 하였다.
5. 0이 아닌 경우에는 nums에 정렬된 대로 순서대로 string을 붙여서 출력하면 되는데, 이때 string에 + 형식 말고, StringBuilder 클래스를 사용하여 붙였다.
   answer라는 이름으로 해당 객체를 생성해 준 다음에 nums에 있는 값들을 차근차근 append하여 넣어준뒤, 마지막에 return할 때는 answer.toString()으로 반환해주었다.

💡 StringBuilder?

• Java에서 문자열을 효율적으로 생성 및 조작하기 위한 클래스이다.
• + 연산자를 이용해서 반복적으로 연산하는 것보다 append()함수를 통해 문자열을 연결하는 것이 성능을 높일 수 있다.
• 문자열을 연결하거나 수정하는 작업을 수행할 때 많은 문자열 객체가 생성되는 것을 방지하기 때문에, 성능이 향상되고 메모리 사용량을 줄일 수 있다.
• StringBuilder 클래스는 문자열을 연결하고 수정하는 역할을 하는 것이기 때문에, 연결 작업을 끝낸 후 문자열을 반환하려면 클래스 이름 자체가 아니라, 반환 함수인 toString()함수를 이용해서 반환해야 한다.

최종 코드는 다음과 같다.

import java.util.Arrays;

class Solution {
    public String solution(int[] numbers) {
        
        String[] nums = new String[numbers.length];
        
        for(int i=0; i<numbers.length; i++){
            nums[i] = Integer.toString(numbers[i]);
        }
        
        Arrays.sort(nums, (o1, o2) -> (o2 + o1).compareTo(o1 + o2));
        
        if(nums[0].equals("0")) return "0";
        
        StringBuilder answer = new StringBuilder();
        
        for(int i=0; i<nums.length; i++){
                answer.append(nums[i]);
        }
    
        
        //문자로 표현된 숫자의 경우.. 숫자가 더 크냐가 아니라, 사전식으로 어떤게 더 앞에 있냐를 따지니까.. 문자로 바꿔서 정렬하면 바로 해결됨.
        
        
        return answer.toString();
    }
}

<자바 문법>

**sort함수는 java.util.Arrays에 있다.

**문자열 비교는 .equals("")로 한다.

**int->string으로 변환하는 함수는 Integer.toString(변수)

***해시알고리즘을 사용한 java 코드가 궁금하다면 아래 블로그를 참고하세요***

2023.10.18 - [CO-TE/challenge] - [프로그래머스] java / c++ LV2 전화번호 목록 / 해시알고리즘, SORT 풀이 (2)

이 문제는 처음에 c++로는 2중 for문을 돌면서, 배열에서 첫번째 전화번호를 기준으로 시작하여, 다른 전화번호들 중 기준이 되는 전화번호보다 길이가 작으면 continue로 건너 뛰고, 그렇지 않으면, substr을 사용해 기준 전화번호 길이만큼 잘라서 비교한 후, 문자열이 동일하면 false를 반환하는 방식으로 접근했다.

이렇게 하면 테스트 케이스는 다 맞지만, 효율성에서 떨어지게 된다. 당연히 무식하게 2중 for문으로 일일이 확인하기 때문에 복잡도가 O(n^2)일 수 밖에 없다.

문제의 카테고리에서 주어진 방식대로 해시 알고리즘을 사용해서 풀면 효율성 문제를 해결할 수 있지만, 사실 해시 알고리즘을 어떻게 사용하는지 몰랐기 때문에, 다른 사람의 코드를 보고 참고하여 먼저 정렬을 이용해 더 쉽게 풀이하였다.

  c++ / sort 함수와 1중 for문으로 풀기 

string 타입의 배열 phone_book을 <algorithm> 헤더에 있는 기본 정렬 함수인 sort()를 통해 정렬한다.

숫자로 표현된 문자열의 경우 사전식으로, 각 문자열의 첫번째 값부터 비교한다. 

첫번째 값들이 다 동일하면 두번째 값을 비교한다.

즉 숫자 그 자체가 큰지가 아니라, 앞에 문자열부터 각 숫자가 작은 것 부터 정렬하는 방식이다

예) "12" "14" "112" 가 있으면, 112, 12, 14 순으로 정렬 된다.

첫번째 1은 모두 같고, 두번째 값이 1,2,4순이기 때문이다.

따라서 이렇게 정렬을 먼저 해 놓으면, 자연스럽게 접두사가 될 확률이 높은 문자열이 앞에 위치하게 되고, 해당 접두사를 가지는 문자열은 무조건 그 문자열의 다음에 정렬될 것이기 때문에, 이 방법은 1중 for문으로도 인접한 문자열에 대해 한번씩만 비교하면 된다. 

해당 코드는 아래와 같다.

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

bool solution(vector<string> phone_book) {
    bool answer = true;
    
    sort(phone_book.begin(), phone_book.end());
    
    for(int i=0; i<phone_book.size()-1; i++){
        string s = phone_book[i+1].substr(0, phone_book[i].size());
        if(phone_book[i]==s) {
            answer = false;
            break;
        }
    }
  
    return answer;
}

• sort함수에 배열의 첫번째 요소와, 배열의 마지막 요소를 인자로 넣어주면, 자동으로 정렬된다.
• 1중 for문을 통하여 string 문자열 s에는 현재 접근하는 phone_book의 전화번호 바로 다음에 위치한 전화번호를, 접두사 길이 만큼 잘라 (substr을 사용) 저장한다. 이때 c++에서는 substr(시작 인덱스, 자르고 싶은 만큼의 문자열 크기) 이므로 이에 유의한다. 
• 그래서 현재 접두사 후보의 값과 s가 일치한다면 false를 반환하도록 answer에 설정해준다.

사실상 해시 알고리즘으로 푸는 의도의 문제이긴 하지만, 실제 코테에서는 이 방법을 꼭 사용하라는 명시가 없기 때문에, 위와 같이 효율적인 코드가 생각이 난다면 당연히 사용해도 좋다.

그러나 해시 알고리즘을 이번 기회에 알고 넘어 가기 위해 java를 이용해서 한번 더 풀어보았다.

2탄에서 이어서...