[프로그래머스]방문 길이 - Java (Set 사용 풀이)

문제

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

프로그래머스

 

 

풀이

10X10의 좌표평면 위에서 게임이 진행되므로 게임 캐릭터가 [11][11] 크기의 배열 위에서 움직인다고 생각하고 문제를 풀었음

 

처음에는 방문한 좌표를 Set에 넣어서 중복을 제거해준 후 마지막에 Set의 크기를 답으로 정했는데, 지나간 길과 방문한 좌표 위치는 다를 수 밖에 없어서 예제 1번이 답이 다르게 나왔음 !

 

그래서 Set<String>에 "처음 위치 + 이동한 위치"를 넣었으나 테케 8번부터 답이 틀렸음

 

찾아보니까 "UDU" 같은 반례가 있다는 것을 알 수 있었음

"UDU"는 한번 지나간 길을 두번 더 왕복하므로 방문 길이는 1이 나와야 하지만 내가 푼 방법으로는 2가 나와서 정답이 아닌 것이였음 !

 

그래서 Set<String>에 "처음 위치 + 이동한 위치"와 "이동한 위치 + 처음 위치"를 저장하였고 마지막에 정답을 출력하기 전에 정답/2를 해줬음 !

 

자세한건 주석으로 !

 

 

코드

// 코딩테스트 연습 - Summer/Winter Coding(~2018) - 방문 길이
// https://school.programmers.co.kr/learn/courses/30/lessons/49994

package PROGRAMMERS.level2;

import java.util.HashSet;

public class Num49994_방문길이_set풀이 {
    private static class Solution {
        private int solution(String dirs) {
            int answer = 0;
            HashSet<String> hashSet = new HashSet<>(); // 지나간 길을 저장하기 위한 Set

            int r = 5, c = 5; // 중앙에서 시작

            for (int i = 0; i < dirs.length(); i++) {
                char temp = dirs.charAt(i);
                switch (temp) {
                    case 'U':
                        if (isPossible(r + 1, c)) { // 갈 수 있는 위치면
                            // 지나간 길에 넣어주고
                            hashSet.add(r + "+" + c + "+" + (r + 1) + "+" + c);
                            hashSet.add((r + 1) + "+" + c + "+" + r + "+" + c);
                            r++; // 현재 위치 이동
                        }
                        break;
                    case 'D':
                        if (isPossible(r - 1, c)) {
                            hashSet.add(r + "+" + c + "+" + (r - 1) + "+" + c);
                            hashSet.add((r - 1) + "+" + c + "+" + r + "+" + c);
                            r--;
                        }
                        break;
                    case 'R':
                        if (isPossible(r, c - 1)) {
                            hashSet.add(r + "+" + c + "+" + r + "+" + (c - 1));
                            hashSet.add(r + "+" + (c - 1) + "+" + r + "+" + c);
                            c--;
                        }
                        break;
                    case 'L':
                        if (isPossible(r, c + 1)) {
                            hashSet.add(r + "+" + c + "+" + r + "+" + (c + 1));
                            hashSet.add(r + "+" + (c + 1) + "+" + r + "+" + c);
                            c++;
                        }
                        break;
                }

                // 왕복하는 길을 넣어줬으므로 2배로 들어감. 그래서 마지막에 2로 나눠줌
                answer = hashSet.size() / 2;
            }


            return answer;

        }

        private static boolean isPossible(int r, int c) {
            if (r < 0 || r >= 11 || c < 0 || c >= 11) { // 범위 밖으로 벗어나면 false
                return false;
            }
            return true;
        }

        public static void main(String[] args) {
            Solution sol = new Solution();

            System.out.println(sol.solution("ULURRDLLU"));
            System.out.println(sol.solution("LULLLLLLU"));
            System.out.println(sol.solution("UDU"));
        }
    }
}