[Java] 프로그래머스(level-2) - 방문 길이
문제 풀이
이 문제는 HashSet 자료구조 를 이용해 풀 수 있다.
아이디어 도출
HashSet 자료구조를 사용해보기 전에는, 단순히 상, 하, 좌, 우로 이동한 횟수를 카운트 했었는데, 이미 다녀온 중복 이동을 고려하기 어려웠다. 이를 HashSet으로 중복을 제거하여 해결할 수 있었다.
문제 풀이를 위한 아이디어는 다음과 같다.
- (0,0) 위치부터 dirs 문자열을 순회하여
U, D, L, R명령에 따라 1,-1씩 움직인다. - 상, 하, 좌, 우로 움직일 경우를 각각 고려하여 문자열에 위치정보를 담는다.
- 움직인 위치가 이동 칸의 범위(최소 -5, 최대 5)를 벗어나지 않았다면 HashSet에 위치정보를 담은 문자열을 삽입하고 현재 위치를 움직인 위치로 갱신한다.
- HashSet의 크기가 곧 이동횟수가 된다.
어떻게 다녀온 위치 중복을 제거하나?
HashSet에 삽입하여 중복을 제거하기 위해 String 문자열에 위치를 담아서 중복을 해결했는데 그 절차는 다음과 같다.
상, 우 로 움직일 경우 [현재x좌표][현재y좌표][다음x좌표][다음y좌표] 형식으로 문자열을 만들고,
하, 좌 로 움직일 경우 [다음x좌표][다음y좌표][현재x좌표][현재y좌표] 형식으로 문자열을 만든다.
U
"[현재x좌표][현재y좌표][다음x좌표][다음y좌표]"
D
"[다음x좌표][다음y좌표][현재x좌표][현재y좌표]"
R
"[다음x좌표][다음y좌표][현재x좌표][현재y좌표]"
L
"[현재x좌표][현재y좌표][다음x좌표][다음y좌표]"
이렇게 문자열을 구성하면 이동시 중복되는 위치의 중복을 해결할 수 있게 된다.
문제 풀이를 위해 작성한 코드는 아래와 같다.
작성 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
import java.util.*;
class Solution {
public int solution(String dirs) {
// 방문 위치를 담을 HashSet
HashSet<String> visited = new HashSet<>();
// 11*11 크기의 배열의 중심점 (0,0)
int nowX = 0;
int nowY = 0;
for(int idx=0; idx<dirs.length(); idx++) {
// 다음으로 이동할 좌표 초기화
int x = nowX;
int y = nowY;
// 위치정보를 문자열 형태로 담기 위한 변수
String location = "";
/**
* 상: y좌표+1, [nowX][nowY][nextX][nextY]
* 하: y좌표-1, [nextX][nextY][nowX][nowY]
* 좌: x좌표-1, [nextX][nextY][nowX][nowY]
* 우: x좌표+1, [nowX][nowY][nextX][nextY]
*/
switch(dirs.charAt(idx)) {
case 'U':
y++;
location += nowX;
location += nowY;
location += x;
location += y;
break;
case 'D':
y--;
location += x;
location += y;
location += nowX;
location += nowY;
break;
case 'R':
x++;
location += nowX;
location += nowY;
location += x;
location += y;
break;
case 'L':
x--;
location += x;
location += y;
location += nowX;
location += nowY;
break;
default:
break;
}
// 좌표 범위 벗어나면 이동하지 않음
if(x < -5 || x > 5 || y < -5 || y > 5) {
continue;
}
visited.add(location);
// 현재 위치를 이동한 위치로 갱신
nowX = x;
nowY = y;
}
return visited.size();
}
public static void main(String[] args) {
Solution sol = new Solution();
// String dirs = "ULURRDLLU";
// String dirs = "LULLLLLLU";
// String dirs = "LURDLURDLURDLURDRULD";
// String dirs = "RRRRRRRRRRRRRRRRRRRRRUUUUUUUUUUUUULU";
// String dirs = "RRRRRLLLLL";
String dirs = "UDU";
sol.solution(dirs);
}
}
회고
출처
- —
- 해당 문제의 저작권은 문제를 만든이에게 있으며 자세한 내용은 문제 링크에서 참조바랍니다.