문제 출처
코딩테스트 연습 - 방의 개수
[6, 6, 6, 4, 4, 4, 2, 2, 2, 0, 0, 0, 1, 6, 5, 5, 3, 6, 0] 3
programmers.co.kr
문제
원점(0,0)에서 시작해서 아래처럼 숫자가 적힌 방향으로 이동하며 선을 긋습니다.
ex) 1일때는 오른쪽 위로 이동
그림을 그릴 때, 사방이 막히면 방하나로 샙니다.
이동하는 방향이 담긴 배열 arrows가 매개변수로 주어질 때, 방의 갯수를 return 하도록 solution 함수를 작성하세요.
제한사항
-
배열 arrows의 크기는 1 이상 100,000 이하 입니다.
-
arrows의 원소는 0 이상 7 이하 입니다.
-
방은 다른 방으로 둘러 싸여질 수 있습니다.
입출력 예
|
arrows |
return |
|
[6, 6, 6, 4, 4, 4, 2, 2, 2, 0, 0, 0, 1, 6, 5, 5, 3, 6, 0] |
3 |
입출력 예 설명
-
(0,0) 부터 시작해서 6(왼쪽) 으로 3번 이동합니다. 그 이후 주어진 arrows 를 따라 그립니다.
-
삼각형 (1), 큰 사각형(1), 평행사변형(1) = 3
Point
1. 위치 0,0 에서 시작해서 움직일 이동 리스트가 입력으로 주어지고 입력에 따라 이동 경로를 그렸을 때, 도형(방)이 몇개인지 구하는 문제이다.
2. 입력값
- arrows = 움직일 이동 리스트, value = 0~7
3. 사방이 막힌 그림을 도형이라고 하고 도형은 모양에 관계 없이 카운트 한다.
Solution Tip
도형이 만들어지는 경우는 2가지가 있다. 있던 점으로 도착하는 경우와 크로스로 지나가는 경우이고 중복의 이동은 카운트 하지 않는다. 입력으로 들어온 이동 리스트를 하나씩 실행하며 이 경우들을 만족하는지 확인하면 된다. 이동에 대한 기록을 할 때 Array로 하면 시간초과가 나므로 이동 지점을 키로 하는 딕셔너리를 만들어야 한다.
Solution
코드 설명
# 12 - 방문한 지점으로 도착점이 되는 경우를 찾기 위해 사용한다.
# 13 - 이동한 기록으로 교차점이 존재하는지, 중복이동인지를 찾기 위해 사용한다.
# 20 - 다음 이동을 위해 이동한 위치를 저장해 놓는다.
# 22 - 이번 이동의 정보로 시작 지점과 방향을 저장해 놓는다.
# 27 - 중복 이동인지 확인하고 중복 이동일 시 다음 이동으로 넘어간다.
# 29 - 이동이 대각선 이동일 때 크로스 되는 이동이 있는지 확인하고 있으면 카운트 한다.
# 37 - 이동한 지점이 이미 방문한 지점인지 확인하고 맞으면 카운트 한다.
# 40 ~ 이동 지점과 이동 정보를 저장하고 다음 이동을 한다.
