뚝딱뚝딱

💡 문제)
USED_GOODS_BOARD와 USED_GOODS_USER 테이블에서 완료된 중고 거래의 총금액이 70만 원 이상인 사람의 회원 ID, 닉네임, 총거래금액을 조회하는 SQL문을 작성해주세요. 결과는 총거래금액을 기준으로 오름차순 정렬해주세요.

1. 회원 ID, 닉네임, 총거래금액을 조회
   SELECT B.USER_ID, B.NICKNAME, SUM(A.PRICE) AS TOTAL_SALES
   문제에서 주어진 쿼리 결과대로 총거래금액의 출력 시 이름을 TOTAL_SALES로 바꾸어준다.
   
   
2. USED_GOODS_BOARD와 USED_GOODS_USER 테이블에서
   테이블 두개가 연결되어야 함을 알 수 있다. 테이블을 보면 USER_ID에 대해서 중복된 것을 알 수 있다 (컬럼이름은 각 테이블에서 다르지만, 결국은 USER의 아이디를 가리키고 있음)
   따라서 두 테이블을 유저 아이디에 대한 조건으로 INNER JOIN시켜야 한다.
   그래야 각 상품 목록에 대해서 유저의 정보를 함께 출력하는 테이블을 얻을 수 있기 때문이다.
   FROM USED_GOODS_BOARD A JOIN USED_GOODS_USER B ON A.WRITER_ID=B.USER_ID
   
   
3. 완료된 중고 거래의
   위의 2번까지를 통해 각 상품에 대한 유저 정보까지 합친 테이블을 얻었으니, 이제 그 중에서도 완료된 거래에 대해서만 추려야 한다.
   그러러면 WHERE 절을 이용해서 STATUS가 DONE인 것만을 가져올 수 있다.
   WHERE A.STATUS="DONE"
   
   
4. 총금액이 70만 원 이상인 사람의
   위의 과정까지는 각 상품에 대해서 개별적으로 조회되기 때문에, 한 사람의 전체 거래 내역을 고려하기 위해서는 사람의 단위로 GROUP을 지어야 한다.
   따라서 GROUP BY 절을 통해 USER_ID 별로 그룹화 시킨다.
   그러면 거래가 완료된 상품의 거래 주인의 아이디, 이름, 총거래금액이 출력되는데, 이 중에서도 조건에서 총거래금액이 70만원 이상인 사람의 것만 출력하라고 되어 있다.
   그러므로 GROUP BY 절에 HAVING을 추가해서 그 그룹 중 총거래금액이 70만원이상인 것만 출력하도록 해준다.
   GROUP BY B.USER_ID HAVING TOTAL_SALES>=700000
   
   
5. 결과는 총거래금액을 기준으로 오름차순 정렬해주세요.
   (나는 이 단계를 빼먹고 채점 결과가 자꾸 틀렸다고 떠서 시간을 낭비했다. 꼭 정렬 조건을 확인하도록 하자)
   이제 조건에 만족하는 결과는 다 출력했다.
   마지막 조건인 정렬을 해준다.
   ORDER BY절을 통해 해줄 수 있다.
   ORDER BY TOTAL_SALES;

위 다섯 단계를 거치면서 하나하나씩 접근하면 매우 쉬운 문제이다!

조인, WHERE절, GROUP BY절, ORDER BY절이 다 쓰인 문제라서, 순서를 한번 정리하고 넘어가자

SELECT > FROM > JOIN-ON > WHERE > GROUP BY - HAVING > ORDER BY

FOOD_PRODUCT 테이블에서 가격이 제일 비싼 식품의 식품 ID, 식품 이름, 식품 코드, 식품분류, 식품 가격을 조회하는 SQL문을 작성해주세요.

WHERE문 안에서는 PRICE=MAX(PRICE) 이런식으로 접근할 수 없다. 따라서 MAX(PRICE)의 값을 가져오려면 서브쿼리를 이용해서 MAX(PRICE) 값을 가져올 수 있도록 해야한다.

SELECT MAX(PRICE) FROM FOOD_PRODUCT를 서브쿼리로 해서 MAX(PRICE)값을 가져오고 그 값이 PRICE와 같으면 해당 정보를 조회하도록 한다.

최종 코드는 아래와 같다.

SELECT * FROM FOOD_PRODUCT WHERE PRICE = (SELECT MAX(PRICE) FROM FOOD_PRODUCT);

= 대신에 IN을 써도 무방하다.

**

다른 사람들의 풀이를 보다가 PRICE에 대해 내림차순 정렬 후 LIMIT 1 을 사용해서 조회한 풀이를 발견하였다.

