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

문제

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

코딩테스트 연습 - 방문 길이

 

접근법

고려했던 것은 두 가지다.

1. 방문한 경로를 어떤 방식으로 체크할 것인가?

2. 지나친 경로의 중복 체크를 어떻게 할 것인가?

1번은 List를 사용했다.

출발하는 x,y 좌표 + 도착하는 x,y 좌표를 String 값으로 해서 List에 저장하고 경로를 체크했다.

2번은 경우에는 list의 contains 함수를 사용하였다.

만약 (0,0) -> (1,0) 의 경로에서 다시 (1,0) -> (0,0)로 갈 경우

두 번 이동했지만 처음 이동한 경로는 하나가 된다.

결국 내가 사용한 방법은

출발하는 x,y 좌표 + 도착하는 x,y 좌표의 String 값과 도착하는 x,y 좌표 + 출발하는 x,y 좌표의 String 값을 둘다 확인하는 것이다.

이렇게 하면 중복된 경로없이 list에 저장할 수 있게 된다.

 

코드

import java.util.ArrayList;
import java.util.List;

class Solution {
    private int x=0, y=0;
    private List<String> list = new ArrayList<>();
    public int solution(String dirs) {

        String dirArr[] = dirs.split("");
        for(String dir : dirArr){
            move(dir);
        }

        return list.size();
    }

    private void move(String dir) {
        String str = x + String.valueOf(y);

        if(dir.equals("U")){
            if(y==5)
                return;
            y ++;
        }else if(dir.equals("D")){
            if(y==-5)
                return;
            y --;
        }else if(dir.equals("L")){
            if(x==-5)
                return;
            x --;
        }else if(dir.equals("R")){
            if(x==5)
                return;
            x ++;
        }
        if(list.contains(str + x + y) ||
            list.contains(String.valueOf(x) + y + str)){
            return;
        }
        list.add(str + x + y);
    }
}