ABOUT ME

GoGo!

Today
Yesterday
Total
  • [알고리즘] 방문 길이
    ■ Algorithm 2019. 6. 24. 14:33

    출처: https://programmers.co.kr/learn/courses/30/lessons/49994?language=java

     

    알고리즘 연습 - 방문 길이 | 프로그래머스

     

    programmers.co.kr

    풀이

     

    일단 U/D/R/L 방향에 따른 좌표 이동을 정리했다. 

    그리고 알고리즘을 정리해보면 아래와 같다.

     

    - 현재 좌표(0,0) 에서 시작.

    - 방향들이 적혀있는 String을 한글자씩 쪼개서 array에 저장

     

    - array 순회

    {

    1. 방향에 따른 좌표 이동

     

    2. 이동한 좌표가 좌표 평면 밖을 넘어가면 -> 1번으로

    넘어가지 않는 경우 -> 3번으로

     

    3. 현재 좌표에서 이동한 좌표로 이동한 길이 이미 지나간 길인지 확인

    이미 지나간 길인 경우 -> 4번으로

    처음 지나가는 길인 경우 -> 지나간 경로 list에 ((현재좌표),(이동한좌표)) 추가.

     

    4. 현재 좌표를 이동한 좌표로 업데이트. 1번부터 다시 시작.

    }

     

    - 지나간 경로 list의 길이 리턴.

     

     

    원래는 좌표 값을 저장할 때 hashmap에 x, y를 key로 하는 변수를 만들어서 저장할까 생각했는데

    단지 숫자 값만 저장하는데 불필요하게 hashmap을 사용하는 것 같아서 string으로 한번에 저장했다.

    이게 나중에 이미 지나간 길인지 비교할 때 equals 함수를 쓰면 시간절약이 될 것 같았기 때문이다.

     

    코드

    결과 값

    ****************************
    이동할 방향: U
    현재 좌표: 0,0
    이동한 좌표: 0,1
    ----------------------------
    지나간 거리 list : [0,0,0,1]
    ****************************
    ****************************
    이동할 방향: L
    현재 좌표: 0,1
    이동한 좌표: -1,1
    ----------------------------
    지나간 거리 list : [0,0,0,1, 0,1,-1,1]
    ****************************
    ****************************
    이동할 방향: U
    현재 좌표: -1,1
    이동한 좌표: -1,2
    ----------------------------
    지나간 거리 list : [0,0,0,1, 0,1,-1,1, -1,1,-1,2]
    ****************************
    ****************************
    이동할 방향: R
    현재 좌표: -1,2
    이동한 좌표: 0,2
    ----------------------------
    지나간 거리 list : [0,0,0,1, 0,1,-1,1, -1,1,-1,2, -1,2,0,2]
    ****************************
    ****************************
    이동할 방향: R
    현재 좌표: 0,2
    이동한 좌표: 1,2
    ----------------------------
    지나간 거리 list : [0,0,0,1, 0,1,-1,1, -1,1,-1,2, -1,2,0,2, 0,2,1,2]
    ****************************
    ****************************
    이동할 방향: D
    현재 좌표: 1,2
    이동한 좌표: 1,1
    ----------------------------
    지나간 거리 list : [0,0,0,1, 0,1,-1,1, -1,1,-1,2, -1,2,0,2, 0,2,1,2, 1,2,1,1]
    ****************************
    ****************************
    이동할 방향: L
    현재 좌표: 1,1
    이동한 좌표: 0,1
    ----------------------------
    지나간 거리 list : [0,0,0,1, 0,1,-1,1, -1,1,-1,2, -1,2,0,2, 0,2,1,2, 1,2,1,1, 1,1,0,1]
    ****************************
    ****************************
    이동할 방향: L
    현재 좌표: 0,1
    이동한 좌표: -1,1
    ----------------------------
    지나간 거리 list : [0,0,0,1, 0,1,-1,1, -1,1,-1,2, -1,2,0,2, 0,2,1,2, 1,2,1,1, 1,1,0,1]
    ****************************
    ****************************
    이동할 방향: U
    현재 좌표: -1,1
    이동한 좌표: -1,2
    ----------------------------
    지나간 거리 list : [0,0,0,1, 0,1,-1,1, -1,1,-1,2, -1,2,0,2, 0,2,1,2, 1,2,1,1, 1,1,0,1]
    ****************************
    7

     


    ****************************
    이동할 방향: L
    현재 좌표: 0,0
    이동한 좌표: -1,0
    ----------------------------
    지나간 거리 list : [0,0,-1,0]
    ****************************
    ****************************
    이동할 방향: U
    현재 좌표: -1,0
    이동한 좌표: -1,1
    ----------------------------
    지나간 거리 list : [0,0,-1,0, -1,0,-1,1]
    ****************************
    ****************************
    이동할 방향: L
    현재 좌표: -1,1
    이동한 좌표: -2,1
    ----------------------------
    지나간 거리 list : [0,0,-1,0, -1,0,-1,1, -1,1,-2,1]
    ****************************
    ****************************
    이동할 방향: L
    현재 좌표: -2,1
    이동한 좌표: -3,1
    ----------------------------
    지나간 거리 list : [0,0,-1,0, -1,0,-1,1, -1,1,-2,1, -2,1,-3,1]
    ****************************
    ****************************
    이동할 방향: L
    현재 좌표: -3,1
    이동한 좌표: -4,1
    ----------------------------
    지나간 거리 list : [0,0,-1,0, -1,0,-1,1, -1,1,-2,1, -2,1,-3,1, -3,1,-4,1]
    ****************************
    ****************************
    이동할 방향: L
    현재 좌표: -4,1
    이동한 좌표: -5,1
    ----------------------------
    지나간 거리 list : [0,0,-1,0, -1,0,-1,1, -1,1,-2,1, -2,1,-3,1, -3,1,-4,1, -4,1,-5,1]
    ****************************
    ****************************
    이동할 방향: L
    현재 좌표: -5,1
    이동한 좌표: -6,1
    ****************************
    이동할 방향: L
    현재 좌표: -5,1
    이동한 좌표: -6,1
    ****************************
    이동할 방향: U
    현재 좌표: -5,1
    이동한 좌표: -5,2
    ----------------------------
    지나간 거리 list : [0,0,-1,0, -1,0,-1,1, -1,1,-2,1, -2,1,-3,1, -3,1,-4,1, -4,1,-5,1, -5,1,-5,2]
    ****************************
    7

    '■ Algorithm' 카테고리의 다른 글

    [알고리즘] #Merge Two Binary Trees  (0) 2019.07.06
    [알고리즘] #최고의 집합  (0) 2019.06.26
    [알고리즘] #체육복  (0) 2019.05.28
    [알고리즘] #Symmetric Tree  (0) 2019.05.28
    [알고리즘] #위장  (0) 2019.05.26
Designed by Tistory.