프로그래머스 - 충돌위험 찾기

문제 링크 ▶︎ 충돌위험 찾기

문제 파악

x대의 로봇의 이동 경로에 대한 좌표 정보를 모두 알고 있어야 하며, 시간대 별로 좌표를 비교할 수 있어야지 충돌하는 지 아닌 지를 체크할 수 있다.
로봇의 수와 point의 수, 그리고 이동하는 지점의 수도 모두 100이하이기 때문에 모두 순회해도 괜찮다는 생각이 든다.
그래서 routes 별로 이동하는 points 마다 이동 좌표를 모두 저장하고 좌표를 시간대별로 검사하는 방법으로 풀면 될 것 같다.

접근 방법

1. 우선 모든 좌표를 저장할 것이기 때문에 x개의 로봇이 points를 이동하는 좌표를 저장하기 위해서 길이가 x인 List<List<정수 배열>>를 만든다.
   바깥 List는 로봇들의 개수에 따라 추가되고 내부의 List는 하나의 로봇이 어떤 경로로 이동하는 지를 추가하면 된다.

2. 이중 반복문을 순회하면서 now, next points를 체크해서 build라는 함수를 통해서 List<정수배열>을 추가해준다.

3. build 함수는 문제에서 설정 방식으로 y좌표를 먼저 검사하게 하기 때문에 y -> x 순서로 좌표를 비교해서 한칸씩 이동할 수 있게 ++, -- 로직을 추가하고 List에 좌표 배열을 추가하도록 구현한다.

4. 다시 돌아와서 해당 List<정수배열>을 모두 만들고나서는 그 List를 최종 List에 추가해주고 전체 List를 순회하면서 동일한 좌표가 나오는 지를 체크한다.

5. 해시맵을 사용해서 키값을 좌표를 String으로 변환해서 넣어주고 밸류로는 정수를 넣어서 동일한 좌표일때 정수++ 할 수 있도록 구현한다. 이때, 키값을 정수배열로 하니까 다른 객체로 인식돼 String으로 구현하였고 중복을 생각해 중간에 쉼표를 추가한 String으로 구현했다.

코드 구현

import java.util.*;
class Solution {
    public int solution(int[][] points, int[][] routes) {
        int answer = 0;
        int range = 0;
        List<List<int[]>> data = new ArrayList<>();
        for (int i=0; i<routes.length; i++) {
            List<int[]> road = new ArrayList<>();
            for (int j=1; j<routes[i].length; j++) {
                int now = routes[i][j-1];
                int next = routes[i][j];
                if (j==1) {
                    road.add(new int[] {points[now-1][0], points[now-1][1]});
                }
                build(road, points, now, next);
            }
            range = Math.max(range, road.size());
            data.add(road);
        }
        for (int j=0; j<range; j++) {
            Map<String, Integer> lst = new HashMap<>();
            for (int i=0; i<data.size(); i++) {
                if (data.get(i).size()-1 < j) {
                    continue;
                }
                String str = data.get(i).get(j)[0] + "," + data.get(i).get(j)[1];
                if (lst.containsKey(str)) {
                    lst.put(str, lst.get(str) + 1);
                } else {
                    lst.put(str, 1);
                }
            }
            for (String k : lst.keySet()) {
                if (lst.get(k) > 1) {
                    answer++;
                }
            }
        }
        
        return answer;
    }
    public void build(List<int[]> road, int[][] points, int s, int e) {
        int[] start = points[s-1];
        int[] end = points[e-1];
        int y = start[0];
        int x = start[1];
        int ny = end[0];
        int nx = end[1];
        while ((y != ny) || (x != nx)) {
            if (y != ny) {
                if (y > ny) {
                    y--;
                    road.add(new int[] {y,x});
                } else {
                    y++;
                    road.add(new int[] {y,x});
                }
            } else {
                if (x > nx) {
                    x--;
                    road.add(new int[] {y,x});
                } else if (x < nx) {
                    x++;
                    road.add(new int[] {y,x});
                } else {
                    break;
                }
            }
        }
    }
}

개선 사항

매 순간의 좌표를 계산한 순간 바로 충돌 위험성을 체크하는 방법으로도 충분히 구현이 가능했을 것 같다.