[프로그래머스 level2] 충돌위험 찾기 자바 Map활용

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

프로그래머스

문제

각 창고의 지정위치를 표현한 points와 각 로봇들의 시작포인트 -> 종료포인트를 표현한 routes가 있다.

모든 로봇은 매 초마다 1칸씩 이동하며 r좌표 변동을 c좌표변동보다 우선한다.

로봇들이 이동하여 같은 지점에 2대이상 로봇이 존재하면 충돌위험으로 판단한다.

모든 routes이동을 완료할 때 까지 발생한 충돌위험의 갯수를 반환하시오.

 

처음접근

Map에 포인트정보를 담고, routes를 반복처리하면서 각 포인트들을 이동하면 어떨까 라고 생각했다.
하지만 이 방법으로는 매 시간별 로봇들의 위치정보를 정확히 파악하기 어려웠고 새로운 방법이 필요했다.

---

GPT 피드백

✅ 핵심 아이디어

1. 모든 로봇의 경로를 시뮬레이션하면서,
2. 각 시간별 위치 기록을 남겨야 하고,
3. 해당 위치에 몇 대의 로봇이 있는지 체크해야 충돌 여부를 알 수 있습니다.

---

📦 추천 방식: Map<time, Map<position, count>>

시간 단위로 위치별 로봇 수를 기록하는 자료구조를 사용하면 좋아요.

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

• key: time → 현재 시각
• value: Map<position, count>
  • position: "r,c" 같은 문자열 형태로 좌표를 표현
  • count: 해당 시간에 그 위치에 있는 로봇 수

---

public int solution(int[][] points, int[][] routes) {
        Map<Integer, Map<String, Integer>> tp = new HashMap<>();

        for(int[] route : routes){
            int time = 0;
            int[] start = points[route[0] -1];
            int[] end = points[route[1] -1];

            int r = start[0], c = start[1];
            int endR = end[0], endC = end[1];
            //최초 포지션에 여러대일 경우
            String initK = r + "," + c;
            tp.computeIfAbsent(time, k -> new HashMap<>()).merge(initK, 1, Integer::sum); // "해당 key가 이미 존재하면 기존 값과 1을 더해서 갱신하고,존재하지 않으면 1을 새로운 값으로 추가한다."


            while(r != endR){
                time ++;
                r += (endR > r ? 1 : -1);
                String key = r + "," + c;
                tp.computeIfAbsent(time, k -> new HashMap<>()).merge(key, 1, Integer::sum); // "해당 key가 이미 존재하면 기존 값과 1을 더해서 갱신하고,존재하지 않으면 1을 새로운 값으로 추가한다."
            }

            while(c != endC){
                time ++;
                c += (endC > c ? 1 : -1);
                String key = r + "," + c;
                tp.computeIfAbsent(time, k -> new HashMap<>()).merge(key, 1, Integer::sum);
            }

        }

        int answer = 0;
        for (Map<String, Integer> posMap : tp.values()) {
            for (int count : posMap.values()) {
                if (count >= 2) {
                    answer += 1;
                }
            }
        }
        return answer;
    }

발견된 문제

route의 길이가 2 이상인 경우 처리되지 않음.

수정

 public int solution(int[][] points, int[][] routes) {
        Map<Integer, Map<String, Integer>> tp = new HashMap<>();

        for(int[] route : routes){
            int time = 0;
            int r = points[route[0] -1][0], c = points[route[0] -1][1];
            //최초 포지션 기록
            tp.computeIfAbsent(time, k -> new HashMap<>())
                    .merge(r + "," + c, 1, Integer::sum); // "해당 key가 이미 존재하면 기존 값과 1을 더해서 갱신하고,존재하지 않으면 1을 새로운 값으로 추가한다."
            for(int j = 0; j < route.length; j ++){
                int[] end = points[route[j] -1];
                int endR = end[0], endC = end[1];

                while(r != endR){
                    time ++;
                    r += (endR > r ? 1 : -1);
                    String key = r + "," + c;
                    tp.computeIfAbsent(time, k -> new HashMap<>()).merge(key, 1, Integer::sum); // "해당 key가 이미 존재하면 기존 값과 1을 더해서 갱신하고,존재하지 않으면 1을 새로운 값으로 추가한다."
                }

                while(c != endC){
                    time ++;
                    c += (endC > c ? 1 : -1);
                    String key = r + "," + c;
                    tp.computeIfAbsent(time, k -> new HashMap<>()).merge(key, 1, Integer::sum);
                }
            }
        }

        int answer = 0;
        for (Map<String, Integer> posMap : tp.values()) {
            for (int count : posMap.values()) {
                if (count >= 2) {
                    answer += 1;
                }
            }
        }
        return answer;
    }

알게된 점

1. Map의 merge(key, 1, Integer::sum)는 put(key, getOrDefault(key, 0) + 1)와 같은 효과
2. map null체크 : computeIfAbsent(key, k - > new HashMap<>())