1. 원래 계획은

배포를 서버리스,,로 Terraform 을 사용해보는 거였어요!

근데 해커톤이기도 하고 모르는 걸 시도해보기엔 리스크가 큰 것 같아서

그냥 기존에 하던 방식으로 하기루,,

응 늘 먹던 맛이군

VPC 환경 위에 구축한다는 게 뭔 소린가 했더니

그냥 EC2 상에서 배포하는 거더라구요?

응 바로 뽀또뽀또라이즈 파이프라인 긁어와~~

근데 인프라 구성도

아니 이게 그렇게 별론가

이거 보냈다가 그림판으로 그리지말라고 진짜 ㅈㄹㅈㄹ 개질알을..  공개저격 당했음;;

아니 화살표는 그림판을 사용하긴 했지만

애초에 뭐 올리는 게 서버밖에 없는데 뭔 아키텍쳐를 그려요

진짜 모르겠어서 물어보니깐 JPA랑 인텔리제이랑 넣으라는데

하.....................의미있나 모르겠다 ㅋ

아무튼

RDS를 처음 사용해봤어요.

트러블슈팅 1 - RDS 가 EC2에서는 접속이 되나 그 외 모든 곳에서 접속 불가

ㅋㅋ

진짜 정신 나가는 줄 알았음

이거만 3시간 붙잡았어

내가 진짜 뭐 잘못설정했나 싶어서

인바운드 아웃바운드 다 확인하고

보안 그룹도 5개나 새로 만들어서 계속 해봤는데

안되는거지...

나중엔 진짜 도저히 모르겠어서

퍼블릭엑세스도 열어봤는데도 안되..더라고요

결론은

MySQL 비밀번호에 ! 특수기호가 있던 것이 원인이였습니다

ㅋㅋ

뭐 익스케이프 처리가 안되는건지

진짜 짜증나네..............아무튼 ! 빼니깐 너무 잘되더라 역시 잠깐 쓸거면 root 1234를............

그리고

트러블슈팅 2 - Swagger 500 에러 : API 확인 불가

그냥 이해가 안감

왜 잘되던 Swagger가 갑자기,,, 내부 500 에러가 뜨는 것인가.

다른 API에 문제가 있던 건 아니고요

그냥 Swagger도 잘 돌아가는데
Swagger 내에서 API 를 Docs화하지 못하는 거였음.

이유가 뭔지 찾아봤다가

"GlobalHandlerException" 선언했을 때 @RestControllerAdvice 가 문제였고요.

일단 이건 알아냈는데

진짜 GPT랑 아무리 머리를 맞대도 해결이 안되는거임;;

근데 상대는 누구? 조수욘

이미 github secrets에서 json파일로 gpt한테 후두려 맞은 여자

바로 gpt버리고 구글링했더니 바로 찾은 해결방안...

문제의 원인은 바로

"Swagger와 Springboot 3.2.X? 였나 암튼

버전이 충돌난다~"
였습니다... 일안하나

아무튼 그냥 버전 충돌로 인한거였구

해결방안은 @RestControllerAdvice 위에

Swagger 내의 어노테이션인 @Hidden 을 추가로 붙여주면 잘 된다,,~~는 거였어요

그리고 진짜 잘 됨. ㅋㅋ

그쵸 아무리 생각해도

모든 에러를 500 Internal server error로 띄우기는

너무 간지가 살지 않았음...

간지추구코딩녀가 결국 성공하는 법이지

암튼 이상합니다..아니 이상입니다...

개발이나 코드 부분에서는

다음 이 시간에....to be continue

import java.util.*;

/**
  테스트 1 〉 통과 (15.28ms, 110MB)
  테스트 2 〉 통과 (58.95ms, 105MB)
  테스트 3 〉 통과 (12.50ms, 105MB)
  테스트 4 〉 통과 (45.74ms, 127MB)
  테스트 5 〉 통과 (43.97ms, 102MB)
  테스트 6 〉 통과 (7.43ms, 78.6MB)
  테스트 7 〉 통과 (30.60ms, 103MB)
  테스트 8 〉 통과 (63.70ms, 128MB)
  테스트 9 〉 통과 (16.12ms, 111MB)
  테스트 10 〉 통과 (63.72ms, 119MB)
  테스트 11 〉 통과 (10.15ms, 90.4MB)
  테스트 12 〉 통과 (0.07ms, 85.3MB)
*/

class Solution {
    public int solution(String[] want, int[] number, String[] discount) {
        int answer = 0;
        
        Map<String, Integer> ori = new HashMap<>();
        Map<String, Integer> window = new HashMap<>();
        for(int i=0;i<want.length;i++) {
            ori.put(want[i], number[i]);

        }
        
        for(int i=0;i<10;i++) {
            window.put(discount[i], window.getOrDefault(discount[i], 0)+1);            
        }

        boolean aa = true;
        for(String key : ori.keySet()) {
            if(window.getOrDefault(key, 0) < ori.get(key)) aa= false;
        }
        
        if(aa) answer++;
        
        f : for(int i=10;i<discount.length;i++) {
            
            window.put(discount[i-10], window.get(discount[i-10])-1);
            if(window.get(discount[i-10]) == 0) window.remove(discount[i-10]);
            
            window.put(discount[i], window.getOrDefault(discount[i], 0)+1);
            
            for(String key : ori.keySet()) {
                if(window.getOrDefault(key, 0) < ori.get(key)) continue f;
            }
            answer++;
        }
        
        return answer;
    }
}

