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

📔 문제

프로그래머스

 

• 문제 내용

캐릭터가 지나가는 길을 구하는데 중복으로 지나간 길을 포함하지 않은 처음 걸어본 길의 길이 구하기

 

• 제한 조건

- dirs는 string형으로 주어지며, 'U', 'D', 'R', 'L' 이외에 문자는 주어지지 않습니다.
- dirs의 길이는 500 이하의 자연수입니다.

 

📖 문제 풀이

와.. 진짜 그냥 단순하게 생각했었는데 할까 말까한 부분으로 풀어야 하는 것이 맞았다..

 

계속 붙잡았는데 아무리 생각해도 한 방법 빼고는 안 떠올라서 그냥 책 답안을 보고 풀게 되었다.

 

일단 여러 메소드를 작성해줘서 풀거나 해야 하는 문제였고..

 

내가 처음에 풀었던 방법들은

1번 생각

// 1번으로 생각 했던 것
// 좌표가 중복인 걸 제외하고 나서 그 좌표 길이들을 구하려고 했었다. 
// 그런데 그 좌표 값들을 계산하니 안맞아서 패스

         int dirsS = dirs.length();
         // 중복이면 안됨!
         int[][] arr = new int[dirsS][2];
         int x = 0;
         int y = 0;
        
         for(int i = 0; i < dirs.length(); i++){
             if(dirs.charAt(i) == 'U' && y < 5){
                 y++;
             } else if(dirs.charAt(i) == 'D' && y > -5){
                 y--;
             } else if(dirs.charAt(i) == 'R' && x < 5){
                 x++;

             } else if(dirs.charAt(i) == 'L' && x > -5){
                 x--;
             }
            
             arr[i][0] = x;
             arr[i][1] = y;
             
              //System.out.println("x : " + x + ", y : " + y);
              //System.out.println("i : " + i + ", arr : " + arr.toString());
         }
        
         Arrays.sort(arr, Comparator.comparingInt(a -> a[0]));
         System.out.println(Arrays.deepToString(arr));

2번 생각 

// 2. 일단 죄다 저장하기
// 그다음에 string으로 만들어서 set에 넣기

		 Map<Integer, Integer> arr = new Map<>();
         int x = 0;
         int y = 0;
        
          for(int i = 0; i < dirs.length(); i++){
             if(dirs.charAt(i) == 'U' && y < 5){
                  y++;
             } else if(dirs.charAt(i) == 'D' && y > -5){
                 y--;
             } else if(dirs.charAt(i) == 'R' && x < 5){
                 x++;

             } else if(dirs.charAt(i) == 'L' && x > -5){
                     x--;
             }
              arr.put(x, y);
              System.out.println("x : " + x + ", y : " + y);
              //System.out.println("i : " + i + ", arr : " + arr.toString());
         }
        
         System.out.println(arr.toString());​

3번 생각

// 3. Hash Set에 x좌표 y좌표 넣기 생각
// 이거는 생각부터 잘못함 ㅠ


         HashSet<Integer> x = new HashSet<>();
         HashSet<Integer> y = new HashSet<>();
         int cx = 0;
         int cy = 0;
        
         for(int i = 0; i < dirs.length(); i++){
             if(dirs.charAt(i) == 'U'){
                 if(cy < 5){
                     cy++;
                 }
                 y.add(cy);
             } else if(dirs.charAt(i) == 'D'){
                 if(cy > -5){
                     cy--;
                 }             
                 y.add(cy);
             } else if(dirs.charAt(i) == 'R'){
                 if(cx < 5){
                     cx++;
                 }             
                 x.add(cx);
             } else if(dirs.charAt(i) == 'L'){
                 if(cx > -5){
                     cx--;
                 }             
                 x.add(cx);
             }
         }
        
         System.out.println(x.toString());
         System.out.println(y.toString());

 

여튼 이렇게 하니 도저히 풀 수가 없었다.

 

그래서 책을 참고하니 책에서 해결법을 알려준 방법은

 

