프로그래밍 면접 문제 9 : Convert Array

프로그래밍 면접 문제 9 : Convert Array

 

이 글은 블로그 http://www.ardendertat.com/프로그래밍 면접에 대한 글을 번역한 글입니다.

이전글 – 프로그래밍 면접 문제 8 : Transform Word (문자 변환)

 

다음과 같이 주어진 배열을 :

latex

일정한 추가 공간을 사용해서 적절한 위치로, 아래와 같은 배열로 변환시킵니다 :

latex

새로운 배열을 생성해서 문제를 해결하면 쉽게 해결할 수 있지만, 그렇지 못하기 때문에 이 문제는 까다로운 문제입니다. i번째 위치에 있는 요소는 원래 배열에서 (i % 3) * N + i / 3위치에 있습니다. 따라서 코드는 단순합니다:

def getIndex(currentIndex, N):
    return (currentIndex % 3) * N + (currentIndex / 3)
 
def convertArray_extraSpace(arr):
    N = len(arr) / 3
    return [arr[getIndex(i, N)] for i in range(len(arr))]

getIndex 함수는 최종 배열의 인덱스를 입력받고, 그 위치에 표시되어야하는 원래 배열 내 요소의 인덱스를 반환합니다. 하지만, 추가 공간을 사용할 수 없기 때문에 그 대신 배열을 내부에서 수정해야합니다. 비슷한 접근 방법을 사용할 수도 있지만, 루프를 반복 수행할 때마다 getIndex 함수와 배열 요소의 교환을 통해서 i 번째 배열 요소를 최종 위치에 배치할 수 있습니다. 알고리즘은 다음과 같이 동작합니다. 루프의 각 반복 수행 과정(currentIndex)에서 getIndex 함수 호출을 통해서 해당 위치(swapIndex)에 표시되어야하는 항목의 인덱스를 얻습니다. swapIndex의 요소는 currentIndex에 나타나는 최종 요소입니다. 따라서 swapIndx >= currentIndex인 경우, currentIndex와 swapIndex 위치의 항목을 서로 바꿉니다. 하지만 swapIndex < currentIndex 인 경우에는 swapIndex 위치에 있는 요소가 이전 반복 수행 과정에서 다른 요소로 바뀌었다는 것을 의미합니다. 이제 그 배열 요소는 다른 위치에 있고 해당 요소를 찾아야 합니다. 다시 swapIndex를 전달해서 getIndex 함수를 호출한 다음 swapIndex 위치에 있던 요소와 교환된 요소를 찾습니다. 새로 얻은 swapIndex가 swapIndex >= currentIndex 인 경우, 이전 과정과 같이 요소를 서로 바꿉니다. 그렇지 않은 경우, swapIndex >= currentIndex 가 될때까지 이 과정을 반복해서 currentIndex에 표시될 최종 요소를 찾습니다. 다음의 코드는 이 과정을 명확하게 보여줍니다:

def convertArray(arr):
    N = len(arr) / 3
    for currentIndex in range(len(arr)):
        swapIndex = getIndex(currentIndex, N)
        while swapIndex < currentIndex:
            swapIndex = getIndex(swapIndex, N)
        arr[currentIndex], arr[swapIndex] = arr[swapIndex], arr[currentIndex]

이 알고리즘은 상당히 간단하고 추가 공간을 사용하지 않고 배열 내부에서 적절히 문제를 해결합니다. 좀 더 명확히하기 위해서 예제를 실행시켜보겠습니다.  다음은 크기가 15인 배열의 프로그램 흐름을 나타냅니다. 위에서 설명했듯이, 일부 배열 요소에서 swapIndex는 swapIndex >= currentIndex 가 될 때까지 여러 번 계산됩니다.

