[Python 코테 입문] 2. (문제 4번) 수열의 회전

🖥️ 입문자를 위한 코딩테스트 핵심 - Python (김태원, 인프런)

 

섹션2. 배열, 연결리스트, deque

 

(문제 4번) 수열의 회전

정수 수열의 원소를 회전하고 싶습니다.

매개변수 nums에 길이가 n인 수열이 주어지고, 매개변수 k에 뒤로 이동시키고 싶은 원소의 개수가 주어지면 nums의 원소 중 앞 원소 k개를 수열의 뒤쪽으로 이동하고 난 후의 수열을 반환하는 프로그램을 작성하세요.

 

입출력 예

nums	k	answer
[3, 7, 1, 5, 9, 2, 8]	3	[5, 9, 2, 8, 3, 7, 1]
[2, 12, 2, 1, 3, 3, 9]	2	[2, 1, 3, 3, 9, 2, 12]
[1, 2, 5, 4, 6, 7, 9]	6	[9, 1, 2, 5, 4, 6, 7]
[1, 3, 6, 8, 14, 2, 1, 7]	5	[2, 1, 7, 1, 3, 6, 8, 14]

 

제한사항

• nums의 길이 : 3 <= n <= 200,000
• 배열 nums의 원소는 정수입니다. -10,000 <= nums[i] <= 10,000
• 0 <= k <= nums의 길이

 

풀이

def rotateSequence(nums, k):
  answer = nums[k:] + nums[0:k]
  return answer;

print(rotateSequence([3, 7, 1, 5, 9, 2, 8], 3));
print(rotateSequence([2, 12, 2, 1, 3, 3, 9], 2));
print(rotateSequence([1, 2, 5, 4, 6, 7, 9], 6));
print(rotateSequence([1, 3, 6, 8, 14, 2, 1, 7], 5));

[5, 9, 2, 8, 3, 7, 1]

[2, 1, 3, 3, 9, 2, 12]

[9, 1, 2, 5, 4, 6, 7]

[2, 1, 7, 1, 3, 6, 8, 14]

 

정답 풀이

분석

1. 첫 번째 제한사항에서 최대 입력크기가 20만이므로 시간복잡도를 생각하며 문제를 풀어야 한다.

2. 배열(Python에서는 list)의 맨 앞에서부터 원소를 pop()해서 배열의 맨 뒤에 원소를 append()하면 될 것 같다.

: 배열의 값을 삽입하거나 삭제할 때 시간복잡도는 O(n)이다.

3. 배열을 연결리스트(Python에서는 deque)로 바꿔서 맨 앞에서부터 원소를 popleft()해서 맨 오른쪽으로 append()해보자.

: deque의 값을 삽입하거나 삭제할 때 시간복잡도는 O(1)이다.

따라서 deque로 바꿔 풀고 다시 list로 바꿔서 반환하면 된다.

 

풀이

from collections import deque
def solution(nums, k):
    answer = deque(nums)
    for i in range(k):
      answer.append(answer.popleft())
    return list(answer);


print(solution([3, 7, 1, 5, 9, 2, 8], 3));
print(solution([2, 12, 2, 1, 3, 3, 9], 2));
print(solution([1, 2, 5, 4, 6, 7, 9], 6));
print(solution([1, 3, 6, 8, 14, 2, 1, 7], 5));

[5, 9, 2, 8, 3, 7, 1]

[2, 1, 3, 3, 9, 2, 12]

[9, 1, 2, 5, 4, 6, 7]

[2, 1, 7, 1, 3, 6, 8, 14]