import java.util.*;
/**
  테스트 1 〉	통과 (0.35ms, 82.7MB)
  테스트 2 〉	통과 (0.61ms, 84.4MB)
  테스트 3 〉	통과 (0.83ms, 72.8MB)
  테스트 4 〉	통과 (0.65ms, 85MB)
  테스트 5 〉	통과 (0.57ms, 78.7MB)
  테스트 6 〉	통과 (0.44ms, 87MB)
  테스트 7 〉	통과 (1.81ms, 79.7MB)
  테스트 8 〉	통과 (3.55ms, 84.3MB)
  테스트 9 〉	통과 (0.39ms, 83.6MB)
  테스트 10 〉	통과 (0.29ms, 75.1MB)
  테스트 11 〉	통과 (1.30ms, 72.4MB)
  테스트 12 〉	통과 (2.85ms, 79.9MB)
  테스트 13 〉	통과 (4.63ms, 78MB)
  테스트 14 〉	통과 (2.66ms, 82.7MB)
  테스트 15 〉	통과 (0.90ms, 83.6MB)
  테스트 16 〉	통과 (8.05ms, 75.6MB)
  테스트 17 〉	통과 (12.72ms, 91MB)
  테스트 18 〉	통과 (0.83ms, 76.3MB)
  테스트 19 〉	통과 (0.64ms, 74.5MB)
  테스트 20 〉	통과 (7.15ms, 73.9MB)
  테스트 21 〉	통과 (2.40ms, 81.5MB)
  테스트 22 〉	통과 (0.79ms, 94.1MB)
  테스트 23 〉	통과 (0.35ms, 89MB)
**/
class Solution {
    static char[][] arr;
    static int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};
    
    static class Loc {
        int x, y;
        
        Loc(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
    
    public int solution(String[] maps) {
        
        arr = new char[maps.length][maps[0].length()];
        Queue<Loc> queue = new ArrayDeque<>();
        
        for(int i=0;i<maps.length;i++) {
            arr[i] = maps[i].toCharArray();
            for(int j=0;j<arr[i].length;j++) {
                if(arr[i][j] == 'S') {
                    queue.offer(new Loc(i, j));
                }
            }
        }
        
        int time = 0;
        boolean pulled = false;
        boolean[][] visited = new boolean[arr.length][arr[0].length];
        
        // 레버 올리기
        while(!pulled && !queue.isEmpty()) {
            time++;
            Queue<Loc> newQueue = new ArrayDeque<>();
            
            c: while(!queue.isEmpty()) {
                Loc loc = queue.poll();
                if(visited[loc.x][loc.y]) continue;
                visited[loc.x][loc.y] = true;
                
                for(int i=0;i<4;i++) {
                    int x = loc.x + dx[i], y = loc.y + dy[i];
                    if(!isInRange(x, y) || visited[x][y] || arr[x][y] == 'X') continue;
                    
                    if(arr[x][y] == 'L') {
                        newQueue.clear();
                        newQueue.offer(new Loc(x, y));
                        pulled = true;
                        break c;
                    }

                    
                    newQueue.offer(new Loc(x, y));
                }
            }

            queue = newQueue;
            
        }
        
        if(!pulled) return -1;
        visited = new boolean[arr.length][arr[0].length];
        
        // 출구 찾기
        while(!queue.isEmpty()) {
            
            time++;
            Queue<Loc> newQueue = new ArrayDeque<>();
            
            while(!queue.isEmpty()) {
                Loc loc = queue.poll();
                // System.out.println(loc.x+" "+loc.y);
                if(visited[loc.x][loc.y]) continue;
                visited[loc.x][loc.y] = true;
                
                for(int i=0;i<4;i++) {
                    int x = loc.x + dx[i], y = loc.y + dy[i];
                    if(!isInRange(x, y) || visited[x][y] || arr[x][y] == 'X') continue;
                    
                    if(arr[x][y] == 'E') {
                        return time;
                    }
                    
                    newQueue.offer(new Loc(x, y));
                }
            }           
            queue = newQueue;
        }
        
        return -1;
    }
    
    static boolean isInRange(int x, int y) {
        return 0 <= x && x < arr.length && 0 <= y && y < arr[0].length;
    }
}

import java.util.*;

/**
  테스트 1 〉 통과 (0.02ms, 73.7MB)
  테스트 2 〉 통과 (0.02ms, 81.8MB)
  테스트 3 〉 통과 (0.02ms, 93MB)
  테스트 4 〉 통과 (0.08ms, 73.3MB)
  테스트 5 〉 통과 (0.68ms, 97.1MB)
  테스트 6 〉 통과 (0.92ms, 78.1MB)
  테스트 7 〉 통과 (1.79ms, 88.4MB)
  테스트 8 〉 통과 (2.52ms, 77.9MB)
  테스트 9 〉 통과 (12.39ms, 86.3MB)
  테스트 10 〉 통과 (11.06ms, 133MB)
  테스트 11 〉 통과 (12.38ms, 126MB)
  테스트 12 〉 통과 (10.15ms, 124MB)
  테스트 13 〉 통과 (19.70ms, 122MB)
  테스트 14 〉 통과 (14.05ms, 139MB)
  테스트 15 〉 통과 (14.80ms, 137MB)
  테스트 16 〉 통과 (6.80ms, 140MB)
  테스트 17 〉 통과 (8.43ms, 121MB)
  테스트 18 〉 통과 (0.01ms, 73.3MB)
  테스트 19 〉 통과 (0.02ms, 76.4MB)
  테스트 20 〉 통과 (0.02ms, 92.6MB)
  테스트 21 〉 통과 (0.02ms, 86.7MB)
  테스트 22 〉 통과 (0.02ms, 72.6MB)
  테스트 23 〉 통과 (0.02ms, 73.3MB)
  테스트 24 〉 통과 (8.87ms, 129MB)
  테스트 25 〉 통과 (5.05ms, 122MB)
  테스트 26 〉 통과 (6.71ms, 124MB)
  테스트 27 〉 통과 (6.67ms, 143MB)
  테스트 28 〉 통과 (9.39ms, 124MB)
  테스트 29 〉 통과 (9.20ms, 144MB)
  테스트 30 〉 통과 (10.53ms, 128MB)
  테스트 31 〉 통과 (0.01ms, 85.3MB)
  테스트 32 〉 통과 (0.01ms, 69.4MB)
  테스트 33 〉 통과 (0.01ms, 79.3MB)
  테스트 34 〉 통과 (0.02ms, 73.2MB)
**/

class Solution {
    public int[] solution(int[] sequence, int k) {
        
        int length = Integer.MAX_VALUE;
        int startIdx = -1, endIdx = -1;
        
        int start = 0, end = 0, sum = 0;
        
        while(end < sequence.length) {
            sum += sequence[end++];
            
            while(sum > k && start < end) {
                sum -= sequence[start++];
            }
            
            if(sum == k && length > end - start) {
                length = end - start;
                startIdx = start;
                endIdx = end-1;
            }
            
            
        }
        
        return new int[]{startIdx, endIdx};
    }
}

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

import java.util.*;

/**

    테스트 1 〉	통과 (8.41ms, 89.2MB)
    테스트 2 〉	통과 (7.23ms, 86.9MB)
    테스트 3 〉	통과 (8.58ms, 92.2MB)
    테스트 4 〉	통과 (8.04ms, 86.9MB)
    테스트 5 〉	통과 (9.12ms, 84.4MB)
    테스트 6 〉	통과 (13.46ms, 76.7MB)
    테스트 7 〉	통과 (7.15ms, 87.2MB)
    테스트 8 〉	통과 (7.34ms, 81.1MB)
    테스트 9 〉	통과 (10.70ms, 90.2MB)
    테스트 10 〉	통과 (9.32ms, 84.1MB)
    테스트 11 〉	통과 (8.33ms, 81.3MB)
    테스트 12 〉	통과 (9.85ms, 72.7MB)
    테스트 13 〉	통과 (10.36ms, 79.9MB)
    테스트 14 〉	통과 (6.95ms, 79.9MB)
    테스트 15 〉	통과 (9.31ms, 75.7MB)
    테스트 16 〉	통과 (7.38ms, 81.3MB)
    테스트 17 〉	통과 (8.24ms, 83.1MB)
    테스트 18 〉	통과 (11.41ms, 90.3MB)
    테스트 19 〉	통과 (12.52ms, 76.5MB)
    테스트 20 〉	통과 (16.39ms, 92.8MB)
    테스트 21 〉	통과 (9.73ms, 85.1MB)
    테스트 22 〉	통과 (10.66ms, 72.7MB)
    테스트 23 〉	통과 (0.08ms, 72.2MB)
    테스트 24 〉	통과 (10.36ms, 94.8MB)
    테스트 25 〉	통과 (0.05ms, 86.5MB)
    테스트 26 〉	통과 (0.08ms, 84.2MB)
    테스트 27 〉	통과 (10.00ms, 83.8MB)
    테스트 28 〉	통과 (0.15ms, 73.7MB)
    테스트 29 〉	통과 (10.99ms, 85.6MB)
    테스트 30 〉	통과 (10.33ms, 73.8MB)
    테스트 31 〉	통과 (8.54ms, 91.8MB)


**/

class Solution {
    public static int[] dx = {-1, 0, 1, 0}, dy = {0, 1, 0, -1};
    public char[][] arr = new char[5][5];
    
    public static boolean isInRange(int x, int y) {
        return 0 <= x && x< 5 && 0 <= y && y < 5;
    }
    
    public List<Integer> solution(String[][] places) {
        List<Integer> ans = new ArrayList<>();
        
        testcase : for(int t =0; t< places.length; t++) {
            
            for(int i=0;i<5;i++) {
                arr[i] = places[t][i].toCharArray();
            }
            
            for(int i=0;i<5;i++) {
                for(int j=0;j<5;j++) {
                    if(arr[i][j] == 'P') {
                        // 거리 체크

                        Queue<int[]> check = new ArrayDeque<>();
                        
                        for(int idx=0;idx<4;idx++) {
                            int x = i+dx[idx], y = j+dy[idx];
                            if(isInRange(x, y) && arr[x][y] == 'P') {
                                System.out.println(x+" "+y);
                                ans.add(0); continue testcase;
                            }
                            
                            else if(isInRange(x, y) && arr[x][y] == 'O') {
                                check.add(new int[] {x, y, idx});
                            }
                            
                        }
                        
                        while(!check.isEmpty()) {
                            int[] loc = check.poll();
                            
                            for(int idx=0;idx<4; idx++) {
                                if(idx == 0 && loc[2] == 2) {
                                    continue;
                                }
                                if(idx == 2 && loc[2] == 0) {
                                    continue;
                                }
                                if(idx == 1 && loc[2] == 3) {
                                    continue;
                                }
                                if(idx == 3 && loc[2] == 1) {
                                    continue;
                                }
                                
                                int x = loc[0]+dx[idx], y = loc[1]+dy[idx];
                                if(isInRange(x, y) && arr[x][y] == 'P') {
                                    System.out.println(x+" "+y);
                                    ans.add(0); continue testcase;
                                }
                            }
                        }

                    }
                }
            }
            ans.add(1);
        }
        

        
        return ans;
    }
}

CHAPTER 14 인덱싱

1. 기본 개념 (Basic Concepts)

• 인덱스(Index) 역할

  • 책의 색인과 유사: 원하는 정보를 빠르게 찾기 위한 “검색 가속” 구조
  • 테이블 전체를 모두 읽지 않고도 필요한 레코드를 찾아갈 수 있음

• 인덱스 필요성

  • 대규모 데이터를 전부 탐색(Full Scan)하지 않고 원하는 정보만 효율적으로 조회
  • 예) 특정 학생의 레코드만 조회할 때, 인덱스를 통해 빠른 접근 가능

