[프로그래머스/JAVA 자바] 방문 길이

 

프로그래머스

 

문제풀이

1. 중복을 고려하는 문제. Hash 사용 고려

2. 정해진 범위를 이탈하면 이동하지않고 다음 행동 진행

3. HashMap의 key , value 값에 배열을 다루기 어려워 HashSet에 String 을 사용

4. HashSet 에 저장할 때 좌표(숫자)를 String 으로 변환하여 저장.   ( set = " " + 좌표 1 + 좌표 2 )

5. 입력값 dirs 가 "UDU" 같은 되돌아오는 값이 주어지면 ( answer = 1 ) 처음 걸어본 길인가를 판단하여 최종 이동거리를 계산해야하는데, 이동 전 좌표 + 이동 후 좌표를 저장할때 x+y 의 합이 더 적은 좌표를 앞에, x+y의 합이 더 큰 좌표를 뒤에 배치를 하여 HashSet에 저장을 하면 방향을 고려한 값을 추가로 저장하지 않아도 됨.

[ 0 , 0 ]  -> U -> [ 0 , 1 ]       ---> HashSet 에 "0001" 저장

[ 0 , 1 ]  -> D -> [ 0 , 0 ]       ---> HashSet 에 "0001" 저장 ( 중복으로 걸러짐 )

( set = " " +  (x,y의 합이 더 적은 좌표)   +  ( x , y 의 합이 더 큰 좌표 )  )

 

dirs	before	after	save
L	[ 0 , 0 ]	[ -1 , 0 ]	"-1000"
U	[ -1 , 0 ]	[ -1 , 1 ]	"-10-11"
L	[ -1 , 1 ]	[ -2 , 1 ]	"-21-11"
L	[ -2 , 1 ]	[ -3 , 1 ]	"-31-21"
L	[ -3 , 1 ]	[ -4 , 1 ]	"-41-31"
L	[ -4 , 1 ]	[ -5 , 1 ]	"-51-41"
L	[ -5 , 1 ]	[ -5 , 1 ]	x
L	[ -5 , 1 ]	[ -5 , 1 ]	x
U	[ -5 , 1 ]	[ -5 , 2 ]	"-52-51"

 

 

import java.util.HashSet;

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

        // 좌표 저장 방식 = ""  +  (x+y)가 더 적은값  +  (x+y)가 더 큰 값
        HashSet<String> set = new HashSet<>();

        int[] before = {0, 0};
        int[] after = {0, 0};

        for (int i = 0; i < dirs.length(); i++) {

            if (dirs.charAt(i) == 'U') { // 상
                after[1]++;
                if (check(before[0], before[1]) && check(after[0], after[1])) {
                    set.add("" + before[0] + before[1] + after[0] + after[1]);
                }else {
                    after[1]--;
                }

            } else if (dirs.charAt(i) == 'D') { // 하
                after[1]--;
                if (check(before[0], before[1]) && check(after[0], after[1])) {
                    set.add("" + after[0] + after[1] + before[0] + before[1]);
                }else {
                    after[1]++;
                }
            } else if (dirs.charAt(i) == 'L') { // 좌
                after[0]--;
                if (check(before[0], before[1]) && check(after[0], after[1])) {
                    set.add("" + after[0] + after[1] + before[0] + before[1]);
                }else {
                    after[0]++;
                }
            } else {                            // 우
                after[0]++;
                if (check(before[0], before[1]) && check(after[0], after[1])) {
                    set.add("" + before[0] + before[1] + after[0] + after[1]);
                }else {
                    after[0]--;
                }
            }

            before[0] = after[0];
            before[1] = after[1];

        }

        answer = set.size();
        return answer;
    }
    
        static boolean check(int x, int y) {

        if (x < -5 || x > 5 || y < -5 || y > 5) {
            return false;
        }

        return true;
    }
    
}