https://www.acmicpc.net/problem/14891
Solution 1
ref blog It was an implementation problem where I needed to figure out how to implement rotation and state checking with recursion.
- Input rotation query
- Rotate the gear specified in the rotation query
- Split into left and right to calculate whether each gear should rotate
- Rotate based on the left/right rotation values
Step 3 can be solved with recursion. You could compute the indices directly, but since n is small, recursion produces simpler code.
For step 4, I tried implementing rotation through simple index element deletion, but it didn’t work well. Since n isn’t large, I moved each element one by one to implement rotation.
I got stuck on index issues in step 3 and couldn’t solve it within the time limit. I ended up looking at the answer later.
Solution 2
The process is the same as Solution 1.
- Input rotation query
- Rotate the gear specified in the rotation query
- Split into left and right to calculate whether each gear should rotate
- Rotate based on the left/right rotation values
The difference is that steps 2 and 4 use deque instead of list, and step 3 uses index calculation instead of recursion.
Step 3 can be implemented either way, but for steps 2 and 4 deque seems better. Since it uses C’s linked list implementation, deque.rotate is concise and should be faster. Use deque.