1. 0, 0에서 시작하는 좌표를 5, 5로 이동해서 생각하기

2. 만약 범위를 넘어서면 메소드를 이용해 return으로 보내버리기

3. hashset 적극 이용하기

4. UDLR에 따라서 좌표 값 저장하는 메소드 만들기

 

등 이었다.

 

처음에는 읽고 이해하기가 너무 어려 웠는데 이제는 이해가 되었다. 하나씩 쪼개서 분석해보자.

 

일단 제일 쉬운 범위 넘어가면 계산 하지 못하게 하는 메서드이다.

 

5, 5 기준이니 아래와 같이 선언 해주면 하나 해결할 수 있다.

private static boolean isValidMove(int nx, int ny){
        return 0 <= nx && nx < 11 && 0 <= ny && ny < 11;
}

 

 

두 번째 좌표 결정을 위한 해쉬 맵 생성과 해당 하는 값 넣는 initLocation 메서드 생성

 

UDLR의 좌표 방향을 저장해 준다. 그렇기에 Charcter로 UDLR을 각각 쪼개서 저장하고, int[] 배열로 x값과 y값을 넣어준다.

 // 다음 좌표 결정을 위한 해시맵 생성
    private static final HashMap<Character, int[]> location = new HashMap<>();
    
    // Charcter에 기록하고, 해당 좌표를 hashmap에 넣어줌.
    private static void initLocation(){
        location.put('U', new int[]{0, 1});
        location.put('D', new int[]{0, -1});
        location.put('L', new int[]{-1, 0});
        location.put('R', new int[]{1, 0});
    }

 

 

그냥 switch case 방식을 쓰느냐 메소드로 쓰느냐 차이일 거 같은데 아직 해보진 않아서 모르겠다! 일단 이해하는데 초점을 맞추자.

 

그 다음 메인인 solution을 풀어야 한다.

 

일단은 initLocation을 먼저 실행 시켜줘야 한다!

 

그 다음 x와 y의 좌표 값을 5, 5로 이동!

 

자 이제 중요하다 여기가 핵심이다.

 

우리는 String으로 좌표 값을 저장할 것이다. 왜냐하면 그렇게 해야 비교하기도.. 중복을 제거하기도 쉽기 때문이다.

 

그렇기에 HashSet을 String으로 선언해준다.

 

자 그다음 for문으로 한 자씩 돌아가면서 캐릭터를 이동시켜 보자.

 

for문으로 dirs만큼 돌리는 것 까진 쉽다.

 

이 다음부터 또 핵심인 것인데 offset이라는 int 1차원 배열을 선언해준다. 그런데 거기 안에 이제 location 값을 가져오는 거다. 가져오는데 그냥 가져오는 것이 아니라 dirs의 한 글자씩 비교한 값과 아까 선언해준 hashmap의 캐릭터 값을 비교해서 좌표들을 넣어주는 거다.

 

그러니까 만약 첫 글자가 U 라면 값을 비교해서 넣으면 int[] offset = {0, 1}이 되는 것이다.

 

이제 돌아갈 때마다 offset에 새 좌표로 넣어준다.

 

그 다음 nx, ny를 선언해준다. 이것은 5, 5에서 위 좌표 offset 만큼 이동한 값을 더해주기 위한 값이다.

 

	    int[] offset = location.get(dirs.charAt(i));
            
            // 0, 0에서 5,5로 이동
            int nx = x + offset[0];
            int ny = y + offset[1];

 

그 다음에서 좌표 값이 넘어가지 않는지 확인해준다.

 

isValidMove를 이용해서! 아까 쓴 메소드 활용하는 것이다.

 

            // 좌표 벗어날 시에 처리
            if(!isValidMove(nx, ny))
                continue;

 

그 다음 이제 여긴 헷갈릴 수도 있는데 잘 주목해야 한다.

 

x, y, nx, ny 값을 차례로 String 으로 만들어서 저장해줄 것이다.

 

근데 이 방향뿐만 아니라

 

nx, ny, x, y만큼도!

 

