처음가본길만을 구하는 문제이므로, 중복되는 길은 선택하지 않는다는의미.
처음엔 최종적으로 위치해있는 지점의 x축 절댓값 + y축 절댓값을 더하면된다생각했는데 그건 아니었다.
어떻게 접근해야할까?
이동할때마다의 좌표를 저장하고 cnt를 ++ 해주면서, 저장된 좌표로 다시 이동하게되면 cnt를 해주지않고 넘어가는 방식으로 해야하나 싶다. 그런데 문제는 파라미터로 주어지는 dirs의 길이는 500이하다. 최대 500번의 좌표를 저장하게되면 런타임에러가 발생하지 않을까 싶다. 일단 한번 이렇게 해보겠다.
수도코드를 짜보자.
// 먼저 (x,y)좌표를 나타낼 길이가 2인 int형 배열 xy를 초기화해주자. int[] xy = new int[2];
// 그다음 xy의 history를 담을 리스트로 ArrayList를 만들어주자.
// dir을 처음부터 순회하면서 조건문을 걸어준다. U가 나오면 y + 1, D가 나오면 y - 1, R이 나오면 x + 1, L이 나오면 x - 1
// xy의값이 바뀔때마다 cnt++
// cnt++ 되기전에 조건문을 하나 걸어준다. history에서 중복된값이 있으면 cnt를 안해주고 xy의값만 바꿔주고 history에 넣지않는다.
// 조건문에 다른조건을 하나걸어주는데, x나 y가 5를 넘지 않게 해준다. 넘는경우엔 다음 dir로 넘어간다.
// 최종적 cnt를 반환한다.
public static int solution(String dirs) {
int cnt = 0;
int[] xy = new int[]{0, 0};
List<int[]> history = new ArrayList<>();
for (int i = 0; i < dirs.length(); i++) {
char UDRL = dirs.charAt(i);
int[] nextXY = xy.clone(); // xy 배열의 복사본을 생성하여 nextXY에 할당
switch (UDRL) {
case 'U':
if (Math.abs(nextXY[1] + 1) <= 5) {
nextXY[1] += 1;
if (!containsXY(history, nextXY)) {
cnt++;
}
history.add(nextXY);
System.out.println(cnt);
}
break;
case 'D':
if (Math.abs(nextXY[1] - 1) <= 5) {
nextXY[1] -= 1;
if (!containsXY(history, nextXY)) {
cnt++;
}
history.add(nextXY);
System.out.println(cnt);
}
break;
case 'R':
if (Math.abs(nextXY[0] + 1) <= 5) {
nextXY[0] += 1;
if (!containsXY(history, nextXY)) {
cnt++;
}
history.add(nextXY);
System.out.println(cnt);
}
break;
case 'L':
if (Math.abs(nextXY[0] - 1) <= 5) {
nextXY[0] -= 1;
if (!containsXY(history, nextXY)) {
cnt++;
}
history.add(nextXY);
System.out.println(cnt);
}
break;
}
xy = nextXY; // 다음 반복을 위해 xy를 업데이트
}
return cnt;
}그런데 이렇게하면 문제가 발생한다.
history를 출력해보면,
[0, 1]
[-1, 1]
[-1, 2]
[0, 2]
[1, 2]
[1, 1]
[0, 1]
[-1, 1]
[-1, 2]
그리고 중복을 검사할때나는 한번갔다온 길이 아닌 한번 거쳐간 점을 검사해서 자꾸 틀렸던것이었다.
이걸 문제푼지 거의 3시간만에 알게되었다.
그래서 지피티에게 물어보니 Set으로 풀더라.
public static int solution(String dirs) {
int cnt = 0;
int[] xy = new int[]{0, 0};
Set<String> history = new HashSet<>(); // 각 지점을 문자열로 저장하여 중복 방문 여부 확인
for (int i = 0; i < dirs.length(); i++) {
char move = dirs.charAt(i);
int[] nextXY = xy.clone(); // 다음 지점을 계산하기 위해 현재 지점 복사
// 이동
switch (move) {
case 'U':
if (xy[1] < 5) nextXY[1]++;
break;
case 'D':
if (xy[1] > -5) nextXY[1]--;
break;
case 'R':
if (xy[0] < 5) nextXY[0]++;
break;
case 'L':
if (xy[0] > -5) nextXY[0]--;
break;
}
// 이동한 지점이 경계를 벗어나지 않는지 확인하고, 중복 방문을 허용하지 않으면서 카운트
if (nextXY[0] != xy[0] || nextXY[1] != xy[1]) { // 이동했는지 여부 확인
String path = xy[0] + "," + xy[1] + "->" + nextXY[0] + "," + nextXY[1];
if (!history.contains(path)) { // 중복 방문 확인
history.add(path);
cnt++;
}
}
xy = nextXY; // 현재 지점 갱신
}
return cnt;
}풀이를 보고 내일 다시 풀어보도록 해야겠다.
한문제를 3시간동안 고민하니 진이 빠진다.ㅠ
