• 차량 내역이 담긴 배열(records) 순회하면서 treeMap에 각 차량번호와 누적 시간 담기 => 시간을 분단위로 계산 후, IN일 경우는 더하기, OUT일 경우는 빼기
• treeMap에 저장된 누적 시간에 따라 요금 계산하기 => 누적 시간이 양수이면 OUT이 없는 차량이므로 23:59으로 OUT 계산 후 treeMap에 넣기 => 요금 계산 후 배열에 넣기 (calFees 함수)
  

👍🏼 원래는 HashMap에 넣고 Key 기준으로 정렬하려고 했는데 TreeMap이 생각나서 다시 수정함 ! (TreeMap : Key 기준으로 자동 정렬) 🚨 주의 ) Math.ceil로 올림할 때 Double형으로 계산하고 올림해야함 (int형으로 나눗셈하면 안됨)

import java.util.*;

class Solution {
    static int defTime, defFee, unitTime, unitFee;
    public int[] solution(int[] fees, String[] records) {
        defTime = fees[0];
        defFee = fees[1];
        unitTime = fees[2];
        unitFee = fees[3];

        // treeMap에 차량번호와 각각 시간 담기
        Map<String, Integer> recMap = new TreeMap<>();
        for(String record : records){
            String[] str = record.split(" ");
            // 분 단위로 변경
            String[] time = str[0].split(":");
            int minute = Integer.parseInt(time[0]) * 60 + Integer.parseInt(time[1]);

            // 누적 시간 구하기
            if (str[2].equals("IN")){ // IN일 경우 시간 더하기
                 recMap.put(str[1], recMap.getOrDefault(str[1], 0) + minute);
            } else { // OUT일 경우 시간 빼기
                recMap.put(str[1], recMap.getOrDefault(str[1], 0) - minute);
            }
        }

        // treeMap에 각 차량번호에 따라 누적 시간 요금 계산
        int idx = 0;
        int[] answer = new int[recMap.size()];  // 결과 배열
        for(String rec : recMap.keySet()){
            if (recMap.get(rec) >= 0){  // OUT이 입력되지 않았으면 23:59을 OUT으로 계산하기
                recMap.put(rec, recMap.get(rec) - (23 * 60 + 59));
            }
            // 요금 계산 후 배열에 넣기
            answer[idx++] = calFees(recMap.get(rec) * -1);
        }

        return answer;
    }

    public int calFees(int time){
        if (time < defTime) return defFee;
        return defFee + (int)Math.ceil(Double.valueOf(time - defTime) / Double.valueOf(unitTime)) * unitFee;
    }
}

• k진수로 변환할 때 나눈 나머지를 StringBuilder에 저장하고 마지막에 문자열을 뒤집어서 진수로 변환
• 진수로 바꾼 숫자를 0을 기준으로 분리
• 분리해서 각 숫자가 소수인지 판별
• 🚨 주의 -> 시간초과 발생
  • long 자료형 필요 -> n의 최대값인 1,000,000을 2진수로 변환하면 2^19로 19자리쯤 되는 10진수로 변환됨
  • 소수 판별할 때 n의 제곱근보다 작은 자연수로 확인하기 -> 0 기준으로 분리했을 때 특정 값이 "1122222222221" 이렇게 크다면 n보다 작은 수로 반복문 돌면서 확인하면 너무 오래걸림

import java.util.*;

class Solution {
    public int solution(int n, int k) {
        int answer = 0;

        String num = calNum(n, k); // 진수 계산
        String[] splitNum = num.split("0"); // 0을 기준으로 분리하기
        for(String s : splitNum){
            if (s.isEmpty()) continue;
            if (isPrime(Long.parseLong(s))) answer++;
        }

        return answer;
    }

    // k진수로 변환
    public String calNum(int num, int k){
        StringBuilder sb = new StringBuilder();

        while(num >= k){
            long n = num % k;
            sb.append(String.valueOf(n));
            num /= k;
        }
        sb.append(num);
        return sb.reverse().toString();
    }

    // 소수 판별
    public boolean isPrime(long num){
        if (num <= 1) return false;
        for(int i = 2; i<=Math.sqrt(num); i++){
            if (num % i == 0) return false;
        }
        return true;
    }
}

• cntMap : 유저별 신고 당한 횟수 카운트
• idMap : 유저별 신고한 ID 리스트로 넣기
• reportSet : report 중복 제거
• cntMap의 value를 확인하면서 k 이상 신고 당한 유저를 리스트에 넣기
• idMap을 돌면서 유저가 신고한 ID 리스트 중에 정지당한 유저가 있으면 resCnt++

import java.util.*;

class Solution {
    public int[] solution(String[] id_list, String[] report, int k) {
        HashMap<String, Integer> cntMap = new HashMap<>(); // 신고당한 횟수
        HashMap<String, ArrayList<String>> idMap = new HashMap<>(); // 유저별 신고한 ID 
        HashSet<String> reportSet = new HashSet<>(); 

        // idMap에 유저 넣기
        for(int i = 0; i<id_list.length; i++){
            idMap.put(id_list[i], new ArrayList<String>());
        }
        // report 중복 제거
        for(String rep : report){
            reportSet.add(rep);
        }

        // 신고당한 횟수와 해당 유저가 신고한 ID 각각 해시맵에 넣기
        for(String rep : reportSet){
            String[] input = rep.split(" ");
            cntMap.put(input[1], cntMap.getOrDefault(input[1], 0) + 1);
            idMap.get(input[0]).add(input[1]);
        }

        // 신고당한 횟수가 k 이상인 유저 리스트에 넣기 
        ArrayList<String> banned = new ArrayList<>();
        for(String cnt : cntMap.keySet()){
            if (cntMap.get(cnt) >= k) banned.add(cnt);
        }

        // idMap을 돌면서 신고한 ID 중 정지당한 ID 있으면 count
        int[] answer = new int[id_list.length];
        for(int i = 0; i<id_list.length; i++){
            ArrayList<String> check = idMap.get(id_list[i]);
            int resCnt = 0;
            for(String c : check){
                if (banned.contains(c)) resCnt++;
            }
            answer[i] = resCnt;
        }

        return answer;
    }
}

