뚝딱뚝딱

문제 자체가 힙을 구현하는 카테고리에 있는 걸 보고 접근한 거라, priorityqueue로 풀 수 있다는 걸 알고 풀어서 쉽게 풀어버린 케이스이다. 그래도 오랜만에 heap을 다루는 것이기도 하고, java에 있는 pq를 쓰는 건 처음이라 메소드도 익힐 수 있었다.

💡 Min Heap (PriorityQueue)

Heap?
- 완전 이진 트리의 일종, 우선순위 큐를 위하여 만들어진 자료구조.
- 힙에서는 중복된 값을 허용.
- max heap은 가장 큰 값이 부모노드에, min heap은 가장 작은 값이 부모노드에 있다.
- 부모노드는 자식노드보다 크거나 같고(max heap), 작거나 같아야(min heap) 한다.

- 힙은 배열을 통해 구현할 수 있다.
- 구현을 쉽게 하기 위해 0번 인덱스는 사용하지 않는다.
- 루트 노드가 1번 인덱스이다.
- 왼쪽 자식 노드 인덱스 : (부모노드 인덱스)*2
- 오른쪽 자식 노드 인덱스 : (부모노드 인덱스)*2+1
- 부모 노드 인덱스 : (자식노드 인덱스)/2

자바에서 힙은 java.util에 있는 PriorityQueue를 사용할 수 있고, 기본적으로 min heap을 구현한다.

💡 java.util.PriorityQueue

- 기본적으로 mean heap을 구현한다.
- 요소 삽입 : offer()
- 가장 작은 요소 반환 및 삭제 : poll()
- 가장 작은 요소 반환 : peek()
- 힙의 크기 반환 : size()

이 정도로 정리해 두면 문제는 충분히 풀 수 있다.

문제
매운 것을 좋아하는 Leo는 모든 음식의 스코빌 지수를 K 이상으로 만들고 싶습니다. 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 Leo는 스코빌 지수가 가장 낮은 두 개의 음식을 아래와 같이 특별한 방법으로 섞어 새로운 음식을 만듭니다.


Leo는 모든 음식의 스코빌 지수가 K 이상이 될 때까지 반복하여 섞습니다.
Leo가 가진 음식의 스코빌 지수를 담은 배열 scoville과 원하는 스코빌 지수 K가 주어질 때, 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 섞어야 하는 최소 횟수를 return 하도록 solution 함수를 작성해주세요.


모든 음식의 스코빌 지수를 K 이상으로 만들 수 없는 경우에는 -1을 return 합니다.

섞은 음식의 스코빌 지수 = 가장 맵지 않은 음식의 스코빌 지수 + (두 번째로 맵지 않은 음식의 스코빌 지수 * 2)

모든 음식의 스코빌 지수가 K이상이 된다는 것은, min heap에서 가장 우선 순위에 있는 노드의 값이 K이상인 것과 같고, 그렇게 되면 그 아래 모든 노드는 K이상이 되기 때문에, min heap을 이용해서 아주 쉽게 이 문제를 해결할 수 있다.

알고리즘은 다음과 같다.

1. PriorityQueue 객체를 Integer 타입으로 생성한다.
2. 스코빌 배열에 있는 모든 값을 우선순위 큐에 삽입한다.
3. while문을 통해 다음의 조건을 만족하는 경우에만 반복실행한다
   "우선순위 큐의 가장 작은 값=가장 먼저 나오는 값이 K보다 작고, 우선순위 큐에 있는 요소가 2개이상인 경우"
   다음을 실행한다
   우선순위 큐에서 가장 작은 값 두개 꺼내고 위의 식을 통해 섞은 음식의 스코빌 지수를 구한 후 이를 다시 큐에 삽입한다. 그리고 answer 값을 1 올린다.
   위 과정을 조건을 만족할 경우에 반복한다
4. 위 과정을 마치고 나면 큐는 스코빌 지수가 모두 K이상이거나, 큐에 있는 요소가 2개 미만인 상태일 수 있다.
5. 전자의 경우라면 answer를 그대로 반환하면 되고, 후자의 경우라면 모든 음식을 섞어도 K이상이 안된다는 것이므로 문제에서 주어진 조건에 따라 -1을 반환하면 된다.

전체 코드는 아래와 같다.

import java.util.PriorityQueue;

class Solution {
    public int solution(int[] scoville, int K) {
        int answer = 0;
        
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        
        for(int item : scoville){
            pq.offer(item);
        }
        
        while(pq.peek()<K && pq.size()>=2){
            int temp1 = pq.poll();
            int temp2 = pq.poll();
            pq.offer(temp1+(temp2*2));
            answer++;
        }
        
        if(pq.size()==1 && pq.peek()<K) return -1;
        
        return answer;
    }
}