• 단순 정렬 리스트의 한계

  • 인덱스 자체가 커질 수 있고, 검색 시간도 여전히 오래 걸릴 수 있음
  • 삽입·삭제 시 재정렬 등의 유지 비용이 매우 큼

• 인덱스의 기본 형태

  • 순서 인덱스(Ordered Indices)
    • 데이터 값을 정렬된 순서로 유지
    • 범위 검색(Range Query)에 유리
  • 해시 인덱스(Hash Indices)
    • 해시 함수를 통해 데이터를 균등하게 분산
    • 완전 일치 검색(Exact Match) 쿼리에 특히 효율적

• 인덱스 선택 시 고려사항

  • 검색(Access) 유형: 정확히 일치하는 값 검색인지, 범위 검색인지
  • 검색 시간(Access Time): 원하는 레코드에 도달하는 데 걸리는 시간
  • 삽입 시간(Insertion Time): 새로운 레코드를 인덱스에 반영하는 데 드는 시간
  • 삭제 시간(Deletion Time): 기존 레코드를 삭제하는 데 드는 시간
  • 추가 공간(Space Overhead): 인덱스 유지를 위해 필요한 추가 저장소

• 다중 인덱스(Multiple Indices)

  • 하나의 테이블에 여러 개의 인덱스를 둘 수 있음
  • 예) 도서 테이블에서 저자, 제목, 주제 각각에 대해 인덱스 생성

• 검색 키(Search Key)

  • 인덱스를 통해 레코드를 찾을 때 사용하는 속성(또는 속성들의 집합)
  • 기본 키나 후보 키가 아니라도, 검색을 위해 사용되는 속성이면 모두 검색 키가 될 수 있음

2. 순서 인덱스 (Ordered Indices)

1. 밀집 인덱스(Dense Index)와 희소 인덱스(Sparse Index)

1.1 밀집 인덱스 (Dense Index)

• 모든 검색 키에 대해 인덱스 엔트리가 존재
• 인덱스 엔트리는 (검색 키 값, 레코드(들)에 대한 포인터)로 구성
• 클러스터링/논클러스터링 여부와 상관없이 각 값에 대한 포인터 목록 관리 가능

장단점

• 장점: 원하는 레코드를 직접 찾아가기 쉬워 검색 속도 빠름
• 단점: 인덱스 크기가 커지고, 삽입/삭제 시 유지 비용이 큼

1.2 희소 인덱스 (Sparse Index)

• 일부 검색 키에 대해서만 인덱스 엔트리를 생성
• 테이블(파일)이 검색 키 순으로 물리적으로 정렬(클러스터링)되어 있어야 사용 가능
• 인덱스 엔트리는 (검색 키 값, 해당 레코드가 존재하는 최초 블록 포인터) 형태
• 원하는 검색 키가 인덱스에 없을 경우, 직전에 해당하는 검색 키 엔트리부터 순차적으로 스캔하여 레코드 탐색