그런데, 내 생각에는, LIMIT 1을 할 시 , 동일하게 MAX PRICE를 갖는 레코드에 대해서는 하나의 레코드만 출력되는 예외가 발생할 수 있기 때문에, 서브쿼리를 이용한 풀이가 더 맞다고 본다. 

***정렬을 이용한 c++ 코드가 필요하다면 아래의 블로그를 참고하세요***

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

이번에는 해시 알고리즘을 이용한 java 풀이법을 살펴보겠다.

💡 ''해시 알고리즘''??

해시(hash)는 임의의 데이터를 고정된 길이의 숫자나 문자열로 변환하는 과정이다.

HashMap
- 해시를 사용하는 자료 구조의 일종이다.
- HashMap은 키-값 쌍을 저장하고, 이러한 키-값 쌍에 대한 빠른 검색 및 검색을 지원합니다
- 문자열을 가지고, 해당 문자열이 HashMap에 있는지 바로바로 찾아주기 때문에 O(1)의 복잡도를 갖는다.

HashMap을 활용해서 HashMap에 전화번호 목록들을 키-값 쌍으로 저장하는 과정이 필요하다.

HashMap에 있는 값들은 이제 HashMap에서 지원하는 찾기 함수를 통해서 바로바로 찾아 낼 수 있다.

 java / HashMap 사용 

1. 먼저 HashMap을 Map<>을 통해서 생성하자.

• HashMap의 경우 java.util.HashMap에 정의되어 있으므로 import해준다.
• Map의 경우 java.util.Map에 정의되어 있으므로 import해준다.

import java.util.HashMap;
import java.util.Map;

• HashMap은 Map 인터페이스를 구현한 클래스로, Map<>의 객체에 HashMap의 생성자로 생성되도록 할 수 있다.
• 전화번호의 경우 String문자열로 되어 있기 때문에, <String, Integer>를 키-값 쌍으로 갖는 Map을 생성한다.
• 사실상 Integer(값)는 쓸 일이 없고, Map을 활용하기 위한 것이므로, 인덱스를 넣어주겠다.

Map<String, Integer> map = new HashMap<>();

2. HashMap에 phone_book에 있는 값들을 키로, 그리고 인덱스를 값으로 넣어준다.

for(int i=0; i<phone_book.length; i++){
            map.put(phone_book[i], i);
        }

• 여기서 주의할 점..phone_book의 배열 크기는 .length로 얻어 올 수 있다. (c++의 size()와 헷갈리지 말자)
• map에 요소를 넣을 때는 put을 사용하고, 지정해준 키-값 쌍을 인자로 넣어주면 된다.

3. 2중 for문을 통해서 phone_book에 있는 전화번호 각각의 접두어가 HashMap에 있는지를 확인한다.

