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

알고리즘 유형 : 구현 (시뮬레이션)

문제 설명

게임 캐릭터를 4가지 명령어를 통해 움직이려 합니다. 명령어는 다음과 같습니다.

U: 위쪽으로 한 칸 가기

D: 아래쪽으로 한 칸 가기

R: 오른쪽으로 한 칸 가기

L: 왼쪽으로 한 칸 가기

캐릭터는 좌표평면의 (0, 0) 위치에서 시작합니다. 좌표평면의 경계는 왼쪽 위(-5, 5), 왼쪽 아래(-5, -5), 오른쪽 위(5, 5), 오른쪽 아래(5, -5)로 이루어져 있습니다.

---

좌표 평면의 위치만 조심하면 되는 문제다.좌표 평면에서 음수의 위치로 가는 것을 고려해야한다.
0.0으로 시작하면 안되고 5,5에서 시작하면 쉽게 풀리는 문제.

1. 어떻게 주어진 문자대로 움직일 것이냐

• HashMap으로 Character ('U','L' 등) 와 좌표의 움직임 (x,y) 저장 후
• 추후 get으로 key값으로 좌표 움직임을 받아와서 move

2. 동선의 중복 저장을 어떻게 피하냐

• 이 문제에서는 동선의 방향성이 없다. 즉 From-to가 바뀌어도 같은 길이라는 것이다.
• 예시) 1->2 과 2->1은 같은 길이다.
• 그러므로 둘다 저장해야 중복을 막는다.
• 중복체크를 위해서 HashSet을 사용

시간 복잡도 (Time Complexity)

문자열의 길이(N) 만큼 수행
O(N)

import java.util.*;

class Solution {
    public static boolean isIn(int x,int y) {
        return x >= 0 && x < 11 && y >= 0 && y <11;
    }
    public int solution(String dirs) {
        int answer = 0;
        Map<Character,int[]> map = new HashMap<>();

        map.put('U',new int[]{-1,0});
        map.put('D',new int[]{1,0});
        map.put('R',new int[]{0,1});
        map.put('L',new int[]{0,-1});
        int x = 5;int y = 5;
        Set<String> set = new HashSet<>();

        for (int i = 0; i<dirs.length();i++){
            int[] move = map.get(dirs.charAt(i));
            int nx = x + move[0];
            int ny = y + move[1];
            if (!isIn(nx,ny)) continue;
            set.add(x+""+y+","+nx+""+ny);
            set.add(nx+""+ny+","+x+""+y);
            x = nx;
            y = ny;
        }
        return set.size() / 2;
    }
}