[programmers] 방문 길이 - Java

방문 길이

문제 설명

• U: 위쪽으로 한 칸 가기

• D: 아래쪽으로 한 칸 가기

• R: 오른쪽으로 한 칸 가기

• L: 왼쪽으로 한 칸 가기

• 1번 명령어부터 7번 명령어까지 다음과 같이 움직입니다.

• 8번 명령어부터 9번 명령어까지 다음과 같이 움직입니다.

• 1번 명령어부터 6번 명령어대로 움직인 후, 7, 8번 명령어는 무시합니다. 다시 9번 명령어대로 움직입니다.

제한사항

• dirs는 string형으로 주어지며, 'U', 'D', 'R', 'L' 이외에 문자는 주어지지 않습니다.

• dirs의 길이는 500 이하의 자연수입니다.

입출력 예

solution.java

import java.util.HashSet;
import java.util.Set;

class Solution {
    public int solution(String dirs) {        
        // 처음 걸어본 경로를 저장하는 set
        Set<String> visitedPaths = new HashSet<>();
        
        // 시작 위치
        int x = 0, y = 0;
        
        // 각각의 이동에 대한 방향 매핑
        for (char dir : dirs.toCharArray()) {
            int nx = x, ny = y;
            switch (dir) {
                case 'U': ny = y + 1; break;
                case 'D': ny = y - 1; break;
                case 'L': nx = x - 1; break;
                case 'R': nx = x + 1; break;
            }
            
            // 이동한 위치가 경계 내에 있는지 확인
            if (nx < -5 || nx > 5 || ny < -5 || ny > 5) {
                continue; // 경계를 벗어나는 값이라면 무시
            }
            
            // 양쪽 방향으로 경로 식별자 만들기
            String path1 = x + "," + y + "->" + nx + "," + ny;
            String path2 = nx + "," + ny + "->" + x + "," + y;
            
            // 새 경로인 경우 경로 추가
            if (!visitedPaths.contains(path1) && !visitedPaths.contains(path2)) {
                visitedPaths.add(path1);
                visitedPaths.add(path2);
            }
            
            // 새 위치로 이동
            x = nx;
            y = ny;
        }
        
        // 처음 걸어본 경로의 수
        return visitedPaths.size() / 2;
    }
}

핵심 키워드

• 캐릭터의 위치는 (-5, -5)에서 (5, 5) 경계 내에 있어야 한다. 이 경계를 넘어서는 모든 움직임은 무시되어야 한다.

• 두 좌표 사이의 경로를 추적해야 한다. 예를 들어 (x1, y1)에서 (x2, y2)로 이동하는 것이 처음이라면 새 경로로 간주되어야 한다.

• 동일한 경로를 두 번 계산해서는 안 되므로 처음 방문한 경로 집합을 저장해야 한다.
• Set을 사용하여 각 이동의 시작과 끝을 나타내는 점 쌍으로 경로를 저장한다. 처음 방문한 경로를 추적하기 위해 각 경로를 x1,y1->x2,y2와 같은 문자열로 나타낼 수 있다.

결론!