[프로그래머스 Lv2] 방문길이

---

 

다른 사람들의 풀이를 보는데 제각기 복잡하긴 해도, 나와 같은 부분에서 고민하고 이름을 짓는 걸 보고 신기해서 기록을 남긴다. 사람 생각하는 거 다 똑같구나 싶어가지고.

 

※ 내 풀이는 전부를, 다른 사람의 풀이는 일부만 발췌했습니다. 

 

먼저 내가 푼 코드:

import java.util.Arrays;
import java.util.List;
import java.util.ArrayList;

class Solution {
    public static int solution(String dirs) {
        // 1. 전체 좌표 배열을 만든다: { {0,0}, {0,1}, ... }
        //      -5보다 작아지거나 5보다 커지려고 하는 경우는 그대로 -5와 5로 고정한다.
        int[][] coords = new int[dirs.length()+1][];
        int x = 0, y = 0;
        coords[0] = new int[] {x, y};
        for (int i = 0; i < dirs.length(); i++) {
            // U or D: y +-1
            // R or L: x +-1
            char dir = dirs.charAt(i);
            if (dir == 'U' && y < 5) {
                y++;
            } else if (dir == 'D' && y > -5) {
                y--;
            } else if (dir == 'R' && x < 5) {
                x++;
            } else if (dir == 'L' && x > -5) {
                x--;
            }
            coords[i+1] = new int[] {x, y};
        }
        // System.out.println(Arrays.deepToString(coords));
        
        // 2. {이전좌표, 지금좌표} 쌍을 새로운 '길' 리스트에 저장한다
        //     {이전좌표, 지금좌표}나 {지금좌표, 이전좌표} 쌍이 이미 들어있는 쌍중에 있다면
        //      넣지 않는다.
        //      또한 {이전좌표}와 {지금좌표}가 서로 다를 때만 넣는다.
        List<int[][]> paths = new ArrayList<int[][]>();
        int[][] temp_path = new int[][] {coords[0], coords[1]};
        int[][] temp_path_reverse = new int[][] {coords[1], coords[0]};

        for (int i = 1; i < coords.length; i++) {
            temp_path[0] = temp_path_reverse[1] = coords[i-1];
            temp_path[1] = temp_path_reverse[0] = coords[i];

            // 연이은 두 좌표가 같으면 '길'에 넣지 않는다
            if (Arrays.deepEquals(temp_path, temp_path_reverse)) {
                continue;
            }
            // '길'에 차례로와 거꾸로 좌표쌍이 모두 없다면 넣는다.
            if (!deepContains(paths, temp_path)
                && !deepContains(paths, temp_path_reverse)) {
               	// System.out.printf("=> temp_path %s 넣음%n", Arrays.deepToString(temp_path));            
                paths.add(Arrays.copyOf(temp_path, 2));
            }
        }
        
        return paths.size();
    }
    
    // 해당 3D 배열에 해당 2D 배열이 들었으면 true 반환(깊은 비교)
    static boolean deepContains(List<int[][]> list, int[][] target){
        for(int[][] arr : list){
            if(Arrays.deepEquals(arr, target)){
                return true;
            }
        }
        return false;
    }
}

=> 배열을 사용해서 풀어보았다. 

 

 

다른 사람의 풀이 중 발췌:

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

class Solution {
    public int solution(String dirs) {
        Map<String, int[]> map = new HashMap<>();
        map.put("U", new int[] {0, 1});
        map.put("D", new int[] {0, -1});
        map.put("R", new int[] {1, 0});
        map.put("L", new int[] {-1, 0});

		// ...

        for(int i=0; i<arr.length; i++) {
            String s = arr[i];

            // ...
            
            set.add(""+(cx-x)+ ""+ (cy-y)+ ""+cx + ""+cy);
            set.add(""+cx + ""+cy+""+(cx-x)+ ""+ (cy-y));
        } 
        return set.size()/2;
    }
}

마지막에 Set을 이용한 것이 인상적이다.

 

남은 코드 줄 수가 점점 줄어감에 따라 "이제 곧 끝나는데 아직 반절도 진행이 안됐는데..?" "다섯 줄 남았는데..?!" 하며 읽어내렸던 게 기억에 남는다. 마지막 3줄이 남도록 아직도 좌표를 계산하고만 있는 것이다. '길'은 언제 저장할건데..? 그런데 정말 Set이 등장해서 3줄만에 반환값까지 해결해버렸다.

 

 => 캐릭터가 지나간 '길'을 기록할 때, [0,0]에서 [0,1]로 갔으면 "0001"같이 문자열로 만들어 보관하는 것을 나도 생각했었다. 그리고 Set을 이용하는 아이디어도. 그런데 거꾸로 지나갔던 길도 비교해야하는 지점에서 나는 배열로 푸는 방법을 모색하게 됐고, 최소 2중 배열을 사용해야 했고, 따라서 깊은 비교는 하지 않는 Set을 사용할 수가 없었다. 

 

