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

프로그래머스 - 방문 길이

풀이

1. 각 명령어와 알맞는 방향을 Map 으로 저장 ➡️ get() 으로 편하게 사용하기 위해
2. visited 리스트를 만들어서 방문했던 경로 저장
   ✔️(0, 0) -> (1, 0) 을 방문했으면 0010 문자열로 저장
   ❗️(1, 0) -> (0, 0) 과 같은 경로이기 때문에 1000 문자열도 저장해야함
3. visited 리스트에 저장된 경로 -> 새로 방문한 경로 -> 개수 리턴
   ❗️중복해서 저장했기 때문에 visited.size() / 2 를 리턴

---

삽질

처음에는 좀 복잡하게 풀려고 했다.
visited를 String 리스트로 만들지 않고 Map으로 구현하려고 했다.

만약 (0, 0) -> (1, 0) 을 표현한다고 하면 아래와 같이 구현하려 했다.

[0, 0] -> {{1, 0}, ...}
[1, 0] -> {{0, 0}, ...}

그런데! 하우에버!

맵은 객체를 저장하기 때문에 int배열을 찾고 넣는 것에 애를 먹었다.

HashMap<int[], List<int[]>> visited = new HashMap<>();

// visited에 [0, 0] -> {{1, 0}, ...} 가 저장되어 있다고 가정

int[] from = new int[]{0, 0};
int[] to = new int[]{1, 0};

if (!visited.containsKey(new int[]{0, 0})) {...}	// 못찾음
if (!visited.get(new int[]{0, 0}).contains(new int[]{1, 0})) {...}	// 못찾음

위 코드에서 두 개의 if 조건이 무조건 true가 된다!
새로운 객체니까 당연히!

이 문제를 해결하기 위해 객체의 값에 접근해서 같으면 true를 반환하는 새로운 메소드를 정의해서 사용하려다가 너무 비효율적인 것 같아서 던졌다! 1시간 삭제! 하하하

visited를 String으로 바꿔서 작성하니까 정말 쉽게 끝났다........

이래서 자료구조 선택하는게 참 중요한 듯^^..

---

코드

import java.util.*;

public class VisitedLength {
	public int solution(String dirs) {
		int size = 5;
		HashMap<String, int[]> UDRL = new HashMap<>(){};
		UDRL.put("U", new int[]{0, 1});
		UDRL.put("D", new int[]{0, -1});
		UDRL.put("R", new int[]{1, 0});
		UDRL.put("L", new int[]{-1, 0});

		List<String> visited = new ArrayList<>();

		int x = 0;
		int y = 0;
		for (String direction : dirs.split("")) {
			int nx = x + UDRL.get(direction)[0];
			int ny = y + UDRL.get(direction)[1];

			if (Math.abs(nx) <= size && Math.abs(ny) <= size) {
				String from = "" + x + y;
				String to = "" + nx + ny;

				if (!visited.contains(from + to)) {
					visited.add(from + to);
					visited.add(to + from);
				}
				x = nx;
				y = ny;
			}
		}
		return visited.size() / 2;
	}

	public static void main(String[] args) {
		VisitedLength visitedLength = new VisitedLength();
		System.out.println(visitedLength.solution("ULURRDLLU"));    // 7
		System.out.println(visitedLength.solution("LULLLLLLU"));    // 7
	}
}