for(int i=0; i<phone_book.length; i++){
            for(int j=0; j<phone_book[i].length(); j++){
                if(map.containsKey(phone_book[i].substring(0,j))){
                    return false;
                }

• 현재 가리키는 전화번호의 0부터 j번 까지의 문자열이 HashMap의 키를 통해 검색한 결과에 있으면, j번까지의 접두어로 존재하는 전화번호가 있다는 의미이기 때문에, false를 반환하도록 한다.
• 이때 사용하는 map의 함수가 containsKey()로, 검색하고자 하는 값을 인자로 넣어주면 된다.
• 자바에서 String의 substring()함수는 자르고자 하는 문자열의 시작 인덱스와 끝인덱스를 인자로 넣어주고, 만약 인자를 하나만 적는다면 해당 시작부터 끝까지 잘라준다.
• string의 쓰임같은 경우 c++에서와 헷갈리지 않도록 주의한다!!!
• 참고로 문자열의 길이를 반환할 때는 .length()이다! 

이렇게 해시를 이용하면 바로바로 문자열을 map의 함수를 통해 검색할 수 있으므로 효율성에서 높아진다.

전체코드는 아래와 같다.

//해시로 풀이
import java.util.HashMap;
import java.util.Map;

class Solution {
    public boolean solution(String[] phone_book) {
        boolean answer = true;
        
        Map<String, Integer> map = new HashMap<>();
        
        for(int i=0; i<phone_book.length; i++){
            map.put(phone_book[i], i);
        }
        
        for(int i=0; i<phone_book.length; i++){
            for(int j=0; j<phone_book[i].length(); j++){
                if(map.containsKey(phone_book[i].substring(0,j))){
                    return false;
                }
                    //substring은 start index부터 end index까지
                    //java에서는 string size가 아니고 배열 크기는 length, 배열 안에서 문자열                        길이는 length() 
            }
        }
        
        
        return answer;
    }
}

***해시알고리즘을 사용한 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탄에서 이어서...

이 문제는 원래 JOIN 카테고리에 있는 문제이지만, JOIN으로 풀었을 때, 두 테이블간의 관계가 중복이 되는 문제와 둘 중 한 테이블이 비어 있을 경우에는 ON에 대한 부분에서 성립이 안되는 것 같아서, 간단하게 UNION ALL로 해결 했다.

다른 사람들의 JOIN 풀이 방법을 보았는데, 실제로는 TOTAL_ORDER의 SUM값이 중복되어 계산되는 경우들이 있어서 아직 JOIN으로의 해결은 완벽히 하지 못했다.

UNION ALL로 해결한 간단한 방법에 대해 소개한다.

UNION ALL

SQL의 집합 연산자 중 하나인데, 중복 레코드도 허용한다는 특징이 있다.

예시 테이블을 보면, 어찌되었던, FIRST_HALF에 있는 값도, JULY에 있는 값도 모두 더해져야 할 대상이다.

따라서 두 테이블의 중복 여부와 상관없이, 두 테이블의 모든 값을 한 테이블로 합쳐주어야 한다.

두 테이블의 컬럼들은 모두 동일하다. 그래서 더 쉽게 사용할 수 있다.

두 테이블을 합칠 때는 SELECT * FROM FIRST_HALF UNION ALL SELECT * FROM JULY 로 합칠 수 있다.

이렇게 합쳐진 하나의 테이블에서 필요한 컬럼들을 가져올 것인데, 조회를 하기 위해 필요한 FLAVOR와 SUM(TOTAL_ORDER)을 가져올 것이고, 이때 SUM을 FLAVOR별로 합쳐야 하기 때문에 GROUP BY FLAVOR를 해준다.

여기 까지 하면

SELECT FLAVOR, SUM(TOTAL_ORDER) AS TOTAL_ORDER_SUM 

FROM (

(SELECT * FROM FIRST_HALF UNION ALL SELECT * FROM JULY)

)AS A 

GROUP BY FLAVOR

이다.

중간 중간 AS로써 컬럼의 이름과 조회 테이블의 이름을 지정해주었다.

이제 FLAVOR와 각 FLAVOR마다의 총 ORDER로 구성된 테이블은 구해졌다.

이 테이블에서 최종으로 조회해야 할 상위 FLAVOR 3개를 출력하면 끝이다.

상위 FLAVOR는 ORDER합의 큰 것부터 이므로, 합을 기준으로 내림차순 해준다.

SELECT FLAVOR 

FROM (

SELECT FLAVOR, SUM(TOTAL_ORDER) AS TOTAL_ORDER_SUM 

FROM (

(SELECT * FROM FIRST_HALF) UNION ALL (SELECT * FROM JULY)

) AS A

GROUP BY FLAVOR

) AS B

ORDER BY TOTAL_ORDER_SUM DESC

그리고 상위 3개만 구하면 끝이므로, MYSQL에서 지원하는 LIMIT 을 통해 상위 3개만 조회한다.

SELECT FLAVOR 

FROM (

SELECT FLAVOR, SUM(TOTAL_ORDER) AS TOTAL_ORDER_SUM 

FROM (

(SELECT * FROM FIRST_HALF) UNION ALL (SELECT * FROM JULY)

) AS A

GROUP BY FLAVOR

) AS B

ORDER BY TOTAL_ORDER_SUM DESC

LIMIT 3;

최종 코드를 한번 더 첨부한다.

SELECT FLAVOR 
FROM (
SELECT FLAVOR, SUM(TOTAL_ORDER) AS TOTAL_ORDER_SUM 
FROM (
(SELECT * FROM FIRST_HALF) UNION ALL (SELECT * FROM JULY)
) AS A
GROUP BY FLAVOR
) AS B
ORDER BY TOTAL_ORDER_SUM DESC
LIMIT 3;

JOIN방법을 찾는 다면 다음 편에 이어서 작성하겠다

DFS/BFS 알고리즘의 대표적인 문제 "타겟 넘버"의 풀이방법이다.

그 전에 DFS/BFS의 개념을 정리하자면,

그래프와 트리와 같은 자료 구조에서 사용되는 탐색 알고리즘이다.

문제에 따라서 각각의 접근방식을 달리 사용할 수 있다.

💡 DFS (깊이 우선 탐색)

• 깊이 우선 탐색은 한 분기를 끝까지 탐색한 후 다음 분기로 넘어가는 방식의 탐색 알고리즘이다.
• 시작 노드에서 출발하여 가능한 한 깊이 들어가면서 탐색한다.
• 주로 재귀 함수를 사용하여 구현하거나 스택(Stack)을 이용한다.
• 특정 경로를 탐색하다가 더 이상 진행할 수 없는 상황에 도달하면 이전 단계로 돌아와 다른 경로를 탐색한다.
• DFS는 그래프에서 사이클을 찾거나 깊이에 관한 문제를 해결하는 데 유용하다.

예시) 미로를 탐색할 때 한 방향으로 직진하다가 막히면 되돌아가서 다른 방향으로 계속 진행하는 방식이다.

💡 BFS (너비 우선 탐색)

• 너비 우선 탐색은 시작 노드에서부터 가까운 노드부터 차례대로 탐색하는 방식의 탐색 알고리즘이다.
• 큐(Queue) 자료 구조를 사용하여 구현한다.
• 주로 최단 경로를 찾는 문제에 사용되며, 모든 가까운 노드를 우선 탐색하여 최단 경로를 찾아낸다.
• BFS는 그래프에서 사이클을 찾지 않고, 가까운 노드를 먼저 탐색하는 데 적합하다.

예시) 같은 미로에서 모든 가로행을 먼저 탐색하고, 그 다음에 세로열을 탐색하는 방식이다.

