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

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

코딩테스트 연습 - 방문 길이

 

풀이

 

이 문제는 좌표를 방문한지 확인하는 것이 아니라, 경로를 이미 방문한지 확인하는 문제이다.

따라서 이 문제의 풀이의 핵심은 경로를 String으로 만들어서 HashSet에 넣어주면서 중복이 제거된 경로의 수만 찾는 것이다.

 

이때 경로 String은 작은 좌표를 앞에 써주는 방식으로 생성해줍니다. 아래처럼 방향이 다르고 같은 길을 지나는 경우를 잘 처리하기 위한 규칙을 임의로 만든 것입니다.

즉, U 또는 R방향으로 이동할 경우엔 "현재 좌표"+"이동 후 좌표"로 생성하고

D 또는 L 방향으로 이동할 경우엔 "이동 후 좌표" + "현재 좌표"로 생성해 줍니다.

이렇게 하면서 범위를 벗어나는 경우를 제외해주면 문제가 해결됩니다.

 

import java.util.*;

class Solution {
    public int solution(String dirs) {
        int answer = 0;
        HashSet<String> s = new HashSet<String>();  //중복확인 위해 사용하는 set
        
        int len = dirs.length();
        
        int nowX = 0;
        int nowY = 0;
        
        for(int i=0; i<len; i++){
            int nextX = nowX;
            int nextY = nowY;
            String road = "";       //경로 저장할 문자열
            // U : "현재 좌표"+"이동 후 좌표"
            if(dirs.charAt(i) == 'U'){
                nextY++;
                road += nowX;
                road += nowY;
                road += nextX;
                road += nextY;
            }
            // D :  "이동 후 좌표" + "현재 좌표"
            else if(dirs.charAt(i) == 'D'){
                nextY--;
                road += nextX;
                road += nextY;
                road += nowX;
                road += nowY;
            }
            // R : "현재 좌표"+"이동 후 좌표"
            else if(dirs.charAt(i) == 'R'){
                nextX++;
                road += nowX;
                road += nowY;
                road += nextX;
                road += nextY;
            }
            // L :  "이동 후 좌표" + "현재 좌표"
            else if(dirs.charAt(i) == 'L'){
                nextX--;
                road += nextX;
                road += nextY;
                road += nowX;
                road += nowY;
            }
            
            //범위 벗어나면 무시
            if(nextX < -5 || nextY < -5 || nextX > 5 || nextY > 5)
                continue;
            
            s.add(road);
            nowX = nextX;
            nowY = nextY;
        }
        answer = s.size();
        return answer;
    }
}