*** while문을 실행하고 나면 어차피 pq.peek()<K라는 것은 pq.size()==1인 것과 동시에 일어나기 때문에, 마지막 if문에서는 pq.peek()K만 만족하면 -1을 반환하도록 코드를 줄여도 된다.

자바 문법 정도만 레퍼런스를 받고, 알고리즘 자체는 직접 구현한 풀이 방법이다.

set을 활용한 부분에 있어서는 다른 사람들의 코드를 살펴보니 대부분 사용하는 편인 것 같았다.

전체적인 진행 방향은 다음과 같다.

1. 문자열에 들어 있는 0~9 숫자들을 INT 타입으로 바꾸어 int배열에 저장한다.
2. 배열에 저장된 수를 가지고, 직접 짠 조합 알고리즘을 통해 가능한 모든 숫자 조합을 찾아 SET 자료구조에 저장한다.
3. SET에 저장된 숫자가 소수인지 판별하여, 소수인 경우에만 카운트를 한다.

SET 자료구조

- 중복된 값을 저장하지 않아서 유니크한 값으로만 구성된다.
- Set 자료구조는 인터페이스라서 HashSet로 Integer를 명시해서 생성해야 한다.

• 문자열에 들어있는 숫자를 조합해 나올 수 있는 모든 수를 구해야 한다.
• permutation 함수를 이용할 수 있었는데, 존재를 까먹고 조합 알고리즘을 직접 구현함.
• 문자열의 각 숫자를 INT 형식으로 바꾸어 INT타입의 배열에 저장해줌.
• 그 INT배열을 가지고 숫자를 조합하는데, 중복된 숫자 값이 생성될 수 있으므로 Set 자료구조를 사용해서 중복된 값이 들어가지 않도록 하였음.
• 일단, 자리수 하나의 숫자들을 set에 저장.
• 그리고 각각의 저장된 숫자를 제외한 배열 값을 갖는 새로운 배열을 만들어서 재귀적으로 가능한 조합을 만들 수 있도록 하는 함수의 인자로 넣어줌.
• 그 함수가 makePrime인데, 함수이름만 makePrime이고, 사실상 조합을 만드는 함수임. 나의 실수.
• makePrime함수에서는 주어진 배열과, set, 이전에 이미 방문?했던 앞자리 수를 인자로 받음.
• 그리고 앞자리수가 하나 제외되어있는 주어진 배열에 있는 값을 하나씩 앞자리 수에 더하여 수를 만들고 set에 집어 넣음.
• 이때 앞자리 수에 10을 곱하고 배열에 있는 값 중 현재 가리키는 값을 더함으로써 새로운 수를 만들 수 있음.
• 그리고 makePrime함수를 재귀호출함으로써 위의 과정을 반복하다 보면, set에는 모든 가능한 숫자 조합이 만들어져 있음.
• 이 set을 가지고, 순회하면서, 만약 값이 0,1이라면 소수로 포함하지 않고, 2,3,5,7이라면 소수로 카운팅 함.
• 그리고 2의 배수라면 소수로 포함하지 않고, 2의 배수가 아니라면 해당 값을 3부터 (해당값/3)을 한 값까지로 나누었을 때 나머지가 0이면 => 1과 자기 자신 말고도 나눠지는 값이 있다는 것이므로 소수가 아니고, 카운팅 하지 않는다. 만약 그런 값이 하나도 없었다면(=>불리언 값으로 판단함) 소수로 카운팅한다.
• 위의 과정을 거침으로써 소수의 개수를 찾을 수 있다.
• 다소 복잡하게 보이지만, 스스로 짰다는 것에 의의를 둔다.
• 메소드를 익히는 것도 중요해 보인다.

전체 코드이다.

import java.util.HashSet;
import java.util.Set;

class Solution {
    public int[] removeValue(int[] arr, int remove){
        int[] newarr = new int[arr.length-1];
        int first = 0;
        int index = 0;
        for(int i : arr){
            if(i==remove && first==0){
                first = 1;
            }else{
                newarr[index]=i;
                index++;
            }
        }
        
        return newarr;
    }
    
    public void makePrime(int[] arr, Set<Integer> set, int prev){
        for(int i=0; i<arr.length; i++){
            set.add(prev*10+arr[i]);
            int[] newarr = removeValue(arr, arr[i]);
            makePrime(newarr, set, prev*10+arr[i]);
        }
    }
    
