뚝딱뚝딱

***정렬을 이용한 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;
}

첫 sql문 문제 풀이이다.

데이터베이스설계를 들으면서 sql문은 어느 정도 익숙해져 있고, 정처기를 준비하면서도 복잡한 sql문을 공부해 왔어서 어렵지 않게 문제를 풀 수 있었으나...! 역시 디테일한 부분은 좀 더 공부할 필요가 있음을 느낀 첫 문제였다.

DATE 형식의 컬럼의 출력 형태 변환하는 방법!

이 문제에서 내가 걸렸던 부분은 주의사항에 있는 DATE 형식을 주어진 예제의 출력결과처럼 변경하여 출력할 수 있도록 하는 것이었다.

문제에서 PUBLISHED_DATE의 형식을 'YYYY-MM-DD' 형태로 출력하도록 요구하고 있다.

처음에는 이 부분을 확인하지 못하고 그냥 출력해 보았는데, 뒤에 상세한 시간까지 출력되는 것을 확인하였다.

이렇게 시간까지 표시되는 것을, 날짜만 표시되도록 변경해주어야 한다.

이때 사용할 수 있는 것이 DATE_FORMAT() 함수이다!!

mysql : DATE를 원하는 형식으로 변경하기

각 sql마다 다른데, 내가 사용하는 mysql을 기준으로는 다음과 같은 방식을 사용할 수 있다.

1. 날짜→문자열로 변환

DATE FORMAT(날짜, 출력 형식)

문제 예시 ) DATE_FORMAT(A.PUBLISHED_DATE, '%Y-%m-%d')

위의 형태의 날짜를 '2020-01-02'의 형태로 리턴해준다.

2. 문자열→날짜로 변환
 
STR_TO_DATE(문자, 출력 형식)
 
예시) 
STR_TO_DATE('20080101', '%Y-%m-%d')

20080101이라는 문자를 2008-01-01의 형태의 날짜로 리턴해준다.

---

여기에서 주의할 점은 '%Y-%m-%d' 이 부분인데, 여기에서 Y이면 '2020'과 같은 형태를, m이면 '03'과 같은 형태를, d이면 '23'과 같은 형태로, 보통 'yyyy-mm-dd'형식의 출력을 얻을 수 있다.
이 부분이 왜 헷갈리냐면, 저 문자를 대문자로 쓰느냐, 소문자로 쓰느냐에 따라 다른 출력이 되기 때문이다.
나도 처음에는 모두 대문자로 써서, 월은 'march', 일은 'secondary_three' 이런식으로 나왔다.
따라서 형식에 따라 잘 구분지어 주어야 한다. 
자세한 내용은 아래의 표를 참고하자.

**FORMAT설명

위의 방법을 사용하고 출력한 결과이다.

원하는 출력 형태를 얻을 수 있었다!

전체 코드는 아래와 같다.

SELECT A.BOOK_ID, B.AUTHOR_NAME, DATE_FORMAT(A.PUBLISHED_DATE, '%Y-%m-%d') AS PUBLISHED_DATE
FROM BOOK A JOIN AUTHOR B ON A.AUTHOR_ID=B.AUTHOR_ID 
WHERE A.CATEGORY='경제' 
ORDER BY A.PUBLISHED_DATE;

join할 때 조인할 테이블을 A, B이런식으로 지정해주는 건 정처기 때 버릇.. 아주 좋은 버릇인거 같다.

가끔 안해도 돌아갈 때가 있는데, 정확하게 쓰는 거는 위가 맞기 때문에, 최대한 쓰려고 한다.

select ~ from~join~on~where~order by~ 순으로 알아보기 쉽게 줄바꿈 해 두었다.

* DATE_FORMAT(A.PUBLISHED_DATE, '%Y-%m-%d') AS PUBLISHED_DATE 

이런 부분의 경우, 예시 출력 형태를 보고 컬럼 이름을 잘 지정해주는 것이 중요한 포인트이다.

아깝게 틀릴 수 있는 사소한 문제이기 때문이다!

이상 백준허브 연동 겸 가볍게 풀어본 sql문제였다.

문제에서 예시로 주어진 접근 순서를 보고, 가장 멀리 있는 집부터 접근해야 한다는 건 다 캐치했을 것이다.

그런데 cap만큼 감소시키는 것을 불규칙한 vector 값에 바로 접근해서 푸는 건 복잡할 것 같았다.

집의 번수 = 물류창고로부터의 거리이고, 거리에 대한 정보도, 각 거리에 있는 집에 두어야 할/ 수거해야 할 택배 개수에 대한 정보도 동시에 가질 수 있는 방법이 무엇이 있을까 생각하다 보니.. 스택이 생각났다.

내가 접근한 방법은 delieveries와 pickups에서 0이 아닌 값을 갖는 인덱스+1(거리는 1부터니까)를 각 택배 개수만큼 스택에 차례로 넣는것이다. 그럼 스택은 뒤에서부터 빼니까, 우리가 원하는 대로 가장 멀리있는 집의 택배를 이용할 수 있게 된다.

두 스택에서 cap만큼씩 삭제하고, 이때 각각의 스택에서 맨 처음 삭제한 값이 가장 멀리까지 가는 거리가 되므로, top1과 top2에 저장해 둔다. 이때 주의할 점은 스택이 비어있지 않은 경우에만 삭제 해야 한다는 점이다.

한번 순회하고 갔다올 때 top1과 top2 중 더 큰 값에 따라서 갔다와야 한번에 해결할 수 있기 때문에 더 큰 값의 2배 만큼을 answer에 더해주면 된다!

c++ 코드는 아래와 같다.

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

using namespace std;

long long solution(int cap, int n, vector<int> deliveries, vector<int> pickups) {
	long long answer = 0;
	
	stack<int> st1, st2;

	for (int i = 0; i < n; i++) {//스택에 다 넣어준다
		for (int j = 0; j < deliveries[i]; j++) {
			st1.push(i + 1);
		}
		for (int k = 0; k < pickups[i]; k++) {
			st2.push(i + 1);
		}
	}

	int top1, top2;

	while (!st1.empty() || !st2.empty()) {//둘다 스택이 비워지면 그만
		top1 = top2 = 0;
        for (int i = 0; i < cap; i++) {
			if (!st1.empty()) {
				if (i == 0) {
					top1 = st1.top();
				}
				st1.pop();
			}

			if (!st2.empty()) {
				if (i == 0) {
					top2 = st2.top();
				}
				st2.pop();
			}
		}
		answer += max(top1, top2) * 2;
		
	}
	
	return answer;
}