currentIdx=0, swapIdx=0, swapIdx >= currentIdx, swap arr[0] arr[0]
currentIdx=1, swapIdx=5, swapIdx >= currentIdx, swap arr[1] arr[5]
currentIdx=2, swapIdx=10, swapIdx >= currentIdx, swap arr[2] arr[10]
currentIdx=3, swapIdx=1, swapIdx < currentIdx, no swap swapIdx=1, newSwapIdx=5, newSwapIdx >= currentIdx, swap arr[3] arr[5]
currentIdx=4, swapIdx=6, swapIdx >= currentIdx, swap arr[4] arr[6]
currentIdx=5, swapIdx=11, swapIdx >= currentIdx, swap arr[5] arr[11]
currentIdx=6, swapIdx=2, swapIdx < currentIdx, no swap swapIdx=2, newSwapIdx=10, newSwapIdx >= currentIdx, swap arr[6] arr[10]
currentIdx=7, swapIdx=7, swapIdx >= currentIdx, swap arr[7] arr[7]
currentIdx=8, swapIdx=12, swapIdx >= currentIdx, swap arr[8] arr[12]
currentIdx=9, swapIdx=3, swapIdx < currentIdx, no swap
  swapIdx=3, newSwapIdx=1, newSwapIdx < currentIdx, no swap
  swapIdx=1, newSwapIdx=5, newSwapIdx < currentIdx, no swap swapIdx=5, newSwapIdx=11, newSwapIdx >= currentIdx, swap arr[9] arr[11]
currentIdx=10, swapIdx=8, swapIdx < currentIdx, no swap swapIdx=8, newSwapIdx=12, newSwapIdx >= currentIdx, swap arr[10] arr[12]
currentIdx=11, swapIdx=13, swapIdx >= currentIdx, swap arr[11] arr[13]
currentIdx=12, swapIdx=4, swapIdx < currentIdx, no swap
  swapIdx=4, newSwapIdx=6, newSwapIdx < currentIdx, no swap
  swapIdx=6, newSwapIdx=2, newSwapIdx < currentIdx, no swap
  swapIdx=2, newSwapIdx=10, newSwapIdx < currentIdx, no swap
  swapIdx=10, newSwapIdx=8, newSwapIdx < currentIdx, no swap swapIdx=8, newSwapIdx=12, newSwapIdx >= currentIdx, swap arr[12] arr[12]
currentIdx=13, swapIdx=9, swapIdx < currentIdx, no swap
  swapIdx=9, newSwapIdx=3, newSwapIdx < currentIdx, no swap
  swapIdx=3, newSwapIdx=1, newSwapIdx < currentIdx, no swap
  swapIdx=1, newSwapIdx=5, newSwapIdx < currentIdx, no swap
  swapIdx=5, newSwapIdx=11, newSwapIdx < currentIdx, no swap swapIdx=13, newSwapIdx=13, newSwapIdx >= currentIdx, swap arr[13] arr[13]
currentIdx=14, swapIdx=14, currentIdx >= swapIdx, swap arr[14] arr[14]

이 알고리즘의 공간 복잡도는 getIndex 함수의 호출 횟수에 따라 결정됩니다. 몇몇 요소에서 getIndex 함수가 여러번 호출되기 때문에 선형(linear) 복잡도가 아니고, 모든 배열 요소에서 getIndex 함수가 반복적으로 호출되지 않기 때문에 2차 함수의 복잡도도 아닙니다. 우리는 위의 2가지 모두를 확인할 수 있습니다. 따라서 이 알고리즘의 복잡도는 선형 복잡도와 2차 함수 복잡도의 중간 복잡도를 갖게 됩니다. 이를 종종 super-linear라고 부릅니다. 정확히 말하면 복잡도는 아래 그림에서 볼 수 있듯이 대략 O(N^1.3)입니다.

plot_convertArray

다음은 getIndex 함수에 대한 호출 수도 같이 계산하고 이를 반환하도록 converArray 함수를 변경했다고 가정해서 plot을 생성하는 코드입니다:

def complexityAnalysis():
    x=range(3, 1000, 3)
    y=[convertArray(range(num)) for num in x]
    pylab.plot(x, sorted(y), label='convertArray')
    pylab.plot(x, map(lambda num: num**1.2, x), label='x^1.2')
    pylab.plot(x, map(lambda num: num**1.3, x), label='x^1.3')
    pylab.legend(loc='upper left')
    pylab.title('Complexity of convertArray')
    pylab.xlabel('array length')
    pylab.ylabel('number of getIndex calls')
    pylab.show()

 

다음글 – 프로그래밍 면접 문제 10 : Kth Largest Element in Array

 

RonnieJ

프리랜서 IT강사로 활동하고 있습니다. 게임 개발, 웹 개발, 1인 기업, 독서, 책쓰기에 관심이 많습니다.

답글 남기기

이메일 주소는 공개되지 않습니다. 필수 항목은 *(으)로 표시합니다