링크

문제 링크

문제 설명

게임 캐릭터를 4가지 명령어를 통해 움직이려 합니다. 명령어는 다음과 같습니다.

U: 위쪽으로 한 칸 가기

D: 아래쪽으로 한 칸 가기

R: 오른쪽으로 한 칸 가기

L: 왼쪽으로 한 칸 가기

캐릭터는 좌표평면의 (0, 0) 위치에서 시작합니다. 좌표평면의 경계는 왼쪽 위(-5, 5), 왼쪽 아래(-5, -5), 오른쪽 위(5, 5), 오른쪽 아래(5, -5)로 이루어져 있습니다.

예를 들어, "ULURRDLLU"로 명령했다면

1번 명령어부터 7번 명령어까지 다음과 같이 움직입니다.

8번 명령어부터 9번 명령어까지 다음과 같이 움직입니다.

이때, 우리는 게임 캐릭터가 지나간 길 중 캐릭터가 처음 걸어본 길의 길이를 구하려고 합니다. 예를 들어 위의 예시에서 게임 캐릭터가 움직인 길이는 9이지만, 캐릭터가 처음 걸어본 길의 길이는 7이 됩니다. (8, 9번 명령어에서 움직인 길은 2, 3번 명령어에서 이미 거쳐 간 길입니다)

단, 좌표평면의 경계를 넘어가는 명령어는 무시합니다.

예를 들어, "LULLLLLLU"로 명령했다면

1번 명령어부터 6번 명령어대로 움직인 후, 7, 8번 명령어는 무시합니다. 다시 9번 명령어대로 움직입니다.

이때 캐릭터가 처음 걸어본 길의 길이는 7이 됩니다.

명령어가 매개변수 dirs로 주어질 때, 게임 캐릭터가 처음 걸어본 길의 길이를 구하여 return 하는 solution 함수를 완성해 주세요.

제한 사항

dirs는 string형으로 주어지며, 'U', 'D', 'R', 'L' 이외에 문자는 주어지지 않습니다.
dirs의 길이는 500 이하의 자연수입니다.

입출력 예

입출력 예 설명

입출력 예 #1
문제의 예시와 같습니다.

입출력 예 #2
문제의 예시와 같습니다.

풀이

1. 현재 위치좌표(x좌표, y좌표) 그리고 방향(dir)을 담은 Point 객체를 선언한다.
2. 이 객체를 자료형으로 List에 담아 많은 메소드를 지원받자.
3. dirs 명령어마다 양방향으로 2개의 Point 좌표를 add한다.
4. add 하기전엔 항상 list의 contains 메소드를 활용하여 있는 원소인지 확인하기!
5. contains는 내부적으로 equals()를 사용하며 "객체"를 비교하기 때문에 Point 클래스에서 equals()를 오버라이드하여 객체의 값을 비교해주게 기능을 변경하자!!!!!

이 문제 엄청 오래걸렸다..

처음에 어떻게 풀려했냐면 10X10 2차원 boolean 배열을 선언한 뒤 (5,5)에서 시작하여 지나간 곳은 True로 마킹하여 마킹된 곳의 개수를 세려했다.

누가봐도 메모리를 훨씬 절약한다는 점에서 이 풀이에 꽂혀가지고 다른 풀이는 생각도 하지않고 시간을 낭비하고 있었다..

그리고 실제로 이 방법만이 이쁜 정답일 줄 알았다 ㅜㅜ

지금 메모리를 거의 남발해버린 내 코드를 보면 솔직히 저 방법이 아직도 욕심난다!

그러나 저 방법은 X축 Y축을 생각해서 배열의 크기가 10X10이 맞는지 11X11이 맞는지 죽도록 헷갈렸다...

하... 그래서 대충 내가 제작한 테스트케이스와 질문 목록에 올라와있는 반례? 들도 다 통과한다고 생각했을시점 제출하니 시뻘건 창 뿐이었다...

그래서 시간도 시간이니 메모리를 좀 팍팍 써보기로 했다.

boolean만 고집하다가 (x,y,dir) (int,int,char)로 메모리를 후하게 두었다!

이렇게되면 풀이는 간단해진다. -5와 5를 벗어나지 않으면 한번 이동마다 list.contains로 이미 왔던 길인지 확인해주고 양방향으로 두 개씩 add해주면 되니까!

근데 contains가 또 객체를 비교하는거라서 equals()를 오버라이드해서 다른 객체더라도 값만 같으면 True를 반환해주게끔 해야했다..

그러면 실제로 내가 "처음 걸어본 길의 길이" X 2가 배열의 크기가 될텐데 이를 반으로 나눠서 리턴해주니 성공!

코드

import java.util.*;
class Point{
    int x,y;
    char dir;
    Point(int x, int y, char dir){
        this.x = x;
        this.y = y;
        this.dir = dir;
    }
    @Override
    public boolean equals(Object obj) {
	    return this.x == ((Point)obj).x && this.y == ((Point)obj).y && this.dir == ((Point)obj).dir;
    }
}
class Solution {    
    public int solution(String dirs) {
        int answer = 0;
        int x = 0, y = 0;
        List<Point> list = new ArrayList();
        Point p;
        for(int i = 0; i < dirs.length(); i++){
            if(dirs.charAt(i) == 'U'){
                if(y < 5) {
                    p = new Point(x,y+1,'U');
                    if(!list.contains(p)) {
                        list.add(p);
                        list.add(new Point(x,y,'D'));
                    }
                    y++;
                }
            }
            else if(dirs.charAt(i) == 'D'){
                if(y > -5) {
                    p = new Point(x,y-1,'D');
                    if(!list.contains(p)) {
                        list.add(p);
                        list.add(new Point(x,y,'U'));
                    }
                    y--;
                }                
            }
            else if(dirs.charAt(i) == 'R'){
                if(x < 5) {
                    p = new Point(x+1,y,'R');
                    if(!list.contains(p)) {
                        list.add(p);
                        list.add(new Point(x,y,'L'));
                    }
                    x++;
                }                
            }
            else {
                if(x > -5) {
                    p = new Point(x-1,y,'L');
                    if(!list.contains(p)) {
                        list.add(p);
                        list.add(new Point(x,y,'R'));
                    }
                x--;                    
                }
            }
        }
        answer = list.size() / 2;
        return answer;
    }
}

풀이가 너무 지저분하다..... ㅜㅠ