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

문제

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

프로그래머스

 

풀이

• 게임 캐릭터에게 상하좌우로 한 칸씩 움직이는 명령을 내린다. 명령어는 순서대로 UDLF이다.
• 게임 캐릭터는 좌표평면 (0,0)에 위치하고, 좌표는 5X5 크기이다.
• 게임 캐릭터가 지나간 길 중 캐릭터가 처음 걸어본 길의 길이를 구한다. 움직인 총 이동거리에서 한번 가본 길을 지날 때는 이동거리에 포함시키지 않는다는 뜻이다.
• 또한 좌표평명 밖으로 이동하는 명령어가 입력된 경우, 그 명령은 무시한다.
• dirs는 UDRL 이외는 주어지지 않으며, 길이는 500 이하의 자연수다.

"ULURRDLLU"나 "LULLLLLLU" 같은 방식으로 dirs가 주어진다. chatAt()을 통해 문자열을 문자로 분리한다.

처음 가본 길의 길이를 구해야 한다. 두 번째, 세 번째로 가는 길은 길이에 포함하지 않는 것이다. 중복을 제거해야 하기 때문에 HashSet으로 경로를 다루는 것이 유용할 것이다.

 

좌표는 현재 좌표를 두고 입력된 문자에 따라 다음 좌표를 구해야 한다. switch문을 사용해 U이라면 좌표의 y 값을 +1, L이라면 좌표의 x 값을 -1 같은 방식으로 다음 좌표 (nx, ny)를 구한다.

다음 좌표가 좌표 평면 밖으로 나간 경우라면 명령을 무시해야 한다. x, y 좌표가 둘 다 6 이상, -6 이하라면 continue를 사용해 반복문을 다음으로 넘긴다.

int x = 0;
int y = 0;

HashSet<String> set = new HashSet<>();

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

    int nx = x;
    int ny = y;

    switch (command) {
    case 'U':
        ny += 1;
        break;

    case 'D':
        ny -= 1;
        break;

    case 'R':
        nx += 1;
        break;

    case 'L':
        nx -= 1;
        break;
    }

    if (nx <= -6 || nx >= 6 || ny <= -6 || ny >= 6)
        continue;
    
    ...
}

 

길에는 방향성이 존재하지 않는다. (x, y)에서 (nx, ny)로 이동하는 경우와 (nx, ny)에서 (x, y)로 이동하는 경우는 같은 것이라는 뜻이다. 따라서 HashSet에 경로를 추가할 때, 두 경우 모두 생각해야 한다.이동 후에는 현재 위치를 (nx, ny)로 바꾸어 준다.

set.add(String.format("(%d, %d) -> (%d, %d)", x, y, nx, ny));
set.add(String.format("(%d, %d) -> (%d, %d)", nx, ny, x, y));

x = nx;
y = ny;

 

최종적으로 set에는 한 가지 경로가 두 번 저장되어 있다. set의 크기의 ÷2 한 값이 출력되어야 한다.

 

 

전체 코드 (Java)

import java.util.*;

class Solution {
    public int solution(String dirs) {
		int x = 0;
		int y = 0;
		
		HashSet<String> set = new HashSet<>();

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

			int nx = x;
			int ny = y;

			switch (command) {
			case 'U':
				ny += 1;
				break;

			case 'D':
				ny -= 1;
				break;

			case 'R':
				nx += 1;
				break;

			case 'L':
				nx -= 1;
				break;
			}

			if (nx <= -6 || nx >= 6 || ny <= -6 || ny >= 6)
				continue;
				
			set.add(String.format("(%d, %d) -> (%d, %d)", x, y, nx, ny));
			set.add(String.format("(%d, %d) -> (%d, %d)", nx, ny, x, y));

			x = nx;
			y = ny;
		}
		
		return set.size() / 2;
	}
}

 

 

후기

경로를 어떤 식으로 저장할지 고민을 많이 하였던 문제이다. 문자열로 자유롭게 저장하는 방법을 빨리 떠올리지 못했다. 좀 더 유연하게 생각할 필요가 있는 것 같다.