-
[알고리즘] 방문 길이■ 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