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

문제 URL

https://programmers.co.kr/learn/courses/30/lessons/49994

풀이

• 이 문제는 좌표를 중복 방문했는지를 검사하는 것이아닌 길을 중복방문했는지 검사하는문제다.

• 따라서 길이 중복되었는지 판단하기위해서 거쳐왔던 길을 저장할 자료구조를 선정해야한다. -> 좌표의 크기가 10*10 밖에 안되므로 배열을 사용해도 충분하다.

• visit[y][x][ny][nx]로 정의했다. 값이 true면 좌표(x,y)에서 (y,x)까지 길을 방문했다는것이다.

• 길을 저장 하는것이므로 방문할때마다. visit[y][x][ny][nx]와 visit[ny][nx][y][x] 둘다 true로 변경해야한다.

• 하지만 배열을 사용하는 방법은 공간복잡도가 굉장히 커서 이 문제에서는 적용가능하나 범용적인 방법은 아니다. HashSet을 사용하면 더 효율적으로 풀이할 수 있다.

• 중복을 검사하기 위해서 배열사용, HashSet사용을 할 수 있다는것을 숙지하자!

나의 풀이 (배열)

class Solution {

    public static int solution(String dirs) {
        boolean[][][][] visit = new boolean[11][11][11][11];

        int x = 5, y = 5, nx=5, ny=5;
        int answer = 0;

        for (char ch : dirs.toCharArray()) {
            nx = x; ny = y;

            if(ch == 'R') nx++;
            else if(ch == 'L') nx--;
            else if(ch == 'U') ny++;
            else if(ch == 'D') ny--;

            if(nx<0 || 10<nx || ny<0 || 10<ny){
                continue;
            }

            if(!visit[y][x][ny][nx]){
                answer++;
                visit[ny][nx][y][x] = true;
                visit[y][x][ny][nx] = true;
            }
            x = nx;
            y = ny;
        }

        return answer;
    }
}

다른 풀이 (HashSet)

https://bb-dochi.tistory.com/44 (출처 : 따봉도치님 tistory)

이 풀이는 공간 측면에서 더효율적으로 계산하고 U,D,R,L을 더 간략하게 해서 가져왔다.

import java.util.HashSet;
import java.util.HashMap;

class Solution {
    public int solution(String dirs) {
        int answer = 0;     
        int x = 0, y = 0;

        HashSet<String> set = new HashSet<>();
        HashMap<Character, 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(Character dir : dirs.toCharArray()){
            int lastX = x, lastY = y;

            x += map.get(dir)[0];
            y += map.get(dir)[1];

            if(x>5 || x<-5){
                x -= map.get(dir)[0];
                continue;
            }

            if(y>5 || y<-5){
                y -= map.get(dir)[1];
                continue;
            }

            //양방향 다 넣어주기
            set.add(lastX+""+lastY+""+x+""+y);
            set.add(x+""+y+""+lastX+""+lastY);
        }

        answer = set.size()/2;
        return answer;
    }
}