문제 07) 방문 길이

게임 캐릭터를 4가지 명령어를 통해 움직이려 합니다. 명령어는 다음과 같습니다.

• U : 위쪽으로 한 칸
• D : 아래쪽으로 한 칸
• R : 오른쪽으로 한 칸
• L : 왼쪽으로 한 칸

캐릭터는 좌표평면의 (0, 0) 위치에서 시작합니다. 좌표평면의 경계는 왼쪽 위(-5, 5), 왼쪽 아래(-5, -5), 오른쪽 위(5, 5), 오른쪽 아래(5, -5)로 구성합니다.

 

이때 우리는 게임 캐리거가 지나간 길 중 캐릭터가 처음 걸어본 길의 길이를 구하려고 합니다. 명령어가 매개변수 dirs로 주어질 때 게임 캐릭터가 처음 걸어본 길의 길이를 구해 반환하는 solution() 함수를 완성하세요.

---

제약조건

• dirs는 string형으로 주어지며, 'U', 'D', 'R', 'L' 이외의 문자는 주어지지 않습니다.
• dirs의 길이는 500자 이하의 자연수입니다.

---

입출력의 예

dirs	answer
ULURRDLLU	7
LULLLLLLU	7

---

아이디어 - (오답)

위 문제를 풀면서 시간 복잡도를 고려하다보니, 2차원 배열 탐색을 이중 for문을 사용하면 O(n^2)의 복잡도를 가질것 같았다.

그래서 먼저 1차원 배열로 생각해보았다.

 

어차피 범위는 x, y 좌표 모두 -5 ~ 5 까지이니, 왼쪽 최하단 점인(-5, -5)를 0번째 인덱스 / 우측 최상단 점인 (5, 5)를 120번째 인덱스로 생각하여 boolean[] visited = new boolean[121]의 1차원 배열을 선언했다. 그리하여 원점은 visted[60]번째 인덱스를 true로 표현.

각각

'U' : +11

'D' : -11

'L' : -1

'R' : +1

로 생각하여 문제를 해결해나갔다. 그리하여 방문하지 않은 점일 때마다 count하여 답을 반환했는데, 문제가 발생했다.

한번 방문했다고 카운트 하지 않는 것이 아니라, 다른 길로 돌아오는 경우에는 카운트 해야 하는데, 아예 점 자체를 건너뛰어버려 정확한 답이 나오지 않았다. 아래 코드는 기록해두고 다른 방법을 찾아보겠다.

 

[오답 코드]

private static int solution(String dirs){
        boolean[] visted = new boolean[121];
        int point = 60; // 원점
        int count = 0;
        visted[point] = true;

        for(int i=0; i<dirs.length(); i++){
            char c = dirs.charAt(i);
            switch(c){
                case 'U':
                    point += 11;
                    break;

                case 'D':
                    point -= 11;
                    break;

                case 'L':
                    point -= 1;
                    break;

                case 'R':
                    point += 1;
                    break;
            }
            if(!visted[point]){
                count++;
                visted[point] = true;
            }
        }

        return count;
    }

---

정답 코드

이중 for문이 아닌, HashMap을 사용하면 O(n^2)의 시간 복잡도가 아니라, O(N)의 복잡도로도 충분히 구현이 가능했다.

// 좌표 평면을 벗어나는지
    private static boolean isValidMove(int nx, int ny){
        return 0 <= nx && nx < 11 && 0 <= ny && ny < 11;
    }

    // 다음 좌표  결정을 위한 해시맵
    private static final HashMap<Character, int[]> location = new HashMap<>();

    private static void initLocation(){
        location.put('U', new int[]{0,1});
        location.put('D', new int[]{0,-1});
        location.put('L', new int[]{-1,0});
        location.put('R', new int[]{1,0});
    }

    private static int solution(String dirs){
        initLocation();

        int x = 5, y = 5;
        HashSet<String> answer = new HashSet<>(); // 겹치는 좌표는 1개로 처리

        for(int i=0; i<dirs.length(); i++){
            int[] offset = location.get(dirs.charAt(i));
            int nx = x + offset[0];
            int ny = y + offset[1];
            if(!isValidMove(nx, ny)){
                continue;
            }

            answer.add(x + " " + y + " " + nx + " " + ny);
            answer.add(nx + " " + ny + " " + x + " " + y);

            x = nx;
            y = ny;
        }

        return answer.size() / 2;
    }