장단점

• 장점: 인덱스 크기가 작고, 삽입/삭제 시 유지 비용이 상대적으로 적음
• 단점: 직접 포인터가 없으므로 추가 스캔 필요 → 밀집 인덱스보다 검색 속도 낮을 수 있음

2. 다단계 인덱스(Multilevel Indices)

• 인덱스가 매우 커서 메모리에 전부 적재 불가능할 때 사용
• 인덱스를 “파일”로 보고, 그 위에 또 다른 희소 인덱스(Outer Index) 를 씌움
  • 예: 내부 인덱스(Inner Index) → 외부 인덱스(Outer Index) → …
• 장점: 검색 시 상위 레벨 인덱스(작은 크기)를 통해 빠른 범위 축소, 디스크 I/O 횟수 크게 감소
• 구현: B+-트리 구조(14.3절)로 자주 구현

3. 인덱스 갱신(Index Update)

3.1 삽입(Insertion)

1. 밀집 인덱스
   • 새 검색 키가 기존에 없으면, 인덱스 엔트리 추가
   • 기존에 있으면, 해당 인덱스 엔트리의 포인터 리스트에 새 레코드 포인터 추가
2. 희소 인덱스
   • 새로운 블록이 생성된 경우, 그 블록의 첫 번째 검색 키 값을 인덱스에 추가
   • 기존 블록에 삽입 시, 가장 작은 값이 변경되면 인덱스 갱신

3.2 삭제(Deletion)

1. 밀집 인덱스
   • 해당 검색 키를 갖는 레코드가 더 이상 없다면, 인덱스 엔트리 자체 삭제
   • 검색 키가 여전히 남아 있다면, 인덱스 엔트리의 포인터 목록에서 해당 포인터만 제거
2. 희소 인덱스
   • 삭제된 레코드의 검색 키가 인덱스에 없으면 아무 일도 하지 않음
   • 해당 검색 키가 인덱스에 있고, 그 키에 대한 레코드가 더 이상 없으면 인접 키로 대체하거나 제거

다단계 인덱스에서도 동일 원리 적용 (최하위 인덱스 갱신 → 상위 인덱스가 그 인덱스를 “파일”로 보고 동일한 갱신 수행)

4. 보조(논클러스터링) 인덱스(Secondary Indices)

• 테이블의 물리적 정렬 순서와 다른 속성(또는 속성 집합)에 대한 인덱스
• 항상 밀집 인덱스 형태이어야 함
  • 테이블이 해당 키 순으로 정렬되어 있지 않으므로, 희소 인덱스로는 중간값들을 찾기 어려움
• 후보 키가 아닌 속성(중복 가능)을 인덱스 키로 사용할 경우, 한 키 값에 여러 레코드 → 각 레코드로 가는 포인터 리스트 관리 필요
• 장점: 클러스터링 인덱스로 처리 불가능한 속성 조건의 검색 속도 향상
• 단점: 인덱스 유지(삽입/삭제) 부담 증가, 디스크 공간 추가 소모

5. 다중 키 인덱스(Composite Keys)

• 인덱스의 검색 키가 여러 속성으로 이루어진 경우
  • 예: (course_id, semester, year)
• 사전식(lexicographic) 정렬 사용
  • 예) (a1, a2) < (b1, b2) 은 a1 < b1 이거나 a1 = b1이고 a2 < b2일 때 성립
• 다중 속성 검색, 결합 조건(query)에 유리

3. B+-트리 인덱스 파일 (B+-Tree Index Files)

1. 배경

• Index-Sequential 방식의 단점: 데이터 양이 커지면 정렬 순서 유지 비용 증가(삽입·삭제에 따른 재조직화 비용 큼).
• B+-트리: 삽입·삭제 시에도 균형(Balanced) 을 유지해, 재조직화 없이 효율적인 인덱싱 가능.
  • 모든 리프(leaf)까지의 경로 길이가 동일 → 균형 트리
  • 노드 간 포인터 개수(child 수)가 일정 범위(⌈n/2⌉ ~ n)를 유지

2. B+-트리 구조

2.1 노드 구조

• 리프 노드(leaf node)
  • 최대 (n-1)개의 검색 키와 (n-1)개의 레코드 포인터 보관
  • 추가로 오른쪽 리프를 가리키는 포인터(Pn)가 있어 리프들끼리 연결 리스트 형태 유지 (순차 접근 편의)
• 비리프(내부) 노드(internal node)
  • 최대 n개의 자식 포인터 보관 (최소 ⌈n/2⌉개 보관)
  • 검색 키들은 자식 범위를 나누는 기준 값

2.2 균형 트리

• 루트(root)에서 리프까지의 높이가 동일 (균형)
• 노드가 반쯤 차 있어도(최소 ⌈n/2⌉ 포인터/값) 재분배나 합병으로 유지 가능 → 삽입·삭제 시에도 트리 높이가 크게 변하지 않음

2.3 중복 키

• 보통은 (검색 키 + 유일 속성) 으로 복합 키(composite key)를 생성해 중복을 제거
• 실제 구현에서 Record ID, Primary Key 등을 추가하여 검색 키를 유일하게 만듦
  • 삭제 시, 특정 레코드를 유일 키로 바로 찾을 수 있어 효율적

3. B+-트리를 이용한 연산

3.1 검색 (Lookup)

1. 루트 노드부터 시작, 현재 노드에서 검색 키 범위를 확인하며 적절한 자식 포인터를 따라감
2. 리프 노드까지 내려간 후, 해당 리프 내에서 검색 키를 찾아 레코드 포인터 획득
3. (일치 키가 없으면) 해당 레코드가 존재하지 않음

• 범위 질의(Range Query)
  • 시작 값(lb)에 해당하는 리프 노드까지 내려간 뒤, 리프들을 순차로 따라가며 ub 이하의 모든 키 수집

3.2 삽입 (Insertion)

1. 삽입 위치(리프 노드) 찾은 후, 노드에 공간이 있으면 바로 삽입
2. 노드가 꽉 차면(split) 반을 나누어 새 노드를 만든 뒤, 상위 부모 노드에 새 노드 포인터와 경계 키 삽입
3. 부모 노드 역시 꽉 차면 재귀적으로 스플릿(split) 진행
4. 루트도 split되면 트리 높이 1 증가

3.3 삭제 (Deletion)

1. 리프 노드에서 키/포인터 삭제
2. 노드가 너무 적어(underfull) 지면, 형제 노드와 재분배(redistribute) 또는 합병(coalesce/merge)
   • 합병 시 부모에서 해당 노드 정보 삭제 → 부모 노드도 underfull이면 재귀적으로 처리