    public int solution(String numbers) {
        int answer = 0;//count
        
        int[] nums = new int[numbers.length()];
        Set<Integer> set = new HashSet<>();
        
        for(int i=0; i<numbers.length(); i++){
            nums[i] = Character.getNumericValue(numbers.charAt(i));
        }
        
        for(int i=0; i<nums.length; i++){
            set.add(nums[i]);
            int[] newarr = removeValue(nums, nums[i]);
            makePrime(newarr, set, nums[i]);
        }
        
        //set에는 가능한 모든 값들이 생성된다.
        
        for(int i : set){
            if(i==0 || i==1){//0이거나 1이면 패스
                continue;
            }
            if(i==2 || i==3 || i==5 || i==7){//2,3,5,7이면 count
                answer++;
                continue;
            }
            if(i%2==0){//2의 배수이므로 패스
                continue;
            }else{
                int isPrime = 1;
                for(int j=3; j<=(i/3); j++){
                    if(i%j==0){
                        isPrime=0;
                        break;
                    }
                }
                if(isPrime==1) answer++;
            }
        }
        
        return answer;
    }
}

이 문제를 푸는데만 1시간 반이 걸렸지만, 성공한게 뿌듯했다. 

스택 알고리즘에서 자주 다루는 () 괄호 문제.

전공 책만 봐도 기본으로 나오는 예제인 것 같다.

그래서 막힘없이 술술 풀릴정도라, 왜 LV2인지는 모르겠으나.. 안 접해본 사람이라면 고민은 해볼 수 있을정도!

본론으로 들어가자면..

스택 (Stack)

• 후입선출(LIFO) 방식의 자료구조.
• 즉, 나중에 들어간 것이 가장 먼저 나오는 구조이다.

이 스택을 어떻게 괄호 문제에 활용할 수 있을까?

괄호가 열리면, 반드시 짝이되는 닫는 괄호가 있어야 한다.

괄호가 열릴 때마다 저장해 두었다가 닫는 괄호를 만나면 하나씩 삭제해 나가면 된다.

만약 열린 괄호의 내역이 없는데, 닫힌 괄호를 만난다면 ? 열린괄호가 없었으므로 닫힌 괄호는 올수없고 이는 규칙을 위반한 사례이므로 false를 반환한다.

그럼 열린 괄호를 어떻게 저장할 수 있을까?

바로 스택을 활용한다.

문자열 타입의 빈 스택을 생성해두고, 인자로 받은 (,)로만 이루어진 문자열 s의 첫번째 문자부터 순회한다.

문자가 열린괄호 ( 이면 스택에 넣어둔다. 그리고 ) 괄호이면, 짝을 하나 찾은 것이므로 스택에서 가장 마지막에 들어간 ( 을 빼주면 된다 = pop으로 가장 마지막 요소가 삭제된다.

그런데 여기서 주의할 점은, 스택이 만약 비어있었다면, 이전에 열린괄호 (가 없었다는 뜻이기 때문에, 규칙을 위반한 것이다. 따라서 이런 경우에는 바로 false를 리턴하도록 한다.

s 문자열을 다 순회하였는데, 스택이 비어있지 않다면?

스택이 비어있지 않다는 건, 이전에 들어왔던 열린 괄호 개수만큼  짝이 될 닫힌 괄호가 없었다는 뜻과 같기 때문에, 이 경우에도 false를 리턴해야 한다.

따라서 결과가 true가 되려면, string 순회 후에 스택이 비어있어야 함을 알 수 있다.

위를 바탕으로 코드를 짜면 아래와 같다.

import java.util.Stack;

class Solution {
    boolean solution(String s) {
        boolean answer = true;
        
        Stack<String> st = new Stack<>();
        
        for(int i=0; i<s.length(); i++){
            if(s.charAt(i) == '('){
                st.push("(");
            }else{
                if(st.isEmpty()){
                    return false;
                }else{
                    st.pop();
                }
            }
        }
     
        if(!st.isEmpty()) answer = false;
        
        return answer;
    }
}

<자바 문법>

** Stack을 사용하려면 java.util.Stack을 import 해야함.

** 문자열의 특정 위치의 문자에 접근하려면, s.charAt(인덱스) 를 사용하여 접근해야함.

** 문자의 경우 ' ', 문자열의 경우 " " 임을 명심하자. 

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

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(변수)

💡 문제)
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를 갖는 레코드에 대해서는 하나의 레코드만 출력되는 예외가 발생할 수 있기 때문에, 서브쿼리를 이용한 풀이가 더 맞다고 본다.