[CodingTest] Codility - 01 — 슬 개발일지

# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")

def solution(A, K):

    # 첫번째로 할 거 . 개수 0 일때, K 의 나머지값이 0일때
    if (len_a:=len(A)) ==0 or (K:=(K%len_a)) == 0:
        return A
    # Implement your solution here
    else:
        return A[-K:] + A[:-K]

An array A consisting of N integers is given. Rotation of the array means that each element is shifted right by one index, and the last element of the array is moved to the first place. For example, the rotation of array A = [3, 8, 9, 7, 6] is [6, 3, 8, 9, 7] (elements are shifted right by one index and 6 is moved to the first place).

The goal is to rotate array A K times; that is, each element of A will be shifted to the right K times.

Write a function:

def solution(A, K)

that, given an array A consisting of N integers and an integer K, returns the array A rotated K times.

For example, given

A = [3, 8, 9, 7, 6] K = 3

the function should return [9, 7, 6, 3, 8]. Three rotations were made:

[3, 8, 9, 7, 6] -> [6, 3, 8, 9, 7] [6, 3, 8, 9, 7] -> [7, 6, 3, 8, 9] [7, 6, 3, 8, 9] -> [9, 7, 6, 3, 8]

For another example, given

A = [0, 0, 0] K = 1

the function should return [0, 0, 0]

Given

A = [1, 2, 3, 4] K = 4

the function should return [1, 2, 3, 4]

Assume that:

N and K are integers within the range [0..100];

each element of array A is an integer within the range [−1,000..1,000].

In your solution, focus on correctness. The performance of your solution will not be the focus of the assessment.

문제를 보고 Python Slicing 기능이 생각났지만,, 우선은 pop insert로 구현을 해봤다.

(성능은 보지 않는다고? 적혀있어서)

# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")

def solution(A, K):
    len_A = len(A)
    ##예외처리
    if len_A == K or len_A == 0:
        return A
    else:
        for i in range(K):
            A.insert(0,A.pop())
    return A

## python 의 slicing써서 풀기

해당 코드의 시간복잡도를 우선 구해보자.

A.pop()

리스트 맨 뒤에서 pop
O(1)

A.insert(0, x)

리스트 맨 앞에 삽입
기존 원소 전부 한 칸씩 밀려야 함
O(N)

for 루프

for i in range(K): A.insert(0, A.pop())

이 작업을 K번 반복

전체 시간복잡도

한 번 회전 비용: O(N)
K번 회전 → O(K × N)

너무 구리다...

slicing 으로 풀어보자.

# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")

def solution(A, K):

    # 첫번째로 할 거 . 개수 0 일때, K 의 나머지값이 0일때
    if (len_a:=len(A)) ==0 or (K:=(K%len_a)) == 0:
        return A
    # Implement your solution here
    else:
        return A[-K:] + A[:-K]

슬라이싱: O(N)
리스트 덧셈: O(N)

A.pop()

A.insert(0, x)

for 루프

전체 시간복잡도

티스토리툴바