결론적으로

DFS는 깊이 관련 문제를 해결할 때 유용하며, BFS는 최단 경로와 가까운 노드를 탐색할 때 효과적이다.

그럼 다시 본론으로 돌아와서...

해당 타겟 넘버 문제를 살펴보자. 

문제에서는 주어지는 숫자 배열 numbers를 각각 더하거나 빼면서 target 값을 생성하는 방법을 반환하는 solution을 찾도록 되어있다.

그렇다면 numbers에 있는 숫자 개수 만큼 + 또는 -의 연산자가 필요하다.

모든 숫자 앞에는 + 또는 -의 연산을 해야하므로, 각각의 숫자는 + 또는 - 중에 선택되어야 하며, 트리 형태로 표현해보면 다음과 같이 표현할 수 있다.

즉, 모든 경우의 수에 대해서 끝까지 탐색해 봐야 target 값이 도출되는지를 확인할 수 있다.

따라서 위 문제는 DFS로 해결할 수 있다.

DFS는 재귀 함수를 이용한다. 그럼 재귀함수를 어떻게 구성할 수 있을까?

한번의 연산에서는 +연산을 했을 때와 -연산을 했을 때의 두가지 경우를 고려할 수 있기 때문에, 두 연산을 각각 수행할 수 있도록 재귀함수를 사용해야 한다.

그런데, 마지막 노드에 대해서는 더이상 탐색할 것이 없기 때문에=해당 분기에 대해서는 다 탐색을 했기 때문에, 해당 연산이 target이 나오는지를 확인하고, 해당하면 이 분기는 타켓 넘버를 계산할 수 있는 경우의 수중 하나가 되기 때문에 1을 반환하도록 할 것이다.

따라서 solution이 시작될 때는 vector가 비어있는지부터 확인하여(비어있다면 다 탐색했다는 의미이므로), 비어있으면 return하는 동작을 수행하도록 한다.

그렇지 않다면 vector의 마지막 요소를 따로 저장해둔뒤, 해당 요소를 삭제한다.

그리고 solution함수를 호출해서 마지막 요속 삭제된 vector를 넘겨주고, target에 마지막 요소를 더한 값을 target자리로 같이 넘겨준다. 반환된 값을 answer에 저장되도록 한다.

이를 빼기 연산에 대해서도 동일하게 수행한다.

target에 vector의 마지막 요소를 더하거나 뺌으로써 탐색을 마쳤을 때 최종 target값이 0이 되면 해당 분기는 하나의 경우의 수가 되는 방식으로 생각했다. (=수학을 잘하자..)

그러면 최종적으로 answer에는 모든 경로를 탐색하여 얻은 "타겟 넘버를 만드는 경우의 수"를 저장하게 될 것이다.

코드는 아래와 같다.

int solution(vector<int> numbers, int target) {
    if(numbers.empty()){
        if(target==0) return 1;
        else return 0;
    }
    
    int answer = 0;
    int top = numbers.back();
    numbers.pop_back();
    
    answer+=solution(numbers, target+top);
    answer+=solution(numbers, target-top);
    
    return answer;
}