Lesson 2: Arrays

[Lesson 2: Arrays]

Tasks 1. OddOccurrencesInArray

Find value that occurs in odd number of elements.

사이트 : https://codility.com/programmers/task/odd_occurrences_in_array/

난이도 : PAINLESS

추가 자료 : Open reading material (PDF)

A non-empty zero-indexed array A consisting of N integers is given. The array contains an odd number of elements, and each element of the array can be paired with another element that has the same value, except for one element that is left unpaired. For example, in array A such that:   A[0] = 9  A[1] = 3  A[2] = 9   A[3] = 3  A[4] = 9  A[5] = 7   A[6] = 9 - the elements at indexes 0 and 2 have value 9, - the elements at indexes 1 and 3 have value 3, - the elements at indexes 4 and 6 have value 9, - the element at index 5 has value 7 and is unpaired. Write a function: def solution(A) that, given an array A consisting of N integers fulfilling the above conditions, returns the value of the unpaired element. For example, given array A such that:   A[0] = 9  A[1] = 3  A[2] = 9   A[3] = 3  A[4] = 9  A[5] = 7   A[6] = 9 the function should return 7, as explained in the example above. Assume that: N is an odd integer within the range [1..1,000,000]; each element of array A is an integer within the range [1..1,000,000,000]; all but one of the values in A occur an even number of times. Complexity: expected worst-case time complexity is O(N); expected worst-case space complexity is O(1), beyond input storage (not counting the storage required for input arguments). Elements of input arrays can be modified.

#1

def solution(A):
    # write your code in Python 2.7
    compareList = []
    
    for num in A:
        flag = False
        for compare in compareList:
            if num == compare:
                compareList.remove(compare)
                flag = True
        if not flag:
            compareList.append(num)
    
    result = compareList.pop()
    return result

배열 A 안에 있는 값을 하나씩 꺼내가면서 비교해본다.

compareList에 만약 동일한 값이 있는 경우, 그 값을 compareList에서 제거해 준다.

동일한 값이 없는 경우, 그 값을 compareList에 저장시켜 준다.

모든 수행이 끝나면 마지막으로 compareList에 저장되어 있는 값을 뽑아 result에 저장시킨다.

SCORE: 66% - 시간 초과

#2

def solution(A):
    A.sort()
    cnt = 1
    for index in range(0, len(A)-1):
        if A[index] == A[index+1]:
            cnt += 1
        else:
            if cnt%2 != 0:
                return A[index]
            cnt = 1
    return A[len(A)-1]

먼저 배열을 정렬시켜 준 뒤, 동일한 수의 갯수를 계산하여 주도록 한다.

만약, 갯수가 홀수인 경우, 바로 리턴하여 주도록 한다.

모든 검사가 끝날 때까지 홀수개가 나오지 않는다면, 마지막 값을 리턴해 주도록 한다.

SCORE: 100%

Tasks 2. CyclicRotation

Rotate an array to the right by a given number of steps.

사이트 : https://codility.com/programmers/task/cyclic_rotation/

난이도 : PAINLESS

추가 자료 : Open reading material (PDF)

A zero-indexed 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 also moved to the first place. For example, the rotation of array A = [3, 8, 9, 7, 6] is [6, 3, 8, 9, 7]. The goal is to rotate array A K times; that is, each element of A will be shifted to the right by K indexes. Write a function: def solution(A, K) that, given a zero-indexed array A consisting of N integers and an integer K, returns the array A rotated K times. For example, given array A = [3, 8, 9, 7, 6] and K = 3, the function should return [9, 7, 6, 3, 8]. 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.

def solution(A, K):
    if len(A) == 0:
        return A
 
    for n in range(K):
        A.insert(0, A.pop())
    return A

받은 A의 배열에서 맨 끝에 있는 요소를 빼내, 0번째 위치 (배열의 앞)에 삽입한다.

이를 K번 반복해 준다.

만약, 배열 A가 요소를 가지고 있지 않은 경우, 그대로 A를 리턴시켜준다.

SCORE: 100%