[Lv.2] 방문 길이 : Java / 간선 방문 확인

프로그래머스

 

좌표가 아니라 "길(간선)"을 HashSet으로 관리

>양방향 간선으로 넣어줘야 함 => 길 개수 구할 때 size()/2 해줘야 함

*HashSet 사용하는 이유 : 중복 카운트하지 않으려고

*마지막에 HashSet크기/2하는 이유 (5,5) → (5,6)랑 (5,6) → (5,5) 둘이 같은 길이니

 

 

#알고리즘 순서

1 시작 좌표 (0,0)

2 명령 하나씩 처리
   → 다음 좌표(nx, ny) 계산

3 범위 체크 (-5 ~ 5)
   → 범위 밖이면 무시

4 길 저장
   (x,y,nx,ny)
   (nx,ny,x,y)

5 현재 좌표 이동
   x = nx
   y = ny

6 마지막에 set.size()/2 반환

 

*HashSet<String> 형식으로 "x, y, nx, ny" 식의 문자열 형태로 저장

import java.util.*;

class Solution {
    public int solution(String dirs) {
        Set<String> visited = new HashSet<>();

        // 현재 위치
        int cx = 0;
        int cy = 0;

        for (int i = 0; i < dirs.length(); i++) {
            char d = dirs.charAt(i);

            // 다음 위치 (현재 위치 기준)
            int nx = cx;
            int ny = cy;

            if (d == 'U') {
                ny++;
            } else if (d == 'D') {
                ny--;
            } else if (d == 'L') {
                nx--;
            } else { // R
                nx++;
            }

            // 경계 밖이면 이동 무시
            if (nx < -5 || nx > 5 || ny < -5 || ny > 5) {
                continue;
            }

            // 간선 저장 (양방향)
            String path1 = cx + "," + cy + "->" + nx + "," + ny;
            String path2 = nx + "," + ny + "->" + cx + "," + cy;

            visited.add(path1);
            visited.add(path2);

            // 현재 위치 갱신
            cx = nx;
            cy = ny;
        }

        // 양방향으로 2번 저장했으므로 2로 나눔
        return visited.size() / 2;
    }
}