공던지기

프로그래머스
정답률: 81%
영역:수학
나의 예상 정답률:63.8%
상승률:1.5%

문제 설명

머쓱이는 친구들과 동그랗게 서서 공 던지기 게임을 하고 있습니다. 공은 1번부터 던지며 오른쪽으로 한 명을 건너뛰고 그다음 사람에게만 던질 수 있습니다. 친구들의 번호가 들어있는 정수 배열 numbers와 정수 K가 주어질 때, k번째로 공을 던지는 사람의 번호는 무엇인지 return 하도록 solution 함수를 완성해보세요.

제한사항

2 < numbers의 길이 < 100
0 < k < 1,000
numbers의 첫 번째와 마지막 번호는 실제로 바로 옆에 있습니다.
numbers는 1부터 시작하며 번호는 순서대로 올라갑니다.

# input setting
problem_num = '공던지기'

import os, sys
path = os.getcwd() + f'\\txt\\{problem_num}'  + '.txt'
sys.stdin = open(path,'r')
num = list(map(int,sys.stdin.readline().strip().split(',')))
k = int(sys.stdin.readline())

from collections import deque
def solution(numbers, k):
    dq = deque(numbers)
    for i in range(k-1):
        dq.rotate(-2)
    return dq[0]
solution(num,k)

3

약간 원 관련 문제는 보통 queue와 관련이 있을 확률이 크고, queue는 선입선출의 개념으로 들어간것을 똥꾸멍에 다시 넣는 식으로 활용된다. 먼저 들어온 놈은 먼저 나가면서 동시에 뒤로 들어가는 것. rotate n=-2를 사용하면 편할 것으로 보인다.

short coding

def solution(numbers, k):
    return numbers[2 * (k - 1) % len(numbers)]

나는 O(k)의 시간복잡도를 가진 반면, 이 아주 단촐해보이는 함수는 O(1)의 시간복잡도를 가진다. 쫀다쫀다. 가독성은 내 코드가 좋지만 위의 코드 자체를 이해해보는 것도 중요할 것으로 보인다.

위에서는 k-1 * 2 % len(numbers) 라는 index를 찾는 방식으로 문제를 해결하는데, 2는 2칸씩 움직이는 것이고 원형에서 회전하면서 움직이는 것이기 떄문에 마지막에 길이로 나눠서 나머지를 취하는 것이다. 이는 원형 회전의 특성을 간결한 인덱스 연산으로 표현하여 문제를 해결한 것으로 좋은 풀이라고 보여진다. 특히나 계산 효율성이 대다나다.

for index,i in enumerate(range(5)):
    print(index,i)

0 0
1 1
2 2
3 3
4 4