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

문제 설명

https://school.programmers.co.kr/learn/courses/30/lessons/49994

프로그래머스

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

• U: 위쪽으로 한 칸 가기
• D: 아래쪽으로 한 칸 가기
• R: 오른쪽으로 한 칸 가기
• L: 왼쪽으로 한 칸 가기

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

예를 들어, "ULURRDLLU"로 명령했다면

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

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

이때, 우리는 게임 캐릭터가 지나간 길 중 캐릭터가 처음 걸어본 길의 길이를 구하려고 합니다. 예를 들어 위의 예시에서 게임 캐릭터가 움직인 길이는 9이지만, 캐릭터가 처음 걸어본 길의 길이는 7이 됩니다. (8, 9번 명령어에서 움직인 길은 2, 3번 명령어에서 이미 거쳐 간 길입니다)

단, 좌표평면의 경계를 넘어가는 명령어는 무시합니다.

예를 들어, "LULLLLLLU"로 명령했다면

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

이때 캐릭터가 처음 걸어본 길의 길이는 7이 됩니다.

명령어가 매개변수 dirs로 주어질 때, 게임 캐릭터가 처음 걸어본 길의 길이를 구하여 return 하는 solution 함수를 완성해 주세요.

제한 사항

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

입출력 예

dirs	answer
"ULURRDLLU"	7
"LULLLLLLU"	7

입출력 예 설명

입출력 예 #1

• 문제의 예시와 같습니다.

입출력 예 #2

• 문제의 예시와 같습니다.

 

내가 작성한 코드

import java.util.*;

class Solution {
    public int solution(String dirs) {
        // 방문 길이를 저장할 변수 생성
        int answer = 0;
        
        // 시작 좌표 (0, 0)
        int x = 0, y = 0;
        
        // 지나간 길(간선)을 저장하는 Set
        // 방향을 무시하고 한 번만 저장하기 위해 문자열 key로 관리
        Set<String> path = new HashSet<>();
        
        // 주어진 이동 명령을 하나씩 처리
        for (int i = 0; i < dirs.length(); i++) {
            // 이동 명령 받아오기
            char c = dirs.charAt(i);
            
            // 이동 후 좌표 위치
            int nx = x;
            int ny = y;
            
            // 명령어에 따라 다음 좌표 계산
            if (c == 'U') {
                ny++;
            } else if (c == 'D') {
                ny--;
            } else if (c == 'L') {
                nx--;
            } else if (c == 'R') {
                nx++;
            }
            
            // 좌표 범위가 -5 ~ 5 안쪽일 때만 이동 가능
            if (nx < -5 || nx > 5 || ny < -5 || ny > 5) {
                continue;
            }
            
            // 이동한 길을 저장 (방향과 관계없이 동일한 길로 처리)
            path.add(edgeKey(x, y, nx, ny));
            
            // 실제 좌표 갱신
            x = nx;
            y = ny;
        }
        
        // 지나간 길 개수 저장
        answer = path.size();
        
        // 정답 반환
        return answer;
    }
    
    // 간선을 방향에 관계없이 동일하게 저장하기 위한 key 생성 메서드
    private String edgeKey(int x1, int y1, int x2, int y2) {
        // 작은 좌표 -> 큰 좌표 순으로 정렬해서 문자열 생성
        if (x1 < x2 || (x1 == x2 && y1 <= y2)) {
            return x1 + "," + y1 + "->" + x2 + "," + y2;
        } else {
            return x2 + "," + y2 + "->" + x1 + "," + y1;
        }
    }
}

문제를 풀기 위해 생각한 방향

처음 문제를 봤을 때, “좌표 평면에서 캐릭터가 U/D/L/R로 이동할 때 처음 지나가는 길(간선)만 길이로 센다”는 점이 핵심이라고 판단했다. 따라서 점(좌표) 방문 여부가 아니라, 두 좌표 사이의 경로 자체가 새롭냐를 판별해야 한다고 보았다. 시작 지점은 (0, 0)이며, 좌표는 -5부터 5까지만 유효하다는 제약이 있으므로 경계 밖으로 나가는 이동은 무효로 처리해야 한다고 정리했다.

조건을 분석해 보면, 동일한 선분을 왕복했을 때 (A → B)와 (B → A)는 같은 길로 간주해야 한다. 또한 이동 명령을 순서대로 수행하면서, 각 이동이 유효할 때만 “이번 이동으로 생성된 길”을 중복 없이 저장하고, 마지막에 저장된 서로 다른 길의 개수를 반환하면 된다. 이때 경계를 벗어나는 이동은 길로 세지도 않고 위치도 바꾸지 않는다는 점이 중요하다.

자료구조는 HashSet을 선택했다. 이유는 첫째, 이미 지나간 길인지 빠르게 확인하기 위해서이고, 둘째, Set 특성상 중복을 자동으로 제거해 주기 때문이다. 길은 두 점으로 이루어진 무향 간선이므로, (x1, y1) - (x2, y2)와 (x2, y2) - (x1, y1)가 동일한 키가 되도록 정규화가 필요하다. 본 코드는 edgeKey(x1, y1, x2, y2)에서 항상 작은 쪽 좌표를 앞에 두는 방식으로 문자열 키를 만들었고, 이렇게 하면 방향이 달라도 같은 문자열이 생성되어 한 번만 저장된다.

로직 흐름은 다음과 같다.

1. 현재 좌표 (x, y)에서 명령 문자 하나를 읽고, 이동 후보 좌표 (nx, ny)를 계산한다.
2. 후보가 경계 [-5, 5]를 벗어나면 이동을 무시하고 다음 명령으로 넘어간다.
3. 후보가 유효하면, 현재 좌표와 후보 좌표로부터 정규화된 간선 키를 만들어 Set에 추가한다.
4. 그다음 실제 위치를 (nx, ny)로 갱신한다.
   모든 명령을 처리한 뒤 Set에 담긴 간선의 개수가 곧 처음 지나간 길의 개수이므로 이를 반환한다.

시간복잡도는 이동 명령 길이를 n이라 할 때 O(n)이다. 각 이동마다 문자열 키 생성과 HashSet 삽입/조회가 평균 O(1)이므로 전체는 선형이다. 공간복잡도는 저장되는 서로 다른 길의 수를 k라 할 때 O(k)이며, k는 최대 n을 넘지 않는다. 문자열 키 생성에 따른 오버헤드는 있지만, 좌표 범위가 작고 입력 길이가 과도하게 크지 않은 문제 특성상 충분히 효율적이라고 판단했다. 만약 문자열 생성 오버헤드를 더 줄이고 싶다면, 작은 Edge 클래스에 equals/hashCode를 정의하거나, 정수 포맷(예: 비트 패킹)으로 키를 구성하는 방법도 대안이 될 수 있다.

정리하면, 이 풀이는 경계 체크로 무효 이동을 배제, 무향 간선 정규화로 왕복 중복 제거, Set으로 처음 지나간 길만 카운트한다는 세 가지 포인트를 일관되게 구현한 방식이다.