3. 루트 노드가 포인터 1개만 남으면, 해당 자식 노드가 새 루트가 되고 루트 삭제 (트리 높이 1 감소)

4. 성능 분석

• 트리 높이가 log( fanout )에 비례 → 검색·삽입·삭제 모두 평균적으로 O(log N)의 디스크 I/O
  • 일반적으로 n(=노드 내 최대 포인터 수)을 디스크 블록 크기 기준으로 설정
  • 실제로는 비리프 노드들이 메모리에 상주할 가능성이 높아, 디스크 접근 횟수는 매우 적음 (1~3회 정도)

5. 비유일(Nonunique) 검색 키 처리

• 실무에서는 검색 키에 레코드 ID나 기본키 등을 덧붙여 복합 키로 만들고, 중복 문제 해결
• 중복을 허용하는 구조도 구현 가능하나, 삭제 시 특정 레코드만 찾아 제거하기가 비효율적 (키가 여러 리프에 걸칠 수 있음)
• 따라서 DBMS에서는 보통 자동으로 유일 키를 구성하는 방식을 사용함

4. B+-트리 확장 (B+-Tree Extensions)

1. B+-트리 파일 구조 (B+-Tree File Organization)

• B+-트리 자체가 파일의 레코드 저장 및 관리를 담당
  • 리프 노드가 레코드 자체를 저장 (기존 인덱스처럼 ‘포인터’가 아니라 ‘실제 레코드’)
  • 삽입/삭제 시 블록 split/merge 과정을 B+-트리처럼 수행
• 장점: 오버플로(overflow) 블록 문제를 줄여 성능 저하 방지
• 단점: 레코드가 크면 리프 노드 당 저장 가능한 레코드 수가 감소 → 노드 수 증가 가능

형제 노드 간 확장(split)·합병(merge)의 다중 노드 재분배 기법

• 삽입 시 인접 형제 노드와 여유 공간을 재분배하여 split 최소화
• 삭제 시 한 노드가 과소 채워짐(underfull) 상태일 때, 형제 노드와 재분배하거나 3노드 이상 함께 합병
• 노드 병합/재분배로 중간 수준의 채움 상태(2/3 이상) 보장 → 공간 활용률↑

2. 보조 인덱스(Secondary Indices)와 레코드 이동 문제

• B+-트리 파일 구조에서 리프 노드 split으로 인해 레코드가 물리적 위치를 이동할 수 있음
  • 이때, 기존 보조 인덱스(secondary index)가 레코드 포인터를 직접 저장할 경우, 대규모 업데이트 필요
• 해결책: 보조 인덱스에는 주(클러스터링) 인덱스 키(예: 기본키)만 저장 → 레코드 위치 변경 시에도 무관
  1. 보조 인덱스 → (주 인덱스 키) 목록 확인
  2. 주(클러스터링) 인덱스를 통해 최종 레코드 위치 찾아감
• 장점: 레코드 물리 위치 변경 시 보조 인덱스 업데이트 불필요
• 단점: 보조 인덱스를 통한 레코드 접근 시 두 번 인덱스 검색(보조 인덱스 → 주 인덱스) 필요

3. 문자열 인덱싱 (Indexing Strings)

• 문자열(가변 길이) 은 키 길이가 달라 고정 개수로 노드 수를 계산하기 어려움
  • 노드에 남은 공간 기준으로 split/merge 판단
• 문자열 길이가 길 경우, 팬아웃(fanout) 이 작아져 트리 높이 증가
• Prefix Compression(접두어 압축) 기법
  • 비리프 노드에는 구분에 필요한 접두어만 저장 (예: Silberschatz 대신 Silb만 사용)
  • 중첩되는 문자열이 많은 경우 저장 공간과 트리 높이를 줄이는 데 효과적

4. 대량 로딩(Bulk Loading) 기법

• 대규모 레코드에 대해 하나씩 삽입 시, 리프 접근이 임의 I/O라서 비용 매우 큼
• 효율적인 로딩 절차:
  1. 새 인덱스에 들어갈 (검색키, 레코드포인터) 쌍 임시 파일 생성
  2. 검색키 순으로 정렬
  3. 정렬된 순서대로 트리에 삽입 (또는 바텀업 방식으로 한 번에 구성)
• 장점:
  • 리프 노드가 순차적으로 차기 때문에 블록 간 임의 탐색 최소화
  • 인덱스 생성 시 I/O 횟수 크게 감소
• 실무 팁: 대량 삽입 시, 보조 인덱스 등을 제거 후 삽입 완료 뒤 재생성 → 더 빠름

5. B-트리(B-Tree)와의 비교

• B-트리: 중간(내부) 노드에 검색 키가 유일하게 한 번만 나타남
  • 각 내부 노드가 추가 포인터(파일/버킷용)를 가짐
  • 리프 노드와 내부 노드에 있는 키가 겹치지 않음
• B+-트리:
  • 비리프 노드의 키가 리프에도 중복으로 존재
  • 팬아웃(fanout)이 커서 트리 높이가 낮아지는 경향
• 대부분 DBMS에서는 B+-트리 사용 (실제로 ‘B-트리’라고 말하지만 구현은 B+-트리)

6. 플래시 스토리지(Flash Storage)에서의 인덱싱

• 플래시(SSD)는 랜덤 읽기(random read) 가 자기 디스크 대비 매우 빠름 (수십 ~ 수백 µs)
• 쓰기는 블록 단위 erase 필요 → In-Place Update 어려움
• B+-트리 노드 크기를 플래시 페이지 크기에 맞추면 성능 향상
• Bulk Loading 시에도 쓰기 횟수 감소하여 플래시 쓰기 비용 절감
• 추가 기법:
  • 노드 내부 버퍼링(내부 노드에 변경 분을 임시 기록 후 한 번에 반영)
  • Log-Structured Merge Tree(LSM-트리) 등 다양한 변형 구조

7. 메인 메모리 상의 인덱싱

• 메모리에 전체 데이터 상주 가능한 경우 → B+-트리 그대로 사용 가능하지만, 다음 최적화 가능:
  1. 메모리 구조(캐시 라인 등)를 고려한 작은 노드 크기 → 캐시 미스 최소화
  2. 노드를 캐시 라인 크기에 맞춰 관리 → 트리 탐색 시 캐시 로드 횟수 감소
• 디스크 기반 접근 최적화(큰 노드)와 메모리 기반 접근 최적화(작은 노드)는 절충이 필요

5. 해시 인덱스 (Hash Indices)

1. 개요

• 해싱(Hashing): 검색 키를 해시 함수 h에 통과시켜 버킷(bucket) 위치를 결정
• 버킷(bucket): 실제 레코드(또는 레코드 포인터)들을 저장할 수 있는 단위 공간
• 오버플로 체이닝(Overflow Chaining) 방식
  • 버킷이 가득 차면 오버플로 버킷을 추가로 연결(체인)
  • 닫힌 주소 방식(closed addressing)이라고도 함

