[프로그래머스 level_3] 방문 길이 for JAVA

https://programmers.co.kr/learn/challenges?selected_part_id=6174

프로그래머스

[문제 설명]

 

게임 캐릭터를 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 이하의 자연수입니다.

입출력 예

dirs	answer
ULURRDLLU	7
LULLLLLLU	7

 

[풀이]

위에서 설명한 것 같이 아래와 같은 제약조건이 있다.

• 명령어에 대한 좌표의 값을 업데이트시켜야 한다.
• 좌표의 범위가 넘어가면 그 명령어는 무시한다.
• 한번 들린 길은 카운트하지 않는다.

문제풀이에 여러 가지 방법이 있겠지만, 나는 ArrayList를 사용해서 간선들을 추가했다.

예를 들어 0,0 좌표에서 0,1로 이동한다면 0,0,0,1(0,0 -> 0,1)이라는 배열을 ArrayList에 추가했다.

하지만 한번 간 길은 들리면 안 된다 했으니 1,0,0,0도 같이 추가해준다. 그리고 매번 출발지점과 도착지점의 간선들이 ArrayList에 있는지 없는지 확인하고 없다면 추가해주기로 한다.

마지막으로 양방향으로 간선을 구했으니 우리가 필요한 단방향으로 /2를 해주면 연결된 간선 수가 구해진다.

 

[코드]

import java.util.ArrayList;
import java.util.Arrays;
 
public class LengthOfVisit {
    ArrayList<int[]> al;                                //간선들
    public boolean check(int x, int y) {
        if(y < 0 || 10 < y || x < 0 || 10 < x) {        //범위를 벗어나면 false
            return false;
        }
        return true;
    }
    
    public void addEdge(int x, int y, int px, int py) {
        int[] a = new int[] {y, x, py, px};            //현재 노드의 py,px 연결하는 노드의 y, x
        int[] b = new int[] {py, px, y, x};            //
        for(int i = 0; i < al.size(); i++) {        //al에 연결되는 노드가 있으면
            if(Arrays.equals(al.get(i),a)) {        //a하나만 비교해도 연결되어 있는지 알 수 있다. 왜냐면 연결되있으면 a b 둘다 연결되있으므로
                return;
            }
        }
        al.add(a);                                    //양방향 추가.
        al.add(b);
    }
    
    public int solution(String dirs) {
        al = new ArrayList<int[]>();
        int x = 5;        //가운데 x좌표
        int y = 5;        //가운데 y좌표
        
        for(int i = 0 ; i < dirs.length(); i++) {
            char ins = dirs.charAt(i);     //명령어(U,D,L,R)
            if(ins == 'U') {
                if(check(x,y-1)) {        //check : 현재 좌표가 좌표계의 범위를 벗어나는지 안나는지
                    addEdge(x,y-1,x,y); //addEdge : 노드에서 노드까지 가는 간선의 정보, 양방향으로 노드를 연결한다.
                    y -= 1;
                }
            }else if(ins =='D') {
                if(check(x,y+1)) {
                    addEdge(x,y+1,x,y);
                    y += 1;
                }
            }else if(ins =='L') {
                if(check(x-1,y)) {
                    addEdge(x-1,y,x,y);
                    x -= 1;
                }
            }else {                     
                if(check(x+1,y)) {
                    addEdge(x+1,y,x,y);
                    x += 1;
                }
            }
        }
        return al.size()/2;                                //양방향이므로 
    }
}

프로그래머스 테스트 케이스 통과

느낀 점: 처음에는 쉬운 문제인지 알고 간단한 규칙성으로만 접근했다가 잘 안 풀리길래 생각이 필요한 문제인걸 깨달았다. 그리고 이제까지 너무 뇌 컴파일을 했더니 너무 효율성이 떨어지는 것 같아 직접 손으로 적으며 이해하고 판단하려고 했다. 이렇게 한 이유는 카카오 코딩테스트를 볼 때마다 카카오 문제들의 방대한 조건들 때문에 내가 하는 방식으로 풀면 풀리지도 않을뿐더러 나중에라도 언젠간 한계에 부딪힐 것 같아서이다.