왜냐면 내 캐릭터가 5,5에 있는데 5, 6으로 이동했다. 그런데 6, 5 에서도 돌아오는 것도 같은 길을 지나는 것이기 때문에!! 이걸 방지하기 위해 두 개를 다 넣어주는 것이다!!!

 

그렇게 두 개를 다 넣게 되면 우리는 HashSet을 썼기 때문에 중복은 알아서 제거가 된다.

 

그 다음에는 원래 우리 캐릭터가 5, 5에 위치 했는데 이동한 곳으로 위치를 옮겨 주면 된다.

 

            // A에서 B로 간 경우, B에서 A로 간 경우 추가(방향성이 없음)
            // 이걸 해주는 이유는 경로 확인을 위해 양 방향을 모두 저장해준다.
            answer.add(x + " " + y + " " + nx + " " + ny);
            answer.add(nx + " " + ny + " " + x + " " + y);
            
            //System.out.println(answer.toString());
            
            // 현재 좌표로 이동 시킴
            x = nx;
            y = ny;

 

그 다음 마지막으로 

 

양 방향으로 기록 했기 때문에 우리가 구한 answer의 사이즈에서 나누기 2를 해주면 끝이 난다.

 

이렇게 코드 완성

 

✅ 소스 코드

import java.util.*;
import java.io.*;

class Solution {
    // 책 보고 풀음
    // 1. 좌표를 5,5로 옮겨서 좌표를 이동 시킨다
    // 2. 범위가 벗어나면 return 시킨다
    // 3. 방향대로 움직이는 메소드를 생성한다.
    
    private static boolean isValidMove(int nx, int ny){
        return 0 <= nx && nx < 11 && 0 <= ny && ny < 11;
    }
   
    // 다음 좌표 결정을 위한 해시맵 생성
    private static final HashMap<Character, int[]> location = new HashMap<>();
    
    // Charcter에 기록하고, 해당 좌표를 hashmap에 넣어줌.
    private static void initLocation(){
        location.put('U', new int[]{0, 1});
        location.put('D', new int[]{0, -1});
        location.put('L', new int[]{-1, 0});
        location.put('R', new int[]{1, 0});
    }
    
    public int solution(String dirs) {
        initLocation();
        
        //System.out.println(Arrays.deepToString(location));
        int x = 5, y = 5;
        
        // 어디로 이동하든 만약 값이 같게 나온다면 hashSet에서 아예 중복을 제거해버리면
        // 되니까 상관 없음
        HashSet<String> answer = new HashSet<>(); // 겹치는 좌표는 1개로 처리하기 위한
        
        for(int i = 0; i < dirs.length(); i++){
            // 여기서 char값 서로 비교한 값 offset 배열에 넣어준다.
            
            int[] offset = location.get(dirs.charAt(i));
            
            // 0, 0에서 5,5로 이동
            int nx = x + offset[0];
            int ny = y + offset[1];
            
            // 좌표 벗어날 시에 처리
            if(!isValidMove(nx, ny))
                continue;
            
            // A에서 B로 간 경우, B에서 A로 간 경우 추가(방향성이 없음)
            // 이걸 해주는 이유는 경로 확인을 위해 양 방향을 모두 저장해준다.
            answer.add(x + " " + y + " " + nx + " " + ny);
            answer.add(nx + " " + ny + " " + x + " " + y);
            
            //System.out.println(answer.toString());
            
            // 현재 좌표로 이동 시킴
            x = nx;
            y = ny;
        }
    
        
        // 양방향을 쟀으므로 반을 나눠준다
        return answer.size() / 2;
    }
}

 

이걸 책 보고 푸니 좀 더 방법론적으로 다양하게 알고 있었다면 좋았을 텐데 라는 생각이 들었다. 다양하게 하나씩 푸는 것이 많이 도움이 되는 것 같다!

 

다음 번에는 나도 메서드를 좀 적극적으로 사용하고 싶다.

 

다음 번에 만약 쓰게 되면 생각했던 방법으로 또 다시 풀어보고 싶다 ㅠ