근데 이 풀이는 마지막에 "지금좌표"+"이전좌표" 하나와 "이전좌표"+"지금좌표" 하나를 다 Set에 넣어버리는 방법으로 해결해냈다. 순수 문자열을 넣는 거니까 Set이 중복을 걸러낼 수 있다. 그리고 마지막에 그냥 Set 전체 길이의 반만 반환하면 되는 것이다. 어썸...

 

 

 

또 다른 사람의 풀이 중 발췌:

import java.util.*;

class Solution {
    public static int solution(String dirs) {
        Set<Road> visited = new HashSet<>();
        Road initRoad = new Road();
        for (char command : dirs.toCharArray()) {
            RoadMover.valueOf(String.valueOf(command)).command(initRoad.getStart())
                    .ifPresent(road -> {
                        initRoad.setStart(road.getEnd());
                        visited.add(road);
                    });
        }
        return visited.size();
    }
}

enum RoadMover implements RoadMoveStrategy {
    // ...
}

// ...

class Road {
    private Point start;
    private Point end;

    private Road(Point start, Point end) {
        this.start = start;
        this.end = end;
    }
    
    // ...

}

class Point {

    private final int y;
    private final int x;

    private static final int MAX_BOUND = 5;

    // ...

}

솔직히 이 코드는 다 뜯어보지 않았다. 다만 클래스 Road와 Point가 각각 '길'과 '좌표'를 나타낸다는 걸 알게 됐다. 이런 코드를 짜는 사람도 나와 비슷한 개념을 쓰네 싶어서 재밌었다. 기회가 된다면 나중에 공부하고 더 뜯어봐야지.

 

 

---

 

새롭게 찾아 쓴(a.k.a. 구글링한) 코드:

• 다중 배열을 선언할 때 첫 차원의 크기만 지정해줘도 에러가 안 난다는 것을 확인했다.
  • ex) int[][] coords = new int[20][];
• 리스트의 타입에도 다중 원시 배열을 선언할 수 있다.
  • ex) List<int[][]> paths = new ArrayList<>();

 

 

문제가 크게 하나 있었다. 지나간 길을 비교할 때마다 매번 새로운 배열을 만들기 싫어서 int[][] temp_path를 하나 만들어두고 내용물을 바꿔가면서 사용했다. 방금 지나온 길을 temp_path에 덮어씌우고 여태껏 지나온 길 리스트에 없으면 집어넣었다. 그런데 아무리 많은 길을 지나도 지나온 길 목록이 늘지를 않는 것이다. 

 

 과정1: 확인해보니 길 리스트에 새로운 길이 등록되기는 하는데 매번 전 데이터가 없어졌다. 마치 덮어씌우는 것처럼. 나는 분명히 List.add()를 썼는데.

 

 과정2: 다음의 에러를 해결하면서 힌트를 얻었다:

• 다중 배열에 값을 집어넣을 때, 그냥 coords[0] = {x, y}와 같이 할 수 없다. 매번 새롭게 생성해서 넣어줘야 한다.
  • ex) coords[0] = new int[] {x, y};

 과정3: 배열 자체도 참조자료형이라는 게 핵심이었다. 리스트가 배열을 저장할 땐 그 주소값을 저장하는 것이다. temp_path의 내용물을 계속 바꿔줘도, 결국 같은 주소 하나만 주구장창 집어넣은 게 된 것이다. List.add()로 똑같은 주소를 넣으면 무시당한다는 걸 알게 되었다... 

 

 과정4: 그래서 temp_path를 업데이트할 때마다 복사해서 다른 주소를 넣어주면 되지 않을까 싶었다:

• Arrays의 copyOf(복사할 배열, 결과배열의 크기값): 복사된 배열을 반환할 거니까 크기값을 반드시 지정해줘야 한다. 새 배열이 반환되는 거니까 coords[0] = new int[] {x, y}자리에 올 수 있다. 즉, coords[0] = Arrays.copyOf(...)이 가능하다. 

 과정5: 해결됐다! 이럴거면 처음부터 int[][] temp_path를 매번 새롭게 '생성'해서 쓰는 게 나았을 수도? 어차피 리스트에 들어갈 때 그만큼의 새 배열들이 만들어져야 했으니 말이다.

 

 

아쉬운 점:

• 리스트에 사용할 타입으로 배열은 피하고 차라리 리스트의 리스트를 만들라고들 한다. 왜 그런걸까? List<int[][]>가 어떻게든 작동하긴 하는데. 검색에는 ArrayList<ArrayList<Integer>>와 같은 예가 많이 나온다. 

 

---