2. 해시 인덱스 연산

2.1 삽입 (Insertion)

1. 레코드의 검색 키 Ki에 대해 h(Ki) 값 계산
2. 해당 버킷이 공간 여유가 있으면 레코드를 저장
3. 공간이 없으면 오버플로 버킷을 만들어 연결

2.2 검색 (Lookup)

1. h(Ki)로 대상 버킷 위치 찾기
2. 해당 버킷(및 연결된 오버플로 버킷들)을 순차 검사
3. 검색 키와 일치하는 레코드 찾기

2.3 삭제 (Deletion)

1. h(Ki)로 대상 버킷 찾기
2. 버킷 내에서 검색 키가 Ki인 레코드 제거 (연결 리스트에서 노드 제거)

3. 특징 및 제한

• Equality(=) 검색에 최적화
  • 예: WHERE key = value
• 범위(range) 검색에는 부적합 (버킷을 통한 순서/범위 판단 불가)
• 버킷 오버플로 발생 가능
  • 레코드 분포의 불균형(해시 충돌)
  • 해시 함수 선택 잘못 → 특정 버킷에 몰림
• 효율을 위해 버킷 수를 (레코드 수 / 버킷당 수용 레코드 수) * (1 + d) 정도로 설정 (d는 여유율, 예: 0.2)

4. 정적 해싱(Static Hashing) vs 동적 해싱(Dynamic Hashing)

4.1 정적 해싱 (Static Hashing)

• 버킷 수 고정
• 레코드 수가 예상보다 많이 증가하면, 한 버킷에 너무 많은 레코드가 몰려 검색 효율 급락
• 해결책: 해시 인덱스 재구성(버킷 수 늘려 다시 빌드)
  • 대규모 데이터 시 비용(다운타임) 매우 큼

4.2 동적 해싱 (Dynamic Hashing)

• 레코드 수 증가에 맞춰 버킷을 점진적으로 늘릴 수 있는 기법
• 대표 기법: 선형 해싱(linear hashing), 확장성 해싱(extendible hashing)
• 필요할 때마다 부분적으로 버킷 확장 → 전면 재구축 불필요

6. 다중 키 접근 (Multiple-Key Access)

1. 다중 단일-키 인덱스(Multiple Single-Key Indices)

1.1 상황 예시

• instructor 테이블에 다음 두 인덱스가 존재:
  1. dept_name 컬럼에 대한 인덱스
  2. salary 컬럼에 대한 인덱스
• 질의 예: dept_name = 'Finance' AND salary = 80000

1.2 처리 전략

1. 단일 인덱스 사용 (예: dept_name 인덱스만 사용 후 레코드에서 salary=80000 필터링)
2. 다른 단일 인덱스 사용 (예: salary 인덱스만 사용 후 dept_name='Finance' 필터링)
3. 두 인덱스 동시 사용
   • dept_name 인덱스로 'Finance' 레코드 포인터 목록 획득
   • salary 인덱스로 80000 레코드 포인터 목록 획득
   • 두 포인터 집합의 교집합(Intersection) 취하기

주의사항

• 포인터 집합이 매우 커서 교집합 과정이 많으면 오히려 비효율적일 수 있음
  • 예) Finance 레코드가 매우 많고, salary=80000도 많으나 실제 교집합은 적을 경우

2. 다중 속성(Composite) 인덱스

2.1 복합 키 인덱스 (Composite Search Key)

• 검색 키를 (dept_name, salary) 같이 2개 이상의 속성으로 구성
• Ordered(B+-트리) 인덱스에서는 (dept_name, salary)가 사전순(lexicographic) 으로 정렬
• 장점
  • (dept_name='Finance' AND salary=80000) 형태의 정확 일치 쿼리에 매우 빠른 접근
  • dept_name='Finance' AND salary < 80000 같은 (첫째 항목==, 둘째 항목 range) 형태 쿼리도 범위 스캔 이용 가능
  • dept_name='Finance' 단일 조건만 있어도 ('Finance', -∞) ~ ('Finance', +∞) 범위 스캔 가능

2.2 한계

• 첫 속성(dept_name)에 대한 조건이 =Finance (정확 일치)가 아닌, <나 > 인 경우, 원하는 범위가 분산되어 I/O 증가
  • 예: dept_name < 'Finance' AND salary < 80000 → 트리 순서가 (dept_name, salary)이므로 효과 떨어짐
• 다중 비교 연산이 섞여 있는 경우 효율이 떨어질 수 있음
  • 예) (dept_name < 'X') AND (salary > 50000) 등

3. 커버링 인덱스(Covering Index)

• 보조(secondary) 인덱스에서 검색 키 외에 추가 속성값 일부를 함께 저장
  • 예: (ID 인덱스)에 salary 값까지 저장
• 장점
  • 어떤 쿼리가 검색 키 + 일부 속성만 요청 시, 실제 테이블에 접근 없이 인덱스만으로 결과 얻을 수 있음
  • 예) SELECT salary FROM instructor WHERE ID = 12345 → 인덱스 내에 salary 존재 시, 테이블 접근 불필요
• 효과
  • 단순 (ID, salary) 복합 키 인덱스를 만드는 것과 유사하나, 인덱스의 검색 키를 작게 유지하면서 추가 속성을 커버함으로써
    • 팬아웃(fanout) 상승 (비리프 노드에 더 많은 키를 저장 가능)
    • 인덱스 높이 감소 → I/O 비용 절감

7. 인덱스 생성 (Creation of Indices)

1. 인덱스 생성 문법

• SQL 표준에는 인덱스 생성 구문이 명시되어 있지 않지만, 대부분 DBMS에서 다음과 같은 구문 지원:

  create index <index_name>
  on <table_name> (<column_list>);
  
  drop index <index_name>;

• UNIQUE 인덱스:

  • create unique index 사용 시, 해당 속성(또는 속성 집합)을 후보 키(중복 불가)로 간주

• 인덱스 종류 지정:

  • DBMS별로 B+-트리, 해시 인덱스 등 여러 유형을 지원할 수 있으며, 구체적 구문은 DBMS 매뉴얼 참조

2. 인덱스 유형

• DBMS마다 B+-트리 인덱스, 해시 인덱스, 기타 특수 인덱스 등 다양한 형태를 지원
• 특정 DBMS의 매뉴얼을 통해 인덱스 유형과 구체적 작성법을 확인 가능

3. 인덱스 사용 시 장점

• 선택 조건이나 조인 조건에 자주 사용되는 속성에 인덱스를 두면 쿼리의 수행 시간이 크게 단축
• 예: 특정 ID만 조회해야 하는 경우, 인덱스가 없으면 테이블 전체 스캔, 인덱스가 있으면 특정 레코드에 직접 접근

