티스토리 뷰


미국식(?) 인터뷰를 다루는 책이 나왔다. 이전에도 MS를 다닌 인도형들이 쓴 책이 있지만, 이번엔 구글러가 쓴 책이다. 기존 대다수의 한국 IT 회사와 달리 미국에서는 개발자 인터뷰에서 문제 풀이를 물어보는 경우가 많다. 좋은 개발자를 뽑기 위해서 당연한 프로세스이지만, 국내에서는 일반적이지 않기도 하다. 그래서일까? 국내에서도 점차적으로 문제 풀이식 인터뷰가 많이 늘었다. 회사의 베이스가 레알 소프트웨어인 회사는 어지간하면 하는 것 같다. 맨땅에 헤딩, 혹은 인터넷에서 무분별한 후기에 의존하는 것에서 벗어나고자 볼만한 인터뷰집들이 나오고 있는거 같다. 아래는 'Cracking the coding interview' 역서를 발간하면서 인사이트에서 진행하는 이벤트이다. 심심풀이로 따라해 봅시다.


-----------------------------------------------------------------------------------------------------------------------------------------

배열 arr[]과 위치 s, t가 있을 때,
arr[s], arr[s+1], … , arr[t-1]을 오른쪽으로 한 칸씩 이동하고,
arr[t]는 arr[s]로 복사하는 것을 ’1만큼 오른쪽으로 회전시켰다’고 한다.

예를 들어 길이가 8인 배열에서 s=2, t=6이면 다음 그림처럼 바뀐다.

길이가 n인 배열의 위치는 0, 1, 2, … , n-1이다.

문제 :
k를 인자로 받아서 k만큼 오른쪽으로 회전시키는 함수를 작성하라.
단, 1만큼 오른쪽으로 이동시키는 과정을 k번 반복해서는 안 된다.


Solve)

문제가 생각보다 느슨하다. 배열에 대한 언급도 없고, 문제에서는 s와 t에 대한 언급이 있다가 정작 term에서는 사라졌다. 1씩 shift를 k번만 반복하지 않으면 된다.

딱히, 알고리즘이라고 할 것 없이 그냥 try하면 될듯하다. 거진 brute force!

문제에서 한정하지 않는 조건은 임의대로 지정했다.

배열 사이즈는 예제 그림에 나온대로 8, 안에는 1부터 순차증가로8까지 넣었다.

해법은 간단하다, 흔히 사용하는 mod를 이용하여 index를 이동하면서 새로운 배열에 shift 된 결과를 삽입 했다. 

res[(i+k)%t] = arr[i];

딱히 뭐 없지만 굳이 핵심이 되는 행이라면 저 행이 될 것이다.

circular linked list에서 정해진 배열 사이즈가 넘어갔을 때, index를 시작(0)으로 되돌리기 위해서 배열 사이즈로 mod 연산을 했던 것을 생각하면 쉽다.

굳이 풀이하면, k번째만큼 shift가 일어나야하니 이동 되어야할 index에 기존값을 순차대로 넣는 것이다.

Timecomplexity는 O(n)이며, Spacecomplexity 또한 O(n)이다.

요즘 시대에 남아도는게 메모리 인지라 쿨하게 입력사이즈만큼 추가로 메모리를 잡고 결과를 넣었다.  알고리즘 문제처럼 표준 입출력으로 찍어내는게 아닌 메모리 상태를 바꿔야 하는 문제였다면, res에 있는 값을 다시 원 배열에 옴기는 과정이 필요해진다. 그러나, 그냥 출력하는 거에 익숙해서(?) 샘플 코드는 그냥 출력만했다.

만약에, shift를 해야할 메모리 사이즈가 정말 크다면 swap을 이용해서 원 배열에서 shift를 하는 것을 지향해야 할 것이다.

또, 자료구조가 linked list라면 더욱 더 간단해진다. circular로 앞 뒤 list를 묶어두면, 더미 하나 두고 시작 list만 변경하면 shift 된 것과 같은 효과를 누릴 수 있다.

아래는 샘플 코드이다. tistory에서 코드블럭을 지원했던거 같은데, 보이지가 않아서 글박스라는 최후의 수단을 사용했다. 혹시라도 생각나면 google prettify라도 적용해놔야겠다...


#include <stdio.h>

int main()

{

int arr[8], res[8];

int i;

int s, t;

int temp;

for(i = 0; i < 8; i++)

{

arr[i] = i+1;

}

int k;

scanf("%d", &k);

for(i = 0; i < 8; i++)

{

printf("%d ", arr[i]);

}

printf("\n");

s=0;

t=8;

for(i = 0; i < 8 ; i++)

{

res[(i+k)%t] = arr[i];

}

for(i = 0; i < 8; i++)

{

printf("%d ", res[i]);

}

printf("\n");

return 0;

}

댓글
댓글쓰기 폼