[프로그래머스] 방문 길이 (JAVA)

개츠비·2023년 5월 18일

프로그래머스

목록 보기

15/16

소요시간 : 1시간 30분
문제 사이트 : 프로그래머스
문제 수준 : 레벨 2
문제 유형 : 구현
다른 사람의 풀이를 참고 했는가 ? : X
문제 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/49994
푼 날짜 : 2023.05.18

1. 사용한 자료구조 & 알고리즘

구현.

2. 사고과정

처음에는 도착한 좌표의 방문처리만 해주면 될 것으로 생각했으나, 도착하는 좌표로 올 수 있는 방법은 4가지나 된다.

그래서 든 생각은
이전 좌표 , 다음 좌표를 해시셋에 저장하는 것이다.
0,0 에서 0,1 로 갔다면 해시셋에
0 0 0 1 을 추가해주면 된다고 생각했다.

그리고 리턴해주는 것은 해시셋의 size로 생각했다.

하지만 이 경우 반례가 있다.
0,0 에서 0,1 로 가고, 그 후 다시
0,1 에서 다시 0,0 으로 온다면
해시셋에는
0 0 0 1
0 1 0 0
2개가 들어가게 된다.
이 경우에 실제로 방문 길이는 1이다.

이 경우를 어떻게 처리해 줄것인가?

생각해보고 내린 결론은 좌표를 오름차순으로 정렬하는 것이다.
0 1 0 0을 보고, 이전 좌표가 0 1, 다음 좌표가 0 0 이므로
다음 좌표가 0 0으로 더 작으므로, 0 1과 0 0의 위치를 바꿔서 0 0 0 1로 바꾼다.
그렇다면 0,0에서 0,1 로 가고, 그 후 0,1 에서 0,0 으로 간것을 모두
0 0 0 1
0 0 0 1의 방문으로 처리할 수 있고, 이 경우 해시셋의 size는 1이 된다.

3. 풀이과정

문자열에 따라서 좌표를 이동한다.
좌표가 맵 범위를 넘었다면, 이동하지 않은 것으로 처리하고 continue
이전 좌표와 다음 좌표를 정렬해준다.
해시셋에 (이전 좌표 + 다음 좌표) 를 저장해준다.
해시셋의 size 를 리턴

4. 소스코드

import java.util.*;
class Solution {
    public int solution(String dirs) {
      HashSet<String> set=new HashSet<>();
        
        int nowY=0;
        int nowX=0;
        int prevY=0;
        int prevX=0;
        for(int i=0;i<dirs.length();i++){
            char ch=dirs.charAt(i);
          
            switch(ch){
                case 'U' : nowY--;break;
                case 'D' : nowY++;break;
                case 'R' : nowX++;break;
                case 'L' : nowX--;break;    
            }
            
            if(nowY<-5||nowX<-5||nowY>5||nowX>5){
                nowY=prevY;
                nowX=prevX;
                continue;
            }
            
            int arr[][]={{nowY,nowX},{prevY,prevX}};
            Arrays.sort(arr,new Comparator<>(){
               @Override
                public int compare(int arr1[],int arr2[]){
                    if(arr1[0]>arr2[0])
                        return 1;
                    else if(arr1[0]==arr2[0]){
                        if(arr1[1]>arr2[1]) return 1;
                    }
                    
                    return -1;
                }
            });
            
            set.add(arr[0][0]+" "+arr[0][1]+" "+arr[1][0]+" "+arr[1][1]);
        
           
            prevY=nowY;
            prevX=nowX;
            
        }
        
        return set.size();
        
        
    }
}