4. 인덱스 사용 시 단점

• 테이블에 삽입, 삭제, 갱신이 일어날 때마다 모든 관련 인덱스도 갱신해야 함
  → 인덱스가 많으면 수정 연산이 느려질 수 있음

5. 인덱스 설계 시 고려 사항

• 개발·테스트 단계에서 쿼리 시간이 빠듯하지 않을 수도 있으나, 동시에 많은 사용자가 같은 쿼리를 실행하면 급격히 느려질 수 있음
• 핵심 속성(자주 조회/조인되는 열)에 대해서는 미리 인덱스를 만들어둬야 함
• Primary Key 선언 시, 대부분의 DBMS는 기본적으로 인덱스를 자동 생성 (중복키 검증에도 사용)
• Foreign Key 속성에도 인덱스를 만들면, 일반적인 PK-FK 조인에서 훨씬 빠른 검색 가능

6. 인덱스 튜닝 (Index Tuning)

• DBMS에서 제공하는 인덱스 튜닝 도구(Index Tuning Wizard/Advisor) 등을 통해 실제 사용되는 쿼리·갱신 패턴을 분석
• 최근 클라우드 DB 서비스: 과도한 테이블 풀 스캔이 감지되면 자동으로 인덱스를 생성해 주는 기능 지원

14.8 쓰기 최적화 인덱스 구조 (Write-Optimized Index Structures)

1. LSM(Log-Structured Merge) 트리

• B+-트리는 랜덤 쓰기가 많은 환경에서 디스크 탐색(I/O)이 빈번 → 삽입/갱신 속도 저하
• LSM 트리:
  1. 메모리 내 트리(L0)*에 삽입
  2. 일정 크기 넘으면 디스크에 있는 트리(L1, L2, …)와 병합(Merge)
  3. 순차 I/O 위주로 처리 → 랜덤 I/O 크게 감소
  • 삭제/업데이트는 별도 표시(“삭제” 레코드 등)를 추가 삽입하고, 이후 병합 과정에서 실제 삭제/갱신 반영
• 장점: 대규모 랜덤 쓰기에 효과적 (No in-place update)
• 단점:
  • 조회 시 여러 레벨 트리를 모두 검색 필요
  • 병합 시 데이터 전체를 재작성할 수도 있음

2. 버퍼 트리(Buffer Tree)

• 각 내부 노드에 버퍼를 두어, 삽입 시 루트 버퍼에 저장 후 여유 시 자식 노드로 한꺼번에 전달
• 랜덤 쓰기를 여러 레코드(버퍼에 모인)로 나눠서(Amortized) 처리 → 쓰기 횟수 절감
• 삽입 시 자식 노드를 한 번 읽고 쓸 때 여러 레코드를 처리하므로 효율적
• 장점:
  • B+-트리처럼 전체 구조가 유지되면서도 쓰기 비용 감소
• 단점:
  • 조회 시 내부 노드 버퍼도 확인해야 하므로 구현 복잡
  • 디스크 기반 무작위 접근이 매우 비싼 상황(디스크 탐색)이면 LSM 트리가 더 효과적일 수도 있음
• 응용: PostgreSQL의 GiST 인덱스 등에서 버퍼링 기법 활용

9. 비트맵 인덱스 (Bitmap Indices)

• 개념: 속성이 가질 수 있는 각 값에 대해, 레코드 개수만큼의 비트 배열(bitmap)을 구성
  • 레코드 i가 해당 값이면 i번째 비트를 1로, 아니면 0으로 표기
• 용도:
  • 속성 값이 중복이 많고(카디널리티 낮고), 결합 질의(여러 속성 동시 조건)에서 빠른 교집합 계산 시 유리
  • 예: gender가 ‘m’, ‘f’만 있는 경우, income_level 등 범주형 속성
• 장점:
  • AND/OR 등 비트 연산을 매우 빠르게 수행해 교집합, 합집합 등을 효율적으로 계산
  • 결과 비트마스크로 해당 레코드만 읽으면 됨
• 한계:
  • 속성 값 범위가 큰 경우(유니크 값 매우 많을 때)는 비트맵 크기가 커서 비효율적
  • 주로 OLAP 환경, 결합 질의가 많은 데이터 웨어하우스에서 활용

10. 공간 및 시간 데이터의 인덱스 (Indexing of Spatial and Temporal Data)

1. 공간(Spatial) 데이터 인덱싱

1.1 개요

• 공간 데이터: 2차원 이상의 좌표로 표현되는 객체(점·선·다각형 등)
• 공간 질의 예:
  • 범위 질의: 특정 영역(원/사각형 등) 내에 포함되는 객체 찾기
  • 최근접 질의: 특정 위치에서 가장 가까운 객체 찾기

1.2 전통적 인덱스(B+-트리, 해시) 한계

• 1차원 기반으로 설계 → 다차원 범위 질의 처리에 비효율

1.3 k-d 트리 (k-dimensional tree)

• 각 내부 노드가 한 차원을 기준으로 공간을 2등분
• 이진 트리 형태로 좌표를 재귀적으로 분할
• 예) 2차원 데이터에서 루트는 x축 기준으로, 자식은 y축 기준으로 분할, 그다음 레벨은 다시 x축…
• 범위 질의(사각형, 원 등) 처리 시, 트리를 내려가며 분할 영역이 질의 범위와 교차하는지 검사

1.4 R-트리

• 다차원 객체(다각형 등) 를 최소 경계 사각형(MBR: Minimum Bounding Rectangle)으로 묶어 B-트리 형태로 구성
• 리프 노드: 실제 객체(또는 그 객체의 MBR) 저장
• 내부 노드: 자식 노드들의 MBR을 저장하며, 자식 포인터 보관
• 질의 시, MBR들과의 겹침 여부를 검사해 하위 노드를 탐색
• 장점: 한 객체를 하나의 노드에만 저장 (중복 X), 균형 트리 유지
• 응용: GIS, 지도 서비스(대상 지역 범위 질의, 최근접 식당 찾기 등)에 활용

2. 시간(Temporal) 데이터 인덱싱

2.1 시간 데이터

• 튜플에 시작 시점(start time)과 종료 시점(end time)으로 표현되는 유효 기간(interval) 존재
• 종료 시점이 현재까지인 경우, end_time = ∞(매우 큰 값)으로 표시

2.2 전통 인덱스의 문제

• attribute = value인 튜플 중 특정 시간점(또는 구간)에 유효한 것만 빠르게 찾고 싶을 때, 단순 B+-트리로는 비효율적

2.3 R-트리 활용

