면접 문제
2.3 중간 노드 삭제
- 단방향 연결리스트가 주어졌을 때 중간(정확히 가운데 노드일 필요는 없고 처음과 끝 노드만 아니면 된다.)에 있는 노드 하나를 삭제하는 알고리즘을 구현하라. 단, 삭제할 노드에만 접근할 수 있다.
- 예제
- 입력 : 연결리스트 a → b → c → d → e 에서 노드 c
- 결과 : 아무것도 반환할 필요는 없지만, 결과로 연결리스트 a → b → d → e가 되어 있어야 한다.
- 힌트
- 리스트 1 → 5 → 9 → 12를 그려보자. 9를 지우면 1 → 5 → 12가 된다. 9 노드에만 접근할 수 있다. 정답처럼 보이게 만들 수 있겠는가?
public class Solution {
public static boolean deleteNode(LinkedListNode n) {
if (n == null || n.next == null) {
return false; // 삭제할 노드가 리스트의 마지막 노드일 경우 삭제 할 수 없음.
}
LinkedListNode next = n.next;
n.data = next.data;
n.next = next.next;
return true;
}
public static void main(String[] args) {
LinkedListNode head = randomLinkedList(10, 0, 10);
System.out.println(head.printForward());
deleteNode(head.next.next.next.next); // delete node 4
System.out.println(head.printForward());
}
public static LinkedListNode randomLinkedList(int N, int min, int max) {
LinkedListNode root = new LinkedListNode(randomIntInRange(min, max),
null, null);
LinkedListNode prev = root;
for (int i = 1; i < N; i++) {
int data = randomIntInRange(min, max);
LinkedListNode next = new LinkedListNode(data, null, null);
prev.setNext(next);
prev = next;
}
return root;
}
}
- 삭제할 노드에만 접근할 수 있기에 헤드에 접근할 수 없음.
- 삭제할 노드의 다음 노드의 데이터를 삭제할 노드에 복사하고, 다음 노드를 지우면 됨.
- 삭제할 노드가 리스트의 마지막 노드일 경우 삭제할 수 없음.
- 마지막 노드인 경우, 그냥 dummy 노드로 표시해두는 방법도 있음.
2.4 분할
- x가 주어졌을 때 x보다 작은 노드들을 x보다 크거나 같은 노드들보다 앞에 오도록 하는 코드를 작성하라. 만약 x가 리스트에 있다면 x는 그보다 작은 원소들보다 뒤에 나오기만 하면 된다. 즉 원소 x는 ‘오른쪽 그룹’ 어딘가에만 존재하면 된다. 왼쪽과 오른쪽 그룹 사이에 있을 필요는 없다.
- 예제
- 입력 : 3 → 5 → 8 → 5 → 10 → 2 → 1 [분할값 x = 5]
- 출력 : 3 → 1 → 2 → 10 → 5 → 5 → 8
- 힌트
- 이 문제를 푸는 방법은 다양하다. 대부분의 최적 해법의 수행 시간도 동일하다. 어떤 코드는 다른 코드보다 좀 더 짧거나 깔끔하다. 다양한 해법을 브레인스토밍해 볼 수 있겠는가?
- 원소의 상대적인 순서가 달라져도 되는 경우를 먼저 생각해 보라. 피벗보다 작은 원소는 피벗보다 큰 원소 이전에만 위치하면 된다. 이게 다른 해법을 생각하는 데 도움이 되었는가?
2.5 리스트의 합
- 연결리스트로 숫자를 표현할 때 각 노드가 자릿수 하나를 가리키는 방식으로 표현할 수 있다. 각 숫자는 역순으로 배열되어 있는데, 첫 번째 자릿수가 리스트의 밴 앞에 위치하도록 배열된다는 뜻이다. 이와 같은 방식으로 표현된 숫자 두 개가 있을 때, 이 두 수를 더하여 그 합을 연결리스트로 반환하는 함수를 작성하라.
- 예제
- 입력 : (7 → 1 → 6) + (5 → 9 → 2). 즉, 617 + 295.
- 출력 : 2 → 1 → 9. 즉, 912
- 연관 문제 : 각 자릿수가 정상적으로 배열된다고 가정하고 같은 문제를 풀어보자.
- 예제
- 입력 : (6 → 1 → 7) + (2 → 9 → 5). 즉, 617 + 295.
- 출력 : 9 → 1 → 2. 즉, 912
- 힌트
- 연결리스트를 정수형으로 바꾸고, 합을 계산하고, 다시 새로운 연결리스트로 바꿔도 된다. 하지만 여러분이 면접에서 이렇게 얘기한다면, 면접관도 아마 괜찮다고 말한 뒤, 여러분이 정수로 바꾸지 않고 문제를 푸는 방법을 찾을 수 있는지 지켜볼 것이다.
- 재귀를 사용해 보라. A = 1 → 5 → 9 (951를 나타냄)와 B = 2 → 3 → 6 → 7 (7632를 나타냄), 이렇게 두 개의 리스트와 리스트의 나머지 (5 → 9와 3 → 6 → 7)에서 동작하는 함수가 있다고 하자. 이를 이용해서 sum 메서드를 만들 수 있겠는가? sum(1→5→9, 2→3→6→7)과 sum(5→9, 3→6→7)에는 무슨 관계가 있는가?
- 길이가 같지 않은 연결리스트를 고려해 봐야 한다.
- 여러분의 알고리즘이 9 → 7 → 8과 6 → 8 → 5 같은 연결리스트에서도 잘 작동하는가? 다시 한번 확인해 보길 바란다.
- 연관 문제
- 두 연결리스트의 길이가 같지 않을 때, 어떤 연결리스트의 헤드는 1000의 자리수를 가리키는 반면에 다른 연결리스트의 헤드는 10의 자리 수를 가리키는 문제가 발생할 수 있다. 두 ㅇ녀결리스트의 길이를 같게 만들면 어떠한가? 값을 변경하지 않으면서 두 연결리스트의 길이가 같아지도록 수정하는 방법이 있는가?
2.6 회문
- 주어진 연결리스트가 회문(palindrome)인지 검사하는 함수를 작성하라.
- 힌트
- 회문(palindrome)은 앞으로 읽으나 뒤로 읽으나 같은 것ㅇ르 말한다. 연결리스트를 뒤집으면 어떻게 되겠는가?
- 스택을 사용해 보라.
- 연결리스트의 길이를 알고 있ㄷ다고 가정하라. 재귀적으로 구현할 수 있겠는가?
- 재귀를 사용하면(리스트의 길이를 알고 있다), 가운데 지점이 기본 사례까 된다. isPermutation(middle)은 참이 된다. middle의 바로 왼쪽 노드인 x를 살펴보자. x → middle → y의 형태가 회문인지 확인하려면 무엇을 해야 할까? 이 부분이 회문이라고 하자. 그 이전 노드인 a는 어떤가? x → middle → y 가 횢문일 때, a → x → middle → y → b가 회문인지는 어떻게 확인할까?
- 이전 힌트로 돌아가 보라. 값 여러 개를 반환하는 방법이 있다는 사실을 기억하라. 새로운 클래스를 만들어서 할 수 있다.
2.7 교집합
- 단방향 연결리스트 두 개가 주어졌을 때 이 두 리스트의 교집합 노드를 찾은 뒤 반환하는 코드를 작성하라. 여기서 교집합이란 노드의 값이 아니라 노드의 주소가 완전히 같은 경우를 말한다. 즉, 첫 번째 리스트에 있는 k번째 노드와 두 번째 리스트에 있는 j번째 노드가 주소까지 완전히 같다면 이 노드는 교집합의 원소가 된다.
- 힌트
- O(A+B) 시간과 O(1) 공간에 풀 수 있다. 즉, 해시테이블이 필요 없다.
- 예제를 사용하면 도움이 될 것이다. 연결리스트가 교차하는 그림을 그려보라. 또한 값이 같은 두 개의 동일한 연결리스트를 교차하지 않게 그려보라.
- 먼저 교차하는 지점이 있는지를 어떻게 확인할 것인지부터 생각해 보자.
- 서로 교차하는 두 개의 연결리스트의 마지막 노드는 항상 같다. 교차하는 노드 이후의 노드는 모두 같다.
- 마지막 노드를 비교함으로써 두 연결리스트가 교차하는지 아닌지 판단할 수 있다.
- 이제 어디서 연결리스트가 교차하는지 찾아야 한다. 연결리스트의 길이가 같다고 가정하자. 어떻게 할 수 있겠는가?
- 두 연결리스트의 길이가 같다면, 공통된 원소를 찾을 때까지 같이 하나씩 읽어나가면 된다. 리스트의 길이가 다른 경우에는 이를 어떻게 조절할 수 있을까?
- 두 연결리스트 길이의 차이를 사용해 보라.
- 길이가 긴 연결리스트에서 포인터를 두 리스트의 길이의 차이만큼 앞에 놓고, 길이가 짧은 연결리스트에서는 포인터를 맨 앞에 놓는다. 그 다음에 마치 두 연결리스트의 길이가 같은 것처럼 알고리즘을 적용할 수 있겠는가?
2.8 루프 발견
- 순환 연결리스트(circular linked list)가 주어졌을 때, 순한되는 부분의 첫째 노드를 반환하는 알고리즘을 작성하라. 순환 연결리스트란 노드의 next 포인터가 앞선 노드들 가운데 어느 하나를 가리키도록 설정되어 있는, 엄밀히 말해서 변질된 방식의 연결리스트를 의미한다.
- 예제
- 입력 : A → B → C → D → E → C(앞에 나온 C와 같음)
- 출력 : C
- 힌트