실제 면접 코딩테스트 문제 (Python)

오늘은 지원했던 회사에서 감사하게도 면접을 볼 기회를 주셔서 면접을 보러 다녀왔습니다.

면접 시 문제로 나왔던 문제를

다시 풀어보니 어려운 문제가 아니었지만 면접시간에 조건에 맞는 코드를 작성하지 못하여 면접이 끝나고 다시 도전해보았습니다.

먼저 문제는 다음과 같습니다.

 

문제

다음과 같이 정렬된 리스트 3개가 주어졌을때 3개의 리스트에 모두 존재하는 값을 찾아 출력하시오.

(단, 정렬된 리스트라는 조건을 활용하여 최대한 효율적인 코드를 작성하시오)

 

Sample input

a = [ 1, 3, 5, 7, 9, 13, 15 ]
b = [ 4, 5, 6, 8, 13 ]
c = [ 5, 8, 13, 19 ]

Sample output

[ 5, 13 ]

 

저는 이문제를 보고 처음에는 in 을 사용하여 문제를 풀었습니다.

 

면접 시 작성했던 코드

answer = []
for i in range(len(a)):
    if ( a[i] in b ) and ( a[i] in c ):
        answer.append(a[i])
print(answer)

물론 이렇게 풀어도 문제는 없지만 in의 시간복잡도가 O(n)이고 a 의 길이만큼 다 탐색을 해야하기에

지금은 데이터의 크기가 작아서 상관없지만 나중에 데이터의 크기가 커지면 시간이 오래걸리는 문제가 생길 수 있습니다.

 

면접 때 풀지못하였던 것이 너무 아쉬워 집으로 돌아와 다시 만들어 보았습니다.

 

집에서 다시 풀어본 코드

def getDuplicateNums(a, b, c):
    answer = []

    a_index = 0
    b_index = 0
    c_index = 0

    while(True):
        if a_index >= len(a) or b_index >= len(b) or c_index >= len(c):
            break
        a_val = a[a_index]
        b_val = b[b_index]
        c_val = c[c_index]

    #     print(a_val, b_val, c_val)

        if a_val == b_val == c_val:
            answer.append(a_val)
            a_index = a_index + 1
            b_index = b_index + 1
            c_index = c_index + 1
        elif min([a_val, b_val, c_val]) == a_val:
            a_index = a_index + 1
        elif min([a_val, b_val, c_val]) == b_val:
            b_index = b_index + 1
        elif min([a_val, b_val, c_val]) == c_val:
            c_index = c_index + 1
        
    return answer

이 방법은 세개의 리스트가 정렬되어있다는 조건을 가지고 있으므로

세개의 리스트를 탐색할 index를 a_index, b_index, c_index로 모두 0으로 설정한 후

그 index를 가지고 가장 앞쪽의 리스트 내의 가장 작은 값을 하나씩 가져와 비교하여 같을 경우

정답 리스트에 추가해주는 방식을 사용했습니다.

 

조금 더 자세히 보면

 

while 반복문을 돌면서 

a_index, b_index, c_index의 값이 각자 탐색하는 리스트의 길이보다 같거나 커지면 반복문을 종료하도록 조건을 걸어주고

그렇지 않을경우 a_val, b_val, c_val에 a_index, b_index, c_index 위치의 값을 가져온 뒤 비교합니다.

 

만약 a_val, b_val, c_val이 모두 같을 경우 answer list에 추가한뒤

a_index, b_index, c_index 값을 각각 1씩 증가하여 각각 다음의 값을 가져오도록 하였고

그렇지 않으면 a_val, b_val, c_val 값중에 가장 작은 값을 가지고 있는 곳의 index를 다음값으로 설정하여

해당 값의 다음 값을 가져오도록 하였습니다.

 

해당 예제에서는 

1 4 5 -> 3 4 5 -> 5 4 5 -> 5 5 5 (5 저장) -> 7 6 8 -> 7 8 8 -> 9 8 8 -> 9 13 8 -> 9 13 13 -> 13 13 13 (13 저장)

 

풀긴하였으나 생각보다 효율이 떨어지는 것 같기도하여 다시 더 고민해보고

더 효율적인 방법이 있다면 다시 풀어보려합니다.

 

아직 코딩테스트를 수월하게 하기위해서는 더 공부해야한다는 것을 느낄수있었습니다.

 

읽어주셔서 감사합니다.

 

SOMJANG/CODINGTEST_PRACTICE