11일차

게일 라크만 맥도웰의 코딩 인터뷰 완전 분석 2.3~ 2.8

내용 정리

9 면접 문제

2.3 중간 노드 삭제

단방향 연결리스트가 주어졌을 때 중간(정확히 가운데 노드일 필요는 없고 처음과 끝 노드만 아니면 된다)에 있는 노드 하나를 삭제하는 알고리즘을 구현하라. 단, 삭제할 노드에만 접근할 수 있다.

예제

입력 : 연결리스트 a->b->c->d->e 에서 노드 c

결과 : 아무것도 반환할 필요는 없지만, 결과로 연결리스트 a->b->d->e가 되어 있어야 한다.

답 : 예제에서 삭제할 노드인 c의 다음 노드 d를 복사해서 c에 붙여 넣는다. d(c였으나 복사하여서 d가 된)를 d(원래 d)의 다음 노드인 e에 연결한 후 d를 삭제한다.

2.4 분할

값 x가 주어졌을 때 x보다 작은 노드들을 x보다 크거나 같은 노드들보다 앞에 오도록 하는 코드를 작성하라. 만약 x가 리스트에 있다면 x는 그보다 작은 원소들보다 뒤에 나오기만 하면 된다. 즉 원소 x는 ‘오른쪽 그룹’ 어딘가에만 존재하면 된다. 왼쪽과 오른쪽 그룹 사이에 있을 필요는 없다.

예제

입력 : 3->5->8->5->10->2->1 [분할값 x = 5]

출력 : 3->1->2->10->5->5->8

답 : 처음으로 나타나는 x보다 크거나 같은 노드와 그 ‘이전 노드’를 저장한다. 이후에 x보다 작은 노드가 나타나면 ‘이전노드’에 연결하고 기존의 위치에서 삭제한 뒤 계속 순회하며 반복한다. 더이상 나타나지 않으면 처음으로 나타난 x보다 크거나 같은 노드를 이어서 연결한다.

2.5 리스트의 합

연결리스트로 숫자를 표현할 때 각 노드가 자릿수 하나를 가리키는 방식으로 표현할 수 있다. 각 숫자는 역순으로 배열되어 있는데, 첫 번째 자릿수가 리스트의 맨 앞에 위치하도록 배열된다는 뜻이다. 이와 같은 방식으로 표현된 숫자가 두 개가 있을 때, 이 두 수를 더하여 그 합을 연결리스트로 반환하는 함수를 작성하라.

예제

입력 : (7->1->6) + (5->9->2). 즉, 617 + 295

출력 : 2->1->9. 즉, 912

def main(a,b):
    i = 0 # a의 자릿수가 b보다 크거나 같다고 가정
    cnt = 0
    arr = [0 for _ in range(len(a))]
    while i <= len(b):
        if cnt:
            arr[i] += cnt
            cnt = 0
        if a[i] + b[i] >= 10:
            cnt += 1
        arr[i] += (a[i]+b[i])%10
    while i <= len(a):
        if cnt:
            arr[i] += cnt
            cnt = 0
        arr[i] += a[i]
    return arr

연관 문제

각 자릿수가 정상적으로 배열된다고 가정하고 같은 문제를 풀어 보자.

예제

입력 : (6->1->7) + (2->9->5). 즉, 617 + 295

출력 : 9->1->2. 즉, 912

def main(a,b):
    A = len(a) # a의 자릿수가 b보다 크거나 같다고 가정
    B = len(b)
    k = A-B
    arr = [0 for _ in range(A)]
    cnt = 0
    for i in range(A,B-1,-1):
        if cnt:
            arr[i-1] += cnt
            cnt = 0
        arr[i] = (a[i]+b[i-k])%10
        if a[i]+b[i] >= 10:
            cnt += 1
    for i in range(k,-1,-1):
        if cnt:
            arr[i] += cnt
            cnt = 0
        arr[i] += a[i]
    return arr

2.6 회문

주어진 연결리스트가 회문(palindrome)인지 검사하는 함수를 작성하라.

답 : 연결리스트의 길이를 파악한 후, 앞의 절반을 스택에 넣고 절반이후부터 스택에서 하나씩 꺼내며 같은지 확인한다.

2.7 교집합

단방향 연결리스트가 두 개가 주어졌을 때 이 두 리스트의 교집합 노드를 찾은 뒤 반환하는 코드를 작성하라. 여기서 교집합이란 노드의 값이 아니라 노드의 주소가 완전히 같은 경우를 말한다. 즉, 첫 번째 리스트에 있는 k번째 노드와 두 번째 리스트에 있는 j번째 노드가 주소까지 완전히 같다면 이 노드는 교집합의 원소가 된다.

나의 답 : 주소..?

정답

각 연결리스트를 순회하면서 길이와 마지막 노드를 구한다.
마지막 노드를 비교한 뒤, 그 참조값이 다르다면 교집합이 없다는 사실을 바로 반환한다.
두 연결리스트의 시작점에 포인터를 놓는다.
길이가 더 긴 리스트의 포인터를 두 길이의 차이만큼 앞으로 움직인다.
두 포인터가 같아질 때까지 두 리스트를 함께 순회한다.

루프 발견

순환 연결리스트(circular linked list)가 주어졌을 때, 순환되는 부분의 첫째 노드를 반환하는 알고리즘을 작성하라. 순환 연결리스트란 노드의 next 포인터가 앞선 노드들 가운데 어느 하나를 가리키도록 설정되어 있는, 엄밀히 말해서 변질된 방식의 연결리스트를 의미한다.

예제

입력 : A->B->C->D->E->C(앞에 나온 C와 같음)

출력 : C

나의 답 : 순회하며 큐(queue) 에 넣어 찾는다.

정답

두 포인터 FastPointer와 SlowPointer를 만든다.
FastPointer는 한 번에 두 노드, SlowPointer는 한 번에 한 노드씩 움직인다.
두 포인터가 만나면, SlowPointer는 LinkedListHead로 옮기고, FastPointer는 그 자리에 그대로 둔다.
SlowPointer와 FastPointer를 한 번에 한 노드씩 움직인다. 이 둘이 만나는 지점을 반환한다.

읽고 나서

파이썬은 기본적으로 연결리스트가 주어지다보니 생각해본적 없는 문제들이라 많이 힘들었다.

자료구조(5) 연결리스트

MySQL 공부