[코딩 인터뷰] 교육플랫폼 라이브코딩 인터뷰 후기

결론부터 말하면 잘 못했고 재밌었다!

 

인성면접이나 기술면접에 해당하는 질문 하나 없이 정말 문제 한가지를 열심히 푸는 면접이었다.

문제는 비교적 간단했고 분위기는 캐주얼했고 면접관분은 친절하셨다.

//  0을 포함한 홀수를 가진 배열이 [0, 2n-1] 존재할 때 배열에서 빠진 수를 찾아 반환하라.
// 배열에는 2n-1보다 작거가 같은 모든 홀수가 들어있어야 한다.
// (n은 배열의 길이)

input = [0,1,3]
output = 5

문제를 이해하는데도 한참 걸렸다. 그래서 질문을 계속하고 예시를 계속 들어주셨음..ㅎㅎㅎ

n은 배열의 길이라 [0,1,3]이 들어오면 3이 되고 2n-1 = 5가 되면서 5보다 작거나 같은 모든 홀수와 0 중에 배열에 없는 수를 반환해야 하는 문제였다. 

 

처음엔 아주 단순하게 풀었다. 

const range = arr.length*2-1;

for(let i=0 ; i <= range; i += 2){
	if(!arr.includes(i)){
    	return i
    }
}

return 0;

시간복잡도와 공간복잡도를 물어보셨는데 공간복잡도는 사실 내가 잘 모르는 개념이었다. 여쭤봤더니 잘 설명해주셨다.

for문을 중복으로 돌기때문에 시간복잡도는 O(n^2)이고 공간복잡도는 배열과 객체를 선언하고 메모리를 차지한게 없으므로 O(1)이었다.

 

이제 시간복잡도를 줄여보자고 하셨다.

const origin = [0];
const range = arr.length*2-1

for(let i=1; i <=range ; i+=2){
	origin.push(i)
    }
    
for(let i=0; i<arr.length; i++){
	if(arr[i] !== origin[i]){
    	return i
    }
}

return 0

원본 배열을 만들고 input 배열과 비교해서 다른 수가 있다면 그 수를 반환하는 코드를 작성했다.

하지만 이게 정상작동하려면 배열의 길이가 순차적이라는 조건이 추가되어야 했다.

그래서 sort method를 썼더니 시간복잡도가 O(nlongn)으로 O(n)보다는 긴 시간이 걸렸다.

또 다른 문제는 배열을 선언하고 n의 길이만큼의 요소를 추가해서 공간복잡도가 O(n)으로 늘었다.

 

다시 O(n)으로 줄여보자

 

const origin = new Map()
const range = arr.length*2-1

for(let i= 0; i < arr.length ; i+=1){
	origin.set(arr[i],1)
}
    
for(let i=1; i<range; i += 2){
	if(!origin[i]){
    	return i
    }
}

return 0;

이번엔 hash map을 썼다. 

배열에 있는 요소를 map에 추가해주고 1부터 모든 홀수를 map에 있는 지 indexing으로 찾은 후 없다면 그 값을 반환, for 문을 빠져나왔다면 0을 반환하도록 했다.

 

indexing으로 값을 찾을 수 있어서 sort 해주지 않아도 되서 시간복잡도가 O(n)으로 줄었다.

공간복잡도는 map 객체가 n만큼의 자리를 차지하고 있기 때문에 여전히 O(n)이다. 

 

이제 공간복잡도를 O(1)로 줄여보자고 하셨다. 

여기서 애를 많이 먹었는데 완전 다르게 접근해야 했는데 도저히 생각이 안났다.

보니까 나는 코드를 작성하면서 논리를 생각한다고 하시며 문제의 근본으로 돌아가보라고 말씀해주셨다.

ㅎㅎㅎㅎㅎ 힌트 아닌 힌트를 주시는 면접관님.

 

여기서 시간이 오래 걸리고 오래 걸릴수록 머리도 잘 안돌아가서 좀 힘들었지만 누군가 나의 문제풀이방향을 보고 피드백을 주고 분석해주고 하는 게 너무 좋고 신기했다.

 

문제에서 중요한 점은 원본배열보다 항상 인풋배열의 길이가  하나 작다는 것이었다.

그 하나 작은 수를 찾는 게 문제라 원본배열의 모든 수를 합한 값에서 인풋배열의 모든 수를 합한 값을 빼면 답이 나오는 문제였다! 

이걸 알아내기까지 너무너무 오래 걸렸고 아마 이전에 푼 알고리즘문제에서 한번쯤 마주쳤을 법한 문제라 너무 짜증나면서 알아내서 좋았다. 이렇게 간단한 문제를 너무 오래 끌고 와서 좀 민망했다.

 

배열의 모든 수를 밖으로 꺼내는 것까지 생각했는데 그리고 든 생각이 꺼낸 애들을 담을 곳이 없네였다.

그렇게 말하니까 면접관님이 코드를 생각하지 말라고 하셨다 ㅎㅎㅎㅎㅎㅎㅎㅎㅎㅎㅎ 

모두 꺼내서 빼면 되는데 코드로 접근하니 그렇게 생각이 못갔단 거 같다. 

내 사고가 코드에 갇혀있다는 걸 처음 알았다. 너무 신기해.

 

아하! 하고 문제를 풀었다.

const range = arr.length*2 - 1;

const sum = arr.reduce((pre,cur) =>pre + cur,0);

let total = 0;
for(let i=1; i<= range; i+=2){
	total += i
}

return total - sum

잘왔다 여기까지. 

근데 또 여기서 for문을 안돌리고 문제를 풀어보라고 하셨다. ㅎㅎㅎㅎㅎㅎㅎㅎㅎ 모든 수의 합을 다른 방법으로 구해보라고. 

 

for문이나 reduce없이 모든 수의 합을 구해본 적이 없는데요..

규칙을 찾으려고 홀수를 나열해서 더해보니 더한 값이 n의 제곱이라는 것을 발견했다.

이건 내가 단순 나열해서 구한 규칙이고 이걸 수학적으로 증명한다면 가우스의 수학..어쩌구를 쓸 수 있다고 말씀해주셨다.

 

1, 3, 5 ... 2n-1 은 즉 1, 3 , 5 ... 2n-5, 2n-3, 2n-1이니까 가장 앞의 수와 가장 뒤의 수를 더하면 2n이 되고 그게 n/2개 만큼 있는거니 곱해주면 되서 n제곱이 되는 거였다!

const sum = arr.reduce((pre,cur) => pre + cur , 0);

const origin = Math.pow(arr.length, 2);

return origin - sum

최종 정답.

 

너무너무 재밌었다. 끝까지 오니 이렇게 간단한 문제를 이렇게 어렵게 오래 풀다니!! 싶어서 좀 아쉬웠지만 혼자 했다면 이 사고과정까지 오지 못했을 거 같아서 또 그렇게 아쉽진 않았다. 

 

멋진 사고과정과 좋은 알고리즘을 보여드리지 못해서 면접의 결과는 떨어질 거 같지만 경험 자체가 굉장히 긍정적이었고 즐거웠다. 

 

나 혼자 공부하고 파는 것의 한계를 한번 더 느끼기도 했다. 이래서 스터디하고 함께 고민하고 공부하면서 사고가 확장될 수 있는 거구나. 역시 재밌다. 

알고리즘 문제 계속 공부할 동력을 받아왔다. 면접에서 긍정적 느낌을 받기가 쉽지 않은데 정말 좋았다.