[programmers] [PCCP 기출문제] 3번 / 충돌위험 찾기 (java)

✏️ 문제

 

 

🔢 알고리즘

 

#시뮬레이션  #해시맵

  

🤯 풀이 방법

<문제 분석>

points: 운송 포인트들의 좌표
routes: 로봇이 어느 포인트를 거쳐야 하는지
찾아야 하는 것: 위험 상황의 발생 횟수

1) 각각의 route에 대해서 경로 배열을 만든다. (이동 포인트 이용해서)

  - 순회할 때 인덱스를 전체 값보다 하나 작게 잡아서 현재 값 기준으로 다음 값까지 이동 경로를 체크하게 함
2) 만들어진 경로 배열을 인덱스별로 확인해서 겹치면 위험 상황 +1, 반복문 종료

  - 같은 좌표에 많은 값이 충돌해도 하나의 충돌로 체크해서 HashMap 사용해서 경로에 대한 등장 횟수를 세는 방식으로 했음

경로 계산은?
ex) 1,4에서 6,4로 이동하려면: r 하나씩 증가
기본적으로 행 먼저 이동, 그다음 열 이동

 

<주의할 점>

• 처음에는 전체 경로의 수를 세서 그걸 하나씩 빼는 반복문을 돌렸는데, 디버깅을 하다가 매 초를 기준으로 한 바퀴씩 돌리는 것이 머릿속에서 시뮬레이션 해보기에 더 편하다고 느껴졌다.
• points 배열에서 좌표 값을 가져올때 clone()을 사용하지 않으면 원본 배열의 값을 바꿔서 참조값 오류 발생
• 제시되는 값 인덱스가 1부터 시작되므로 인덱스를 잡을 때 잘 일치시켜야 한다
• HashMap의 key를 int[]로 잡으면 같은 객체로 인식하지 않는다. List<Integer> 사용

 

👾 구현 코드 (자바)

import java.util.*;
import java.util.stream.Collectors;

class Solution {
    public int solution(int[][] points, int[][] routes) {
        int answer = 0;
        int countRoutes = routes.length;    // 로봇의 수
        
        // 각 로봇이 어떤 경로로 이동하는지 저장한다
        // key: 로봇 인덱스(0~routes.length - 1), value: 각 로봇의 경로(int[])를 ArrayList에 저장
        HashMap<Integer, ArrayList<int[]>> paths = new HashMap<>();
        
        for (int idx = 0; idx < countRoutes; idx++) {   // 0 ~ routes.length - 1까지 로봇 순회
            paths.put(idx, new ArrayList<int[]>()); // paths에 로봇 인덱스 key 삽입
            int[] route = routes[idx];  // route: 로봇의 이동 경로 배열
            int l = route.length;   // l: 각 로봇이 거치는 포인트의 수
            paths.get(idx).add(points[route[0] - 1].clone());  // 시작점 paths에 삽입
            
            for (int i = 0; i < l - 1; i++) {
                int[] cur = points[(route[i] - 1)].clone();   // 현재 좌표
                int[] next = points[(route[i + 1] - 1)].clone();  // 다음에 이동할 좌표

                while (cur[0] != next[0]) { // row
                    if (cur[0] < next[0]) {
                        cur[0] = cur[0] + 1;
                        paths.get(idx).add(new int[]{cur[0], cur[1]});               
                    } else {
                        cur[0] = cur[0] - 1;
                        paths.get(idx).add(new int[]{cur[0], cur[1]});
                    }
                }
                while (cur[1] != next[1]) { // column
                    if (cur[1] < next[1]) {
                        cur[1] = cur[1] + 1;
                        paths.get(idx).add(new int[]{cur[0], cur[1]});               
                    } else {
                        cur[1] = cur[1] - 1;
                        paths.get(idx).add(new int[]{cur[0], cur[1]});
                    }
                }   
            }
        }
        
        // 가장 긴 경로 수 구하기
        int maxCnt = 0;
        Set<Integer> keySet = paths.keySet();        
        for (Integer key : keySet) {
            if (paths.get(key).size() > maxCnt) {
                maxCnt = paths.get(key).size();
            }                                        
        }
        
        // 충돌 확인
        for (int sec = 0; sec < maxCnt; sec++) { // 가장 긴 경로만큼 순회 (매 초에 해당)
            HashMap<List<Integer>, Integer> check = new HashMap<>();    // 각 시간별 등장 경로 count
            for (int i = 0; i < countRoutes; i++) { // 로봇 순서대로 탐색
                if (paths.get(i).size() != 0) { // 경로가 끝나지 않았을 경우에만
                    int[] target = paths.get(i).get(0);
                    List<Integer> targetList = Arrays.stream(target).boxed().collect(Collectors.toList());
                    if (check.containsKey(targetList)) {    // 이미 나온 거면 + 1
                        check.replace(targetList, check.get(targetList) + 1);
                    } else {
                        check.put(targetList, 1);
                    }
                    
                    paths.get(i).remove(0); // 계산한 경로는 path에서 삭제
                    
                }   
            }   
            
            for (List<Integer> key : check.keySet()) {
                if (check.get(key) > 1) {   // 2번 이상 등장한 경우 중복 경로로 count
                    answer++;
                }
            }
        }   
        return answer;
    }
}

 

 

🤖 GPT의 코드 개선 제안

✅ 1. paths.get(i).remove(0) 성능 이슈

문제

• ArrayList.remove(0)는 O(n) 시간 복잡도를 갖습니다. 이를 maxCnt만큼 반복하게 되면 전체 시간복잡도는 O(R × maxLen²) 수준으로 늘어납니다 (R: 로봇 수, maxLen: 경로 길이).
• 로봇 수나 경로 길이가 많아질 경우 심각한 비효율로 이어질 수 있습니다.

🔧 해결 방법

• index 기반 시뮬레이션으로 전환 (슬라이싱 대신 인덱스를 증가시키는 방식)

✅ 2. 좌표 비교 시 List<Integer> → 문자열 또는 Pair 구조로 단순화

문제

• List<Integer>로 좌표를 표현하고 Map 키로 사용하는 건 불필요하게 무겁습니다.

🔧 해결 방법

• 좌표를 문자열 "r,c" 형식으로 처리하거나, Objects.hash(r, c)를 사용할 수 있습니다.

 

 

프로그래머스