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

1. 문제

---

프로그래머스

2. 풀이 과정

핵심 로직

1. 처음 걸어본 길의 길이를 구해야 하므로 중복해서 걸은 길은 체크하지 않는다.
2. 만약 좌표의 범위를 넘어서는 걸음이 있다면 그 걸음은 무시한다.

2시간 넘게 풀어보다가 결국엔 실패했다. 

막힌 부분: 핵심 로직 1번

접근 방식

1. 처음에는 각 좌표평면의 모든 점과 1:1 대응되는 2차원 배열을 만들어 해당 점을 방문할 때 마다 방문 처리를 하고
   이후에 움직인 지점이 이미 방문 처리가 된 곳이라면 이미 걸은 길이라고 판단

 

하지만 이렇게 하면 다음의 경우 문제가 발생한다.

7번 움직임의 경우 도착점이 이미 방문한 적이 있는 곳인데 실제로 해당 길은 걸어본 적이 없다. 

따라서 이 로직은 틀린 로직이다.

 

뻘짓 흔적...

import java.util.*;
class Solution {
    public int solution(String dirs) {
        boolean[][] before_walk = new boolean[11][11];
        // 캐릭터의  초기 위치
        int cur_x = 5;
        int cur_y = 5;
        
        before_walk[5][5] = true; // 초기 위치 걸음 처리
        
        int total_walk = 0; // 캐릭터가 총 걸은 거리
        
        for(int i = 0; i < dirs.length(); i++) {
            char move = dirs.charAt(i);
            if(isNotOver(cur_x, cur_y, move)){ // 범위를 넘어서 걷는지 체크
             
                // 현재 위치 기억해두기
                int before_x = cur_x;
                int before_y = cur_y; 
                
                // 걷기
               if(move == 'U') {
                    cur_y++;    
                } else if(move == 'D') {
                    cur_y--;
                } else if(move == 'R') {
                    cur_x++;
                } else if(move == 'L') {
                    cur_x--;
                }     
                
                if(before_walk[before_x][before_y] && before_walk[cur_x][cur_y]) { 
                
                } else { // 해당 위치를 이전에 걸은적이 없다면 
                    total_walk++;
                    before_walk[cur_x][cur_y] = true; // 해당 위치 걸음 처리
                }
            
            } 
        }
        return total_walk;
    }
    
    // 해당 움직임이 좌표평면 범위를 넘어서는지 체크
    private boolean isNotOver(int x, int y, char move) {
        boolean result = true;
        if(move == 'U') {
            if(y == 10) {
                result = false;
            }
        } else if(move == 'D') {
            if(y == 0) {
                result = false;
            }
        } else if(move == 'R') {
            if(x == 10) {
                result = false;
            }
        } else if(move == 'L') {
            if(x == 0) {
                result = false;
            }
        }
        return result;
    }
}

 

2. 중복처리에 특화된 HashSet에 움직일 때마다 길 정보를 넣어서 처리

 

HashSet을 사용하는 건 좋은데 그 Set 안에 길 정보를 어떻게 넣어줘야 하나 고민이었다...

하나의 길은 두 개의 점이 있어야 존재하므로 그 두 개의 점을 포함하는 하나의 클래스를 만들어 Set에 넣으면 어떨까 생각도 해봤는데 Set에 객체를 넣으면 그 객체의 값을 기반으로 비교하는 것이 아닌 객체 자체의 주소값을 통해 비교하기 때문에 이는 불가능했다. 

---

이렇게 두 시간을 뻘짓하다 도저히 답이 나올 것 같지 않아 풀이를 보았다.

3. 정답 코드

---

import java.util.HashMap;
import java.util.HashSet;

public class Solution {

    // ❶ 좌표평면을 벗어나는지 체크하는 메소드
    private static boolean isValidMove(int nx, int ny) {
        return 0 <= nx && nx < 11 && 0 <= ny && ny < 11;
    }

    // ❷ 다음 좌표 결정을 위한 HashMap 생성
    private static final HashMap<Character, int[]> location = new 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();
        int x = 5, y = 5;
        HashSet<String> answer = new HashSet<>(); // ❸ 겹치는 좌표는 1개로 처리하기 위함
        // ❹ 주어진 명령어로 움직이면서 좌표 저장
        for (int i = 0; i < dirs.length(); i++) {
            int[] offset = location.get(dirs.charAt(i));
            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);
            // ❼ 좌표를 이동했으므로 업데이트
            x = nx;
            y = ny;
        }

        return answer.size() / 2;
    }

}

시간복잡도

• O(N)

정답 코드를 보고 그냥 어이가 없어 웃음이 나왔다... 왜 문자열로 저장할 생각을 못했을까... 어차피 길에 대해서 식별만 할 수 있으면 되는데 괜히 클래스 선언이니 뭐니 하면서 어렵게 생각했던 것 같다... 

 

코드에서 HashMap을 사용하는 부분도 있는데 이 부분은 코드의 가독성을 위해 사용된 것 같다.