• 카테고리로 그룹화 후에 MAX 집계함수로 비싼 식품 나오게 했음 🫥 분명히 맞는데.. 자꾸 틀려서 헤매다가

• group by에 없는 컬럼이고 집계함수도 아닌 컬럼을 select에 사용해서 상품 이름이 정확히 매핑되지 않음 => 서브쿼리 필요

SELECT CATEGORY, MAX(PRICE) AS MAX_PRICE, PRODUCT_NAME
FROM FOOD_PRODUCT
GROUP BY CATEGORY
HAVING CATEGORY IN ('과자', '국', '김치', '식용유')
ORDER BY MAX_PRICE DESC

💡 풀이

• 서브쿼리를 통해 그룹화해서 카테고리별 가장 큰 금액과 카테고리명 가져오기
• where절에서 해당 카테고리와 금액인 칼럼 출력

  SELECT CATEGORY, PRICE AS MAX_PRICE, PRODUCT_NAME
  FROM FOOD_PRODUCT
  WHERE (CATEGORY, PRICE) IN (
    SELECT CATEGORY, MAX(PRICE)
    FROM FOOD_PRODUCT
    GROUP BY CATEGORY
    HAVING CATEGORY IN ('과자', '국', '김치', '식용유')
  )
  ORDER BY MAX_PRICE DESC

• 각 배열을 각각 큐에 넣고, 합계도 구하기
• queue1의 합이 queue2의 합보다 더 작으면 queue2에서 꺼내서 queue1에 넣기
• 반대로 queue2도 더 작으면 queue1 원소 넣기
• 큐에서 넣을때 해당 큐에 원소가 하나밖에 없으면 같은 합을 못 만드므로 -1 리턴 🫥 테스트케이스 30개중 5개 시간초과

  import java.util.*;
  

class Solution { public int solution(int[] queue1, int[] queue2) { int answer = 0; int sum1 = 0; int sum2 = 0; int total = sum1 + sum2; Queue q1 = new LinkedList<>(); Queue q2 = new LinkedList<>(); for(int i = 0; i<queue1.length; i++){ sum1 += queue1[i]; sum2 += queue2[i];

        q1.add(queue1[i]);
        q2.add(queue2[i]);
    }

    while(sum1 != sum2){
        if (sum1 < sum2){
            if (q2.size() == 1) return -1;
            int n = q2.poll();
            sum1 += n;
            sum2 -= n;
            q1.add(n);
        } else {
            if (q1.size() == 1) return -1;
            int n = q1.poll();
            sum2 += n;
            sum1 -= n;
            q2.add(n);
        }
        answer++;
    }


    return answer;
}

}