• 1차원 값(a) + 1차원 시간(time) → 2차원으로 확장하여 R-트리(또는 k-d 트리) 사용
• (a, start_time) ~ (a, end_time) 구간을 다루는 직사각형으로 표현
• 다만, end_time = ∞(현재 유효)인 구간은 매우 큰 사각형이 될 수 있어 처리 시 주의 필요
  • 현재 유효 튜플은 별도 인덱스 분리(B+-트리 등) or 다른 방식으로 관리

2.4 다른 기법

• Interval B+-tree: 시간 구간(시작~종료)에 특화된 인덱스
• 실제 DB 구현에서는 R-트리 등 다차원 인덱스를 재사용해 간단히 처리하는 경우가 많음

import java.util.*;

/*

최적화 X
테스트 1 〉	통과 (15.05ms, 77MB)
테스트 2 〉	통과 (6.67ms, 77.7MB)
테스트 3 〉	통과 (7.94ms, 78.7MB)
테스트 4 〉	통과 (17.39ms, 80.2MB)
테스트 5 〉	통과 (32.44ms, 102MB)
테스트 6 〉	통과 (29.87ms, 104MB)
테스트 7 〉	통과 (45.43ms, 111MB)
테스트 8 〉	통과 (122.54ms, 126MB)
테스트 9 〉	통과 (149.90ms, 183MB)
테스트 10 〉	통과 (87.34ms, 143MB)
테스트 11 〉	통과 (138.59ms, 133MB)
테스트 12 〉	통과 (171.24ms, 128MB)
테스트 13 〉	통과 (148.72ms, 183MB)
테스트 14 〉	통과 (304.81ms, 311MB)
테스트 15 〉	통과 (325.75ms, 327MB)
테스트 16 〉	통과 (323.85ms, 324MB)
테스트 17 〉	통과 (369.03ms, 377MB)
테스트 18 〉	통과 (447.14ms, 380MB)
테스트 19 〉	통과 (338.50ms, 355MB)
테스트 20 〉	통과 (339.62ms, 336MB)

*/

class Solution {
    
    static int[][] points, routes;
    
    static class Loc {
        int x, y;
        
        Loc(int x, int y) {
            this.x = x;
            this.y = y;
        }
        
        Loc(int a) {
            this.x = points[a][0];
            this.y = points[a][1];
        }
    }
    
    static class Robot {
        int idx;
        Loc loc;
        int stage;
        
        Robot(Loc loc, int idx) {
            this.idx = idx;
            this.loc = loc;
            stage = 1;
        }
    }
    
    static Queue<Robot> queue = new ArrayDeque<>();
    
    public int solution(int[][] points, int[][] routes) {
        
        this.points = points;
        this.routes = routes;
        
        int ans = 0;
                    
        int[][] visited = new int[101][101];
        
        // 로봇의 시작 위치를 담아 Queue에 넣기
        for(int i=0;i<routes.length;i++) {
            
            int pointIdx = routes[i][0]-1;
            
            Loc loc = new Loc(points[pointIdx][0]-1, points[pointIdx][1]-1);
            queue.offer(new Robot(loc, i));
            visited[loc.x][loc.y]++;
            // System.out.println(loc.x+" "+loc.y);
        }
        
                    
        for(int i=0;i<101;i++) {
            for(int j=0;j<101;j++) {
                if(visited[i][j] > 1) {
                    ans++;
                }
            }
        }
        
        while(!queue.isEmpty()) {
            
            visited = new int[101][101];
            Queue<Robot> newQueue = new ArrayDeque<>();
            
            while(!queue.isEmpty()) {
                Robot robot = queue.poll();
                

                
                int pointIdx = routes[robot.idx][robot.stage]-1;
                
                Loc target = new Loc(points[pointIdx][0]-1, points[pointIdx][1]-1);
                Loc nowLoc = robot.loc;
                
                // System.out.print(pointIdx+" "+ nowLoc.x+" "+nowLoc.y+" "+target.x+" "+target.y);
                                
                // 위치 도달 확인
                if(nowLoc.x == target.x && nowLoc.y == target.y) {
                    robot.stage++;
                }
                
                if(robot.stage >= routes[robot.idx].length) {
                    continue;
                }
                
                pointIdx = routes[robot.idx][robot.stage]-1;
                
                target = new Loc(points[pointIdx][0]-1, points[pointIdx][1]-1);
                nowLoc = robot.loc;
                
                // 위치 조정
                if(nowLoc.x == target.x) {
                    if (nowLoc.y > target.y) nowLoc.y--;
                    else nowLoc.y++;
                } else {
                    if (nowLoc.x > target.x) nowLoc.x--;
                    else nowLoc.x++;
                }
                
                visited[nowLoc.x][nowLoc.y]++;
                
                // System.out.println("-> "+nowLoc.x+" "+nowLoc.y);

                robot.loc = nowLoc;
                newQueue.offer(robot);
            }
            
            for(int i=0;i<101;i++) {
                for(int j=0;j<101;j++) {
                    if(visited[i][j] > 1) {
                        // System.out.println(i+" "+j+" "+visited[i][j]);
                        ans++;
                    }
                }
            }
            // System.out.println("----------");
            
            queue = newQueue;
        }
        
        
        return ans;
    }
}

풀이 과정을 대충 설명하자면,

시간을 int 로 변환하여 저장하였고,

ArrayList에 넣어서,,,

방의 갯수를 관리하였다.

하지만 더 똑똑한 방법이 있는데

그건 다음주에..

import java.util.*;

class Solution {
    static class Time {
        int startTime, endTime;
        
        Time(int startTime, int endTime) {
            this.startTime = startTime;
            this.endTime = endTime;
        }
    }
    public int solution(String[][] book_time) {
        int answer = 0;
        
        PriorityQueue<Time> pq = new PriorityQueue<>((a, b) -> (a.startTime - b.startTime));
        
        for(int i=0;i<book_time.length;i++) {
            String[] in = book_time[i][0].split(":");            
            int startTime = Integer.parseInt(in[0])*100 + Integer.parseInt(in[1]);
            
            in = book_time[i][1].split(":");
            int endTime = Integer.parseInt(in[0])*100 + Integer.parseInt(in[1])+10;
            
            if(endTime % 100 >= 60) {
                endTime += 40;
            }
            pq.offer(new Time(startTime, endTime));
        }
        
        List<Integer> list = new ArrayList<>();
        
        w: while(!pq.isEmpty()) {
            Time t = pq.poll();
            
            for(int i=0;i<list.size();i++) {
                if(list.get(i)<= t.startTime) {

                    list.remove(i);
                    list.add(t.endTime);
                    continue w;
                }
            }
            
            list.add(t.endTime);

        }
        
        return list.size();
    }
}

// 14:00 ~ 16:00
// 14:00 ~ 15:50