(JAVA) 백준 14891번 : 톱니바퀴

 

 

https://www.acmicpc.net/problem/14891

14891번: 톱니바퀴

 

정말 오랜만에 백준을 풀었다.

 

회사에서 프로젝트에 지원가면서 개발하며 적응하느라

 

집에서 문제 풀 수 없었다고 한다...!!

 

하지만 이제 적응도 했고

 

개발도 어느정도 맞춰갈 수 있어서

 

슬슬 백준에 시동건다!

 

 

 

이 문제는 시뮬레이션 문제로

 

규칙을 찾아 알고리즘을 짠 후 

그거대로 코딩하면 된다.

 

 

내 알고리즘의 핵심은

 

1) 톱니바퀴 톱니를 나타내기 위해 LinkedList 배열 및 LinkedList<Character> 사용

2) 처음 움직인 톱니 위치부터 좌우로 뻗어나가며 반대 방향으로 이동할 수 있는 바퀴 탐색

 

이다.

 

 

 

 

매커니즘

---

하단의 소스코드에서 각 알고리즘 별로 주석을 달아놓았다.

 

따라서, 소스볼 때 이해하기 편할 수 있을 것이다.. :)))

 

 

 

 

큰 알고리즘은

 

 

 

1)  톱니바퀴의 톱니 입력 값을 톱니바퀴 순서대로 LinkedList[4] 의 인덱스에 맞게 LinkedList<Character>에 넣어준다.

 

 

2)  해당하는 값이 들어갈 수 있게 배열을 생성한다.

 

|  1  |  2  |  3  |  4        <= 톱니바퀴 번호(index)

|  0  |  0  |  -1 |  0        <= 회전 방향 (1: 시계 방향, 0: 정지, -1: 반시계. int 배열)

|  F  |  F  |  T  |  F         <= 톱니바퀴 회전 체크 여부(boolean 배열)

 

 

3)  처음 회전한 톱니바퀴의 인덱스 Queue에 넣기. 해당 톱니바퀴의 방향과 체크 여부 설정.

 

 

4)  Queue에서 꺼낸 톱니바퀴 위치에서 인덱스 -1(왼쪽), 인덱스 + 1(오른쪽) 톱니바퀴 비교

 

 ** 인덱스 + 1 이면 해당 인덱스 톱니바퀴의 2번 톱니와 인덱스 +1의 6번 톱니 비교

 ** 인덱스 - 1 이면 해당 인덱스 톱니바퀴의 6번 톱니와 인덱스 -1의 2번 톱니 비교

 ** 값이 다르면 인덱스 톱니바퀴의 반대 방향 배열에 넣기. Queue에 넣기.

 

 

5)  Queue가 Empty 전까지 4) 반복

 

 

6)  회전 횟수 K번 3) ~ 5) 반복 진행

 

 

7)  점수 계산. 계산 시 Math.pow(2, index) 를 더하며 진행(점수 규칙이 2의 index제곱이므로)

 

 

 

 

 

감사합니다.

 

 

 

소스코드

---