![](https://velog.velcdn.com/images/inss_/post/f4ad61dd-fcab-4492-b2fe-d9c2d2ff7d2c/image.png)

</br>
</br>

### 💡 풀이
- queue2 원소 합은 굳이 필요 없이 queue1 원소 합이랑 total 원소 합 구하기
- 위 코드에서 실패했던 이유는 다 순회해서 결국 처음 큐의 원소와 같아졌으면 더이상 반복할 필요 없어서 return -1
- queue1.length * 4는 (queue1.length + queue2.length) * 2를 의미
```java
import java.util.*;

class Solution {
    public int solution(int[] queue1, int[] queue2) {
        int answer = 0;
        long sum1 = 0;
        long total = 0;
        Queue<Integer> q1 = new LinkedList<>(); 
        Queue<Integer> q2 = new LinkedList<>();
        for(int i = 0; i<queue1.length; i++){
            sum1 += queue1[i];
            total += queue1[i] + queue2[i];

            q1.add(queue1[i]);
            q2.add(queue2[i]);
        }

        while(sum1 != total/2){
            // 다 순회하고 결국 다시 원래 자리로 오면 return
            if (answer > queue1.length * 4) return -1;

            if (sum1 < total/2){
                if (q2.size() == 1) return -1;
                int n = q2.poll();
                sum1 += n;
                q1.add(n);
            } else {
                if (q1.size() == 1) return -1;
                int n = q1.poll();
                sum1 -= n;
                q2.add(n);
            }
            answer++;


        }


        return answer;
    }

}

• String 날짜를 일수로 변경해주는 함수 => toDays
• 약관 종류와 유효기간 Map에 담기
• privacies 하나씩 확인하면서 개인정보 수집 일자 + 유효기간 일수 구하기
• 오늘 날짜 일수와 비교해서 오늘 날짜가 더 크면 만료기간이 지났으므로 정답 리스트에 담기
• ⭐ "2021.01.11" . 기준으로 나눌 때 split(".") 아닌 split("\.")으로 해야함

• 전자로 하면 .(dot)을 모든 문자를 기준으로 나뉨

  import java.util.*;
  

class Solution { public int[] solution(String today, String[] terms, String[] privacies) { int todays = toDays(today); // 오늘 날짜 일수로 변경 ArrayList res = new ArrayList<>();

    // 약관 종류와 유효기간 map에 담기
    HashMap<String, Integer> termMap = new HashMap<>();
    for(String term : terms){
        termMap.put(term.split(" ")[0], Integer.parseInt(term.split(" ")[1]));
    }

    for(int i = 0; i<privacies.length; i++){
        String[] sp = privacies[i].split(" ");
        // 개인정보 수집 일자 + 유효기간
        int expDays = toDays(sp[0]) + termMap.get(sp[1]) * 28;

        if (todays >= expDays) res.add(i+1);
    }

    // list에 담은 정답 배열로 옮기기
    int[] answer = new int[res.size()];
    int idx = 0;
    for(int r : res){
        answer[idx++] = r;
    }
    return answer;
}

// 일수로 변경 메소드
public int toDays(String date){
    String[] d = date.split("\\.");
    int year = Integer.parseInt(d[0]);
    int month = Integer.parseInt(d[1]);
    int day = Integer.parseInt(d[2]);

    return year * 12 * 28 + month * 28 + day;
}

} ```

• place 배열 돌면서 응시자(P) 확인 후 List에 넣기, 2차원 배열에 응시자, 테이블, 파티션 정보 넣기
• 응시자 리스트에 2중 for문으로 두명씩 확인하기 => isCheck
• 두 응시자의 맨해튼 거리가 1이면 무조건 false 2이면 두 응시자 거리가 직선인 경우, 대각선인 경우 생각해서 테이블(X)이 있는지 확인하기 => checkPartition

import java.util.*;

class Solution {
    public int[] solution(String[][] places) {
        int[] answer = new int[5];
        int idx = 0;
        for(String[] place : places){
            ArrayList<int[]> pList = new ArrayList<>(); // 응시자 좌표 담기
            String[][] arr = new String[5][5];   // place 2차원 배열에 담기

            for(int i = 0; i<place.length; i++){
                String p = place[i];
                for(int j = 0; j<p.length(); j++){
                    if (p.charAt(j) == 'P') pList.add(new int[]{i, j});
                    arr[i][j] = String.valueOf(p.charAt(j));
                }
            }

            // isCheck 함수로 거리두기 확인하기
            answer[idx++] = isCheck(pList, arr) ? 1 : 0;
        }
        return answer;
    }


    public boolean isCheck(ArrayList<int[]> pList, String[][] arr){
        for(int i = 0; i<pList.size(); i++){
            for(int j = i + 1; j<pList.size(); j++){
                // 거리두기를 하라도 안지킨 응시자가 있으면 false 후 종료
                if (!checkPartition(pList.get(i), pList.get(j), arr)) {
                    return false;
                }
            }
        }

        return true;
    }

    // 거리두기 확인
    public boolean checkPartition(int[] a, int[] b, String[][] arr){
        int x1 = a[0], y1 = a[1];
        int x2 = b[0], y2 = b[1];

        int dist = Math.abs(x1 - x2) + Math.abs(y1 - y2);

        // 거리가 1인 경우
        if (dist == 1) return false;

        // 거리가 2인 경우
        if (dist == 2) {
            // 두 응시자 거리가 직선인 경우
            if (x1 == x2) return arr[x1][(y1 + y2) / 2].equals("X");
            else if (y1 == y2) return arr[(x1 + x2) / 2][y2].equals("X");
            // 대각선인 경우
            else return arr[x2][y1].equals("X") && arr[x1][y2].equals("X");
        } 

        return true;
    }
}

🫥 처음에는 무조건 조합 알고리즘 써서 2명씩 뽑고 확인하려고 했는데 그냥 2명만 뽑으면 되니까 이중 for문으로 간단하게 해도 됐다 ..!

✔️ 2중 for문

• 보석 종류 수 세기 위해서 Set에 넣고 크기 구하기
• 보석 첫번째 부터 2중 for문 돌면서 새로운 set에 넣고 현재 확인 중인 set 크기랑 보석 종류 수 같고, 구간이 짧으면 answer 배열에 넣기
• 😓 뭐야 쉽네???? 했지만 효율성에서 실패

  import java.util.*;
  

class Solution { public int[] solution(String[] gems) { Set set = new HashSet<>(); for(String gem : gems){ set.add(gem); }

    int[] answer = new int[2];
    int result = Integer.MAX_VALUE;
    for(int i = 0; i<gems.length; i++){
        Set<String> s = new HashSet<>();
        for(int j = i; j<gems.length; j++){
            s.add(gems[j]);

            if(set.size() == s.size()) {
                if (result > j - i) {
                    result = j - i;
                    answer[0] = i + 1;
                    answer[1] = j + 1;
                }
                break;
            }
        } 
    }


    return answer;
}

}

</br>
</br>

### 🚨 두번째 실패 풀이
✔️ 투포인터 + HashSet
- 이중탐색으로 생각해봤지만 아무리 생각해도 모르겠어서 GPT 한테 힌트를 구하니까 (까먹고 있었던) 투포인터를 사용하라고 했다..!
- 투포인터를 사용하는데 계속 left = 0, right = 배열 사이즈 로 생각 하니까 잘 안풀렸는데 left = 0, right = 0 으로도 풀 수 있었음
- 😓 하지만 while문 안에 또 for문으로 효율성 실패
![](https://velog.velcdn.com/images/inss_/post/1a2f2370-5794-4434-9a87-e9aae1742d94/image.png)
```java
import java.util.*;

class Solution {
    public int[] solution(String[] gems) {
        Set<String> set = new HashSet<>(Arrays.asList(gems));
        int targetCnt = set.size();

        int left = 0, right = 0;
        int[] answer = new int[2];
        int cnt = Integer.MAX_VALUE;
        while(left <= right && right < gems.length){
            Set<String> check = new HashSet<>();
            for(int i = left; i<=right; i++){
                check.add(gems[i]);
            }

            if (check.size() < targetCnt) right++;
            else if (check.size() == targetCnt) {
                if(cnt > right - left){
                    answer[0] = left+1;
                    answer[1] = right+1;

                    cnt = right - left;
                }

                left++;

            }
        }


        return answer;
    }
}

💡 정답 풀이

✔️ 투포인터 + HashMap

• 데이터를 1번만 순회해야 효율성에 통과해야하는 데 떠오르지 않아서 다른 사람 풀이 참고 ..
• 보석을 하나씩 추가하는데 해시맵에 저장해서 몇개가 들어있는지 Count => 다음에 right +1
• 해시맵에 보석 종류가 다 들어온 경우 (= 해시맵 사이즈가 종류 수랑 같은 경우) => 짧은 구간 찾아서 answer 배열 갱신 => 더 짧은 구간 있는지 파악하기 위해 left 증가, 이때 증가하기전에 해시맵에서 left 지점에 있는 보석 수 빼기

  import java.util.*;
  

class Solution { public int[] solution(String[] gems) { Set set = new HashSet<>(Arrays.asList(gems)); int types = set.size();

    int left = 0, right = 0;
    int[] answer = new int[2];
    int minLen = Integer.MAX_VALUE;

    HashMap<String, Integer> gem = new HashMap<>();
    while(right < gems.length){
        // 보석 추가
        gem.put(gems[right], gem.getOrDefault(gems[right], 0) + 1);
        right++;

        // gem 해시맵에 보석이 다 들어온 경우
        while (gem.size() == types) {
            // 보석 중 짧은 구간 찾기
            if (minLen > right - left){
                answer[0] = left+1;
                answer[1] = right;

                minLen = right - left;
            }

            // left 위치 늘리고 기존 left는 gem 해시맵에서 제거
            gem.put(gems[left], gem.get(gems[left]) - 1);
            if (gem.get(gems[left]) == 0){
                gem.remove(gems[left]);
            }
            left++;

        }
    }


    return answer;
}

}

• a, b 정점을 무조건 거쳐야 하므로 2가지로 나눠서 생각 1) 1 -> a -> b -> n 2) 1 -> b -> a -> n
• 그리고 각각 다익스트라 실행 (1에서 a, a에서 b, b에서 n)
• 최단 거리 테이블을 Integer.MAX_VALUE로 설정했다가 오버플로우 발생 => 간선이 없는 경우 MAX_VALUE를 3번 더하는 상황 발생
• 최대 간선 수 * 최대 가중치인 200,000,000으로 설정해야함

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

import java.util.ArrayList;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {
    static class Node{
        int v; // 간선
        int cost; // 가중치

        public Node(int v, int cost){
            this.v = v;
            this.cost = cost;
        }
    }

    static ArrayList<ArrayList<Node>> graph; // 노드 정보 담는 리스트
    static boolean[] visited; // 방문 처리
    static int[] dist; // 최단 거리 테이블
    static int v, e;
    static int INF = 200000000; // 최대 간선 수 * 최대 가중치

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        v = Integer.parseInt(st.nextToken());
        e = Integer.parseInt(st.nextToken());

        graph = new ArrayList<>();

        // 그래프와 최단 거리 테이블 초기화
        for(int i = 0; i<=v; i++){
            graph.add(new ArrayList<>());
        }

        for(int i = 0; i<e; i++){
            st = new StringTokenizer(br.readLine());
            int U = Integer.parseInt(st.nextToken());
            int V = Integer.parseInt(st.nextToken());
            int W = Integer.parseInt(st.nextToken());

            // 양방향
            graph.get(U).add(new Node(V, W));
            graph.get(V).add(new Node(U, W));
        }

        st = new StringTokenizer(br.readLine());
        int a = Integer.parseInt(st.nextToken());
        int b = Integer.parseInt(st.nextToken());

        // 1 -> a -> b -> n 인 경우
        int case1 = 0;
        case1 += dijkstra(1, a);
        case1 += dijkstra(a, b);
        case1 += dijkstra(b, v);

        // 1 -> b -> a -> n 인 경우
        int case2 = 0;
        case2 += dijkstra(1, b);
        case2 += dijkstra(b, a);
        case2 += dijkstra(a, v);

        int result = (case1 >= INF && case2 >= INF) ? -1 : Math.min(case1, case2);
        System.out.println(result);
    }

    public static int dijkstra(int start, int end){
        // visited와 dist 초기화
        visited = new boolean[v + 1];
        dist = new int[v + 1];
        for(int i = 0; i<=v; i++){
            dist[i] = INF;
        }

        PriorityQueue<Node> queue = new PriorityQueue<>((a, b) -> a.cost - b.cost);
        queue.add(new Node(start, 0));
        dist[start] = 0;

        while(!queue.isEmpty()){
            Node curr = queue.poll();
            int currV = curr.v;

            if (!visited[currV]){
                visited[currV] = true;

                for(Node n : graph.get(currV)){
                    if (!visited[n.v] && dist[n.v] > dist[currV] + n.cost){
                        dist[n.v] = dist[currV] + n.cost;
                        queue.add(new Node(n.v, dist[n.v]));
                    }
                }
            }
        }
        return dist[end];
    }
}

• 특정 노드에서 출발하여 다른 노드로 가는 각각의 최단 경로를 구하는알고리즘
• 시간복잡도 : O(E logN) (N : 노드 수, E : 간선 수)
• 간선의 가중치가 양수인 경우만 가능 (음수인 경우 플로이드워셜 알고리즘 사용)
• 그리디 알고리즘 사용
• 우선순위 큐(힙 자료구조) 사용

  동작과BR

  1. 출발 노드를 설정
  2. 최단 거리 테이블 초기화
  3. 방문하지 않은 노드 중에서 최단 거리(가중치)가 가장 짧은 노드 선택
  4. 해당 노드를 거쳐 다른 노드로 가는 비용 계산하여 최단 거리 테이블 갱신
  5. 3, 4번 반복

구현

1. 출발 지점의 노드가 1이므로 우선순위 큐에 넣기, 출발 노드에서 출발 노드로의 거리는 0이므로 0으로 초기화

   노드 번호	1	2	3	4	5
   가중치	0	MAXVALUE	MAXVALUE	MAXVALUE	MAXVALUE
   우선순위 큐 : (거리: 0, 노드: 1)

2. 큐에서 노드 꺼내기 -> 해당 노드를 이미 처리했으면 무시하고 처리하지 않은 노드는 최소 비용 계산 => 2번(0 + 2), 3번(0 + 3)

   꺼낸 원소 : (거리: 0, 노드: 1)

   노드 번호	1	2	3	4	5
   가중치	0	2	3	MAXVALUE	MAXVALUE
   우선순위 큐 : (거리: 2, 노드: 2), (거리: 3, 노드: 3)

3. 과정 반복 => 3번(2 + 4)은 기존 거리 3보다 크므로 넘어감, 4번(2 + 5) 꺼낸 원소 : (거리: 2, 노드: 2)

   노드 번호	1	2	3	4	5
   가중치	0	2	3	7	MAXVALUE
   우선순위 큐 : (거리: 3, 노드: 3), (거리: 7, 노드: 4)

4. 4번(3 + 6)으로 기존 거리 7보다 커서 넘어감 꺼낸 원소 : (거리: 3, 노드: 3)

   노드 번호	1	2	3	4	5
   가중치	0	2	3	7	MAXVALUE
   우선순위 큐 : (거리: 7, 노드: 4)

5. 해당 노드에서 가는 길이 없어서 큐가 비어서 종료 꺼낸 원소 : (거리: 7, 노드: 4)

   노드 번호	1	2	3	4	5
   가중치	0	2	3	7	MAXVALUE
   우선순위 큐 :

⭐ 관련 문제

백준 1753번 최단경로

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

import java.util.ArrayList;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {
    static class Node{
        int v; // 간선
        int cost; // 가중치

        public Node(int v, int cost){
            this.v = v;
            this.cost = cost;
        }
    }

    static ArrayList<Node>[] graph; // 노드 정보 담는 리스트
    static boolean[] visited; // 방문 처리
    static int[] dist; // 최단 거리 테이블

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int v = Integer.parseInt(st.nextToken());
        int e = Integer.parseInt(st.nextToken());
        int s = Integer.parseInt(br.readLine());

        graph = new ArrayList[v + 1];
        visited = new boolean[v + 1];
        dist = new int[v + 1];

        // 그래프와 최단 거리 테이블 초기화
        for(int i = 1; i<=v; i++){
            graph[i] = new ArrayList<>();
            dist[i] = Integer.MAX_VALUE;
        }

        for(int i = 0; i<e; i++){
            // u -> v로 가는 가중치 w
            st = new StringTokenizer(br.readLine());
            int U = Integer.parseInt(st.nextToken());
            int V = Integer.parseInt(st.nextToken());
            int W = Integer.parseInt(st.nextToken());

            graph[U].add(new Node(V, W));
        }

        // 다익스트라 수행
        dijkstra(s);
        for(int i = 1; i<=v; i++){
            System.out.println((dist[i] == Integer.MAX_VALUE ? "INF" : dist[i]));
        }

    }

    static void dijkstra(int start){
        // 우선순위 큐 사용 - 가중치 기준으로 오름차순
        PriorityQueue<Node> queue = new PriorityQueue<>((a, b) -> a.cost - b.cost);
        queue.add(new Node(start, 0));
        dist[start] = 0;

        while(!queue.isEmpty()){
            // 최단 거리가 짧은 노드 꺼내기
            Node curr = queue.poll();
            int currV = curr.v;

            // 이미 방문한 노드는 무시
            if (!visited[currV]) {
                visited[currV] = true;

                for(Node n : graph[currV]){
                    int v = n.v;
                    int cost = n.cost;

                    // 현재 노드 거리 + 확인하는 노드 거리가 최단 거리일 경우 업데이트
                    if (!visited[v] && dist[currV] + cost < dist[v]){
                        dist[v] = dist[currV] + cost;
                        queue.add(new Node(v, dist[v]));
                    }
                }
            }
        }
    }
}

백준 1504번 특정한 최단 경로

• 집합 내부에 값이 존재하는지 여부
• IN 쿼리 -> 메인 쿼리순서로 진행
• 예제 [STUDENT 테이블][

  SELECT *
  FROM STUDENT
  WHERE department_id IN ('1001', '1002');
  

// 결과 이름이 홍길동인 row만 출력됨

</br>

### NOT IN 
- 조건이나 서브쿼리에 일치하지 않는 값을 반환
- ⭐ 조건에 null이 존재하게 되면 no rows selected로 UNKNOWN(=false) 값이 반환되므로 무조건 null 처리 필요!!!!
- 관련 문제 : [업그레이드 할 수 없는 아이템 구하기](https://school.programmers.co.kr/learn/courses/30/lessons/273712)


</br>

</br>

### EXISTS
- 결과로 TRUE, FALSE 반환하는 연산자
- 테이블 간의 결과를 어떤 값이 존재하는 지만 조회할때 사용
- 메인 쿼리 -> EXISTS 쿼리 순서로 진행
=> 메인 쿼리에 먼저 접근 후 ROW 하나 가져오고 EXISTS 서브쿼리를 실행시켜 결과 판단
- 예제
[STUDENT 테이블][
![](https://velog.velcdn.com/images/inss_/post/1f54522e-82e8-41c3-b6f6-7fbd04c5cd4f/image.png)
[DEPARTMENT 테이블]
![](https://velog.velcdn.com/images/inss_/post/6fce73cf-e32d-4a59-aaf9-b3206c68b5dc/image.png)
```SQL
SELECT 
    * 
FROM STUDENT_TABLE A
WHERE 
    EXISTS (SELECT 1
            FROM DEPARTMENT_TABLE B
            WHERE A.department_id = B.department_id)


// 결과
홍길동, 이순신 ROW 출력

NOT EXISTS

• 조건에 맞지 않는 ROW 들만 추출할때

💡 비교

• EXISTS 절이 성능 더 좋음
• EXISTS는 일치하는 행 발견시 테이블 스캔 중지
• IN은 하위 쿼리와 결합하면 서브쿼리를 먼저 처리 한 다음 서브 쿼리 결과를 가지고 메인 쿼리 처리함
• EXISTS -> 서브 쿼리에 데이터가 많을 때, IN -> 데이터가 적거나 작은 연산자를 사용할 때

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

• 처음 풀이

SELECT COUNT(*) AS FISH_COUNT, MAX(LENGTH) AS MAX_LENGTH, FISH_TYPE
FROM(
    SELECT ID, FISH_TYPE, IFNULL(LENGTH, 10) AS LENGTH
    FROM FISH_INFO
) AS SUB
GROUP BY FISH_TYPE
HAVING AVG(LENGTH) >= 33
ORDER BY FISH_TYPE ASC

• 두번째 풀이
  • 생각해보니 MAX 안에 IFNULL 을 넣으면 된다..

    SELECT COUNT(*) AS FISH_COUNT, MAX(IFNULL(LENGTH, 10)) AS MAX_LENGTH, FISH_TYPE
    FROM FISH_INFO
    GROUP BY FISH_TYPE
    HAVING AVG(LENGTH) >= 33
    ORDER BY FISH_TYPE ASC

• 해당 칸이 0이 아니면 -stack이 비어 있지 않고 맨 위의 인형과 같으면 pop 후 +2 -맨 위의 인형과 다르면 추가 add
• 인형을 뽑고 0으로 리셋 후 해당 위치는 다 뽑았으므로 break (😓 처음에 break 깜빡해서 헤맸음)

import java.util.*;

class Solution {
    public int solution(int[][] board, int[] moves) {
        int answer = 0;

        Stack<Integer> stack = new Stack<>();

        int n = board.length;
        for(int move : moves){
            for(int i = 0; i<n; i++){
                int check = board[i][move-1];
                // 해당 칸이 0이 아니면
                if (check != 0) {
                    // stack이 비어 있지 않고 맨 위에 인형이 같으면 pop하고 +2
                    if (!stack.isEmpty() && stack.peek() == check) {
                        stack.pop();
                        answer+=2;
                    } else {  // 같은 인형이 stack에 없으면 add
                        stack.add(check);
                    }
                    // 인형 뽑기 후 0으로 리셋
                    board[i][move-1] = 0;
                    break;
                }
            }
        }
        return answer;
    }
}

✔️ 순열 + TreeSet

• 순열 알고리즘으로 id들 중 불량 id 수대로 뽑음
• 뽑은 id를 불량 id와 매칭
• 일치하면 treeSet에 담아서 정렬하면서 set으로 저장
• 뽑은 id가 불량 id와 맞다면 treeSet의 사이즈가 불량 id 수와 같아야함
• 같으면 hashSet인 answerSet에 treeSet 그대로 넣기 => ["frodo", "crodo"]와 ["crodo", "frodo"]은 하나로 저장해야하기 때문

  import java.util.*;
  

class Solution { static Set<TreeSet> answerSet = new HashSet<>(); public int solution(String[] user_id, String[] banned_id) { String[] output = new String[banned_id.length]; permutation(output, 0, user_id, banned_id, new boolean[user_id.length]); return answerSet.size(); }

// 순열 알고리즘
public void permutation(String[] output, int depth, String[] user_id, String[] banned_id, boolean[] visited){
    if(depth == banned_id.length){
        TreeSet<String> idSet = new TreeSet<>();
        for(int i = 0; i<banned_id.length; i++){
            // 순열로 뽑은 id와 불량 id가 동일한지 확인
            // 동일하면 treeSet에 넣기
            if (check(output[i], banned_id[i])){
                idSet.add(output[i]);
            } 

        }
        // 동일한 id를 담은 idSet의 길이가 불량 id 수와 동일하면 
        // answerSet에 treeMap 형태 그대로
        if (idSet.size() == banned_id.length) {
            answerSet.add(idSet);
        }       
        return;
    }

    for(int i = 0; i<user_id.length; i++){
        if (!visited[i]){
            visited[i] = true;
            output[depth] = user_id[i];
            permutation(output, depth+1, user_id, banned_id, visited);
            visited[i] = false;
        }
    }
}

// 순열로 뽑은 id와 불량 id가 매칭되는지 확인
public boolean check(String output, String banned_id){ 
    if (output.length() != banned_id.length()) return false;
    for(int i = 0; i<output.length(); i++){
        if (banned_id.charAt(i) == '*') continue;
        if (output.charAt(i) != banned_id.charAt(i)) {
            return false;
        }
    }
    return true;
}

}

</br>
</br>
🫥 처음에는 조합으로 고르고 어떻게 매칭할지를 계속 고민했음. 그냥 순열로 처음부터 뽑고 그대로 매칭시켜보면 해결됐던 문제!!

</br>
</br>

✔️ substring, 정규표현식 기억하기!!!

• 바깥 중괄호 두개 제거 후 "},{" 기준으로 split -> substring 사용 -> }와 {은 정규표현식 사용 => ex. {{1,2},{1,2,3}} -> 1,2 / 1,2,3
• 분리된 튜플 배열에서 튜플 길이 기준으로 오름차순 정렬
• 튜플 배열 하나씩 "," 기준으로 분리 후 arrayList에 넣기, 넣을 때 arrayList에 그 값이 포함되어있지 않으면 넣기
• ArrayList에서 int 배열로 변환

import java.util.*;
class Solution {
    public int[] solution(String s) {
        List<Integer> list = new ArrayList<>();

        // 바깥의 중괄호 두개 제거 후 "},{" 기준으로 분리
        String[] tuples = s.substring(2, s.length()-2).split("\\},\\{");
        // 분리된 tuple 배열에서 길이 기준으로 오름차순 정렬
        Arrays.sort(tuples, (a, b) -> a.length() - b.length());

        // tuple 배열 하나씩 "," 기준으로 분리 후 arrayList에 넣기
        for(String tuple : tuples){
            String[] tt = tuple.split(",");
            for(String t : tt){
                int num = Integer.parseInt(t);
                if (!list.contains(num)){
                    list.add(num);
                }
            }
        }
        // ArrayList -> int 배열로 변환
        int[] answer = new int[list.size()];
        int idx = 0;
        for(int tuple : list){
            answer[idx++] = tuple;
        }
        return answer;
    }
}

🚨 첫번째 실패 코드

• 바깥 중괄호 하나만 제거 후 "," 기준으로 split -> 당연히 {1 / 2 / 3} / {4} 이런식으로 분리됨.. -> 원래 생각했던건 {1, 2} / {2} 이렇게 분리된 각 튜플 배열을 또 중괄호 없애고 ","로 분리하려고 했음 -> 그냥 이런 문자열은 헷갈리니까 적으면서 하자...!!!

  public int[] solution(String s) {
        List<Integer> list = new ArrayList<>();
  
        String[] tuples = s.substring(1, s.length()-1).split(",");
  
        // tuple 배열 하나씩 "," 기준으로 분리 후 arrayList에 넣기
        for(String tuple : tuples){
            String[] tt = tuple.substring(1, s.length()-1).split(",");
            for(String t : tt){
                int num = Integer.parseInt(t);
  
                list.add(num);
                }
            }
        }
  
       ...
  }

  
  
  

🚨 두번째 실패 코드

• 각 튜플의 길이대로 정렬을 안하고 하니까 결과 배열 원소값은 똑같은데 순서가 달라서 틀림
• 문제를 정확히 이해못해서 이렇게 푼듯.. (똑바로 보잣)

• parent 해시맵에 판매원과 추천인 넣기
• seller과 amount 배열 하나씩 계산 함수 실행 (calculate)
• 해당 판매원의 money 해시에 이익 계산해서 넣기
• parent 해시에서 그 판매원의 추천인 찾아서(containsKey) 재귀로 10% 계산 실행

import java.util.*;

class Solution {
    Map<String, String> parent = new HashMap<>();
    Map<String, Integer> money = new HashMap<>();

    public int[] solution(String[] enroll, String[] referral, String[] seller, int[] amount) {
        // 판매원과 추천인 정보 넣기
        for(int i = 0; i<enroll.length; i++){
            parent.put(enroll[i], referral[i]);
        }

        for(int i = 0; i<seller.length; i++){
            calculate(seller[i], amount[i] * 100);
        }

        int[] answer = new int[enroll.length];
        for(int i = 0; i<enroll.length; i++){
            answer[i] = money.getOrDefault(enroll[i], 0);
        }
        return answer;
    }

    void calculate(String curr, int sales){
        int nextSales = sales / 10;
        money.put(curr, money.getOrDefault(curr, 0) + sales - nextSales);

        if(nextSales > 0 && parent.containsKey(curr)){
            calculate(parent.get(curr), nextSales);
        }
    }
}

🫥 문제가 어려워서 다른 사람 풀이 참고했는데 생각보다 쉬웠던 문제

• 생성된 정점과 각 그래프의 특징을 찾으면 되는 문제
• 생성된 정점 : in은 무조건 0, out은 2개 이상
• 막대 모양 그래프 : out이 0인 정점이 있음 (마지막 정점)
• 8자 모양 그래프 : out이 2개 이상인 정점중에 in이 존재하는 정점
• 도넛 모양 그래프 : 생성된 정점의 out 간선 수 - 막대 그래프 - 8자 그래프
• 각 정점의 in과 out 간선 수를 각각 hashMap에 넣고 조건에 맞게 생성된 정점과 그래프 수 찾으면 됨

import java.util.*;

class Solution {
    public int[] solution(int[][] edges) {
        int[] result = new int[4];
        HashMap<Integer, Integer> in = new HashMap<>();
        HashMap<Integer, Integer> out = new HashMap<>();

        // 각 정점마다 in 간선과 out 간선 count 
        for(int[] edge : edges){ // a -> b
            int a = edge[0];
            int b = edge[1];
            in.put(b, in.getOrDefault(b, 0) + 1);
            out.put(a, out.getOrDefault(a, 0) + 1);
        }


        for(int o : out.keySet()){
            if (out.get(o) >= 2){
                // 생성된 정점 찾기
                if (!in.containsKey(o)){
                    result[0] = o;
                 } else { // 8자 모양 그래프 찾기
                    result[3] += 1;
                }
            }

        }
        // 막대 모양 그래프 찾기
        for(int i : in.keySet()){
            if (!out.containsKey(i)) result[2] += 1;
        }

        result[1] = out.get(result[0]) - result[2] - result[3];

        return result;
    }
}

• 끊을 전선 하나씩 고르고 그 전선 제외하고 인접 리스트 생성(createList)
• 생성 후 인접 리스트에 전선 정보 넣기 -> bfs 실행
• bfs 실행해서 노드 수 count하고 두 전력망의 송전탑 개수 차이를 반환
• 가장 작은 차이가 정답

  import java.util.*;
  

class Solution { static ArrayList<ArrayList> graph; public int solution(int n, int[][] wires) { int answer = Integer.MAX_VALUE; for(int i = 0; i<wires.length; i++){ createList(n);

        // 해당 전선(wires[i]) 제외하고 인접 리스트에 넣기
        for(int j = 0; j<wires.length; j++){
            if (j == i) continue;
            int[] curr = wires[j];
            graph.get(curr[0]).add(curr[1]);
            graph.get(curr[1]).add(curr[0]);
        }
        // bfs 실행
        answer = Math.min(checkBfs(n), answer);
    }
    return answer;
}

// 인접 리스트 생성
public void createList(int n){
    graph = new ArrayList<>();
    for(int i = 0; i<=n; i++){
        graph.add(new ArrayList<>());
    }
}

public int checkBfs(int n){
    int cnt = 1;
    Queue<Integer> q = new LinkedList<>();
    boolean[] visited = new boolean[n+1];

    q.add(1);
    visited[1] = true;

    while(!q.isEmpty()){
        int curr = q.poll();
        for(int i : graph.get(curr)){
            if(!visited[i]){
                q.add(i);
                visited[i] = true;
                cnt++;
            }
        }
    }
    // cnt : bfs로 찾은 노드 count 
    // 두 전력망 차이 반환
    return Math.abs(2 * cnt - n);
}

} ```

✔️ 조합 + BFS

• 조합 알고리즘으로 빈칸 중 벽 세울 곳 3군데 구하기
• 빈칸 3곳을 골랐으면 bfs 실행
• 나중에 arr 원상복구 시키기 위해 바이러스 감염된 곳은 따로 좌표 보관(newVirus)
• 빈칸 수 count
• 바이러스 새롭게 감염된 곳 다시 빈칸으로 복구

  import java.io.BufferedReader;
  import java.io.IOException;
  import java.io.InputStreamReader;
  import java.util.ArrayList;
  import java.util.LinkedList;
  import java.util.List;
  import java.util.Queue;
  import java.util.StringTokenizer;
  

public class Main { static int n, m; static int[][] arr; static Queue<int[]> q = new LinkedList<>(); static int[] dx = {1, -1, 0, 0}; static int[] dy = {0, 0, 1, -1}; static int result = 0;

public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st = new StringTokenizer(br.readLine());
    n = Integer.parseInt(st.nextToken());
    m = Integer.parseInt(st.nextToken());
    arr = new int[n][m];
    for(int i = 0; i<n; i++){
        st = new StringTokenizer(br.readLine());
        for(int j = 0; j<m; j++){
            arr[i][j] = Integer.parseInt(st.nextToken());
        }
    }
    combination(0, 0);
    System.out.println(result);
}

public static void combination(int start, int depth){
    // 조합 알고리즘으로 빈칸 중에 3곳 벽으로 처리하고 bfs 실행
    if (depth == 3){
        result = Math.max(result, bfs());
        return;
    }

    for(int i = start; i<n*m; i++){
        int x = i / m;
        int y = i % m;

        if (arr[x][y] != 0) continue;

        arr[x][y] = 1;
        combination(i+1, depth+1);
        arr[x][y] = 0;
    }
}

public static int bfs(){
    int cnt = 0;
    List<int[]> newVirus = new ArrayList<>(); // 바이러스 감염된 좌표 저장 -> 원상복구때 필요
    // bfs 실행
    for(int i = 0; i<n; i++){
        for(int j = 0; j<m; j++){
            if (arr[i][j] == 2){
                q.add(new int[]{i, j});
            }
        }
    }

    while(!q.isEmpty()){
        int[] curr = q.poll();
        for(int i = 0; i<4; i++){
            int nx = curr[0] + dx[i];
            int ny = curr[1] + dy[i];

            if (nx >= 0 && nx < n && ny >= 0 && ny < m){
                if (arr[nx][ny] == 0){
                    arr[nx][ny] = 2;
                    q.add(new int[]{nx, ny});
                    newVirus.add(new int[]{nx, ny});
                }
            }
        }
    }

    // 빈칸 count
    for(int i = 0; i<n; i++){
        for(int j = 0; j<m; j++){
            if (arr[i][j] == 0){
                cnt++;
            }
        }
    }
    // 바이러스 감염된 곳 다시 빈칸으로 원상복구
    for(int[] v : newVirus){
        arr[v[0]][v[1]] = 0;
    }
    return cnt;
}

} ```

• 서류 순위 기준으로 오름차순
• 맨 앞에 있는 사람은 무조건 채용
• 두번째 사람부터 면접 순위가 앞사람들보다 높은지 확인

  import java.io.BufferedReader;
  import java.io.IOException;
  import java.io.InputStreamReader;
  import java.util.Arrays;
  import java.util.StringTokenizer;
  

public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int T = Integer.parseInt(br.readLine()); for(int t= 0; t<T; t++){ int n = Integer.parseInt(br.readLine()); int[][] scores = new int[n][2]; // 순위 입력 for(int i = 0; i<n; i++){ StringTokenizer st = new StringTokenizer(br.readLine()); scores[i][0] = Integer.parseInt(st.nextToken()); scores[i][1] = Integer.parseInt(st.nextToken()); }

        int result = 1;
        // 서류 성적 순위 기준으로 오름차순
        Arrays.sort(scores, (a, b) -> Integer.compare(a[0], b[0]));
        int prevMin = scores[0][1];
        // 앞에 면접 순위 중 가장 작은 순위랑 비교해서 작으면 result +1
        for(int i = 1; i<n; i++){
            if (prevMin > scores[i][1]) {
                result++;
                prevMin = scores[i][1];
            }
        }
        System.out.println(result);
    }
}

}

</br>
</br>

###  🚨시간초과
- 면접 순위 확인하는 코드에서 이중 for문으로 시간초과
- 앞에 사람들을 하나씩 확인하는게 아니라 앞 사람들 중 높은 순위를 계속 갱신하고 그걸 기준으로 확인
```java
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());
        for(int  t= 0; t<T; t++){
            int n = Integer.parseInt(br.readLine());
            int[][] scores = new int[n][2];
            for(int i = 0; i<n; i++){
                StringTokenizer st = new StringTokenizer(br.readLine());
                scores[i][0] = Integer.parseInt(st.nextToken());
                scores[i][1] = Integer.parseInt(st.nextToken());
            }

            int result = 1;
            Arrays.sort(scores, (a, b) -> Integer.compare(a[0], b[0]));
            for(int i = 1; i<n; i++){
                int cnt = 0;
                for(int j = i-1; j>=0; j--){
                    if (scores[i][1] < scores[j][1]) cnt++;
                }
                if (cnt == i) result++;
            }
            System.out.println(result);
        }

    }
}