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

링크

https://school.programmers.co.kr/learn/courses/30/lessons/49994

프로그래머스

 

문제 요약

명령어 리스트 dirs가 주어졌을 때, 캐릭터가 지나간 길 중 캐릭터가 처음 걸어본 길의 길이를 구하기

 

이동 명령어 4가지 U, D, R, L(위, 아래, 오, 왼)가 있다.

즉, 이전에 왔던 길은 카운트하지 않아도 된다.

 

제한

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

 

풀이

dirs 길이가 500 이하이고, 좌표평면의 크기는 10*10으로 고정입니다.

따라서 시간 복잡도를 크게 신경 쓰지 않고 흐름대로 구현하면 됩니다.

 

1. dirs 속 명령어를 하나씩 순회하면서 왔던 길을 체크한다.
2. 만약, 이전에 왔던 길이면 체크하지 않는다.
3. 마지막으로 카운트한 값을 반환한다.

왔던 길을 체크하기 위해서는 어떤 형태의 배열이 필요할까요?

현재 좌표에서 이동할 수 있는 선택지는 위쪽, 아래쪽, 오른쪽, 왼쪽 4가지입니다.

즉, 왔던 길인지 식별하기 위해 필요한 값은 <이전 x좌표, 이전 y좌표, 방향>입니다.

따라서 크기가 11*11*4인 3차원 배열로 visit 여부를 표시할 수 있습니다.

 

구현할 때 주의할 점이 몇 가지 있습니다. 이를 고려하여 조건문을 잘 설정해야 합니다.

1. 인덱스에는 음수가 불가능합니다.
   1. 따라서 주어진 좌표평면과 다르게 왼쪽 맨 위를 0,0이라고 생각하고 표시해야 합니다.
2. 어떤 문제든 좌표평면, 위치 이동 관련일 때 항상 경곗값을 벗어나지 않았는지 확인해야 합니다.
3. 양방향입니다.
   1. 똑같은 길을 위로 이동했다면 다시 아래로도 이동 못합니다. 따라서 이를 둘 다 표시해줘야 합니다.
   2. 저는 둘 다 표시하기 귀찮아서 그냥 하나로 통일했습니다. 위-아래는 무조건 위에 있는 좌표 기준으로, 왼-오는 무조건 오른쪽에 있는 좌표 기준으로 표시하게 했습니다.

 

코드

import java.util.*;
class Solution {
    public int solution(String dirs) {
        boolean[][][] visited = new boolean[11][11][2];
        int curX=5, curY=5, cnt=0;
        for(int i=0; i<dirs.length(); i++){
            if(dirs.charAt(i)=='U' && curX-1>=0){
                if(!visited[curX][curY][0]){
                    visited[curX][curY][0]=true;
                    cnt++;
                }
                curX--;
            } else if(dirs.charAt(i)=='D' && curX+1<=10){
                if(!visited[curX+1][curY][0]){
                    visited[curX+1][curY][0] = true;
                    cnt++;
                }
                 curX++;
            } else if(dirs.charAt(i)=='R' && curY+1<=10){
                if(!visited[curX][curY+1][1]){
                    visited[curX][curY+1][1] = true;
                    cnt++;
                }
                curY++;
            } else if(dirs.charAt(i)=='L' && curY-1>=0){
                if(!visited[curX][curY][1]){
                    visited[curX][curY][1]=true;
                    cnt++;
                }
                curY--;
            }
        }
        return cnt;
    }
}

🏷 시간 복잡도

• N: dirs 길이
• for문: O(N)
• 전체 시간 복잡도: O(N)

🏷 설명

• `visited`의 첫 인덱스는 X 좌표, 두 번째 인덱스는 Y좌표를 의미합니다.
• 세 번째 인덱스는 두 가지 값으로 0이면 위-아래 표시, 1이면 왼-오 표시입니다.
• 이미 방문한 길은 카운트를 하지는 않지만 좌표 이동을 해줘야 합니다.
  • 처음에 방문한 길이면 무조건 패스하게 구현했다가 실패했습니다 😅