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

문제 링크

풀이

중복으로 왔다 갔다 하는걸 어떻게 셀 수 있을까 생각하다가 자바의 컬렉션 프레임워크 중 중복을 허용하지 않는 Set이 있다는 것을 떠올렸다.

(지금 좌표, 움직일 좌표) 이걸 Set에 넣으면 같은 곳을 또 방문했을 때는 중복 저장이 되지 않으므로 Set의 크기가 방문 길이가 될 것이다. 라고 생각했다.

그런데 예제 중

입력값 〉	"UDUDUDUD"
기댓값 〉	1

이걸 보고 이 상태로 짜면 2가 나오는데, 고민한 결과 추가로 (지금 좌표, 움직일 좌표) 뿐만 아니라 (움직일 좌표, 지금 좌표)를 기록한 후 2를 나누면 된다는 결론이 나왔다. 왜냐하면 예제 그대로 왔던 곳을 다시 돌아가는 것은 한번 움직인 것이기 때문이다. 그래서 모든 구간을 왔다 갔다 두 번 한 걸로 기록하면 여러곳을 빙빙 돌다가 다시 왔을 때, 양방향으로 문질러 놨으므로(?) 기록 되지 않는다. 그리고 모두 두 번씩 간 걸로 더했기 때문에 마지막엔 2로 나눠주면 원하는 길이가 나온다는 결론이였다.

즉,

set.add(지금좌표, 움직일좌표)
set.add(움직일좌표, 지금좌표)

이렇게 추가하고 2로 나눠주면 된다는 것이다.

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

public class Solution
{
    public int solution(String dirs) {
        int answer = 0;
        char[] command = dirs.toCharArray();
        int x = 0;
        int y = 0;
        int[] dx = {0,0,-1,1};
        int[] dy = {1,-1,0,0};
        Set<String> movement = new HashSet<String>();
        for(int i = 0; i< command.length; i++) {

            if (command[i] == 'U' && y < 5) {
                movement.add(Arrays.toString(new int[]{x,y,x+dx[0],y+dy[0]}));
                movement.add(Arrays.toString(new int[]{x+dx[0],y+dy[0],x,y}));
                y++;

            } else if (command[i] == 'D' && y > -5) {
                movement.add(Arrays.toString(new int[]{x,y,x+dx[1],y+dy[1]}));
                movement.add(Arrays.toString(new int[]{x+dx[1],y+dy[1],x,y}));
                y--;


            } else if (command[i] == 'L' && x > -5 ) {
                movement.add(Arrays.toString(new int[]{x,y,x+dx[2],y+dy[2]}));
                movement.add(Arrays.toString(new int[]{x+dx[2],y+dy[2],x,y}));
                x--;

            } else if (command[i] == 'R' && x < 5) {
                movement.add(Arrays.toString(new int[]{x,y,x+dx[3],y+dy[3]}));
                movement.add(Arrays.toString(new int[]{x+dx[3],y+dy[3],x,y}));
                x++;

            }

        }
        return movement.size()/2;

    }

}