손코딩 | Tech Interview

손코딩 기술면접 18문항의 기본 답변과 핵심 개념을 정리합니다. 구현 접근법.

현재 주제에서 검색전체 18문항

1. 삽입 정렬, 병합 정렬, 퀵 정렬을 구현해 보세요.

접근 방법

삽입 정렬은 정렬된 구간을 확장하는 반복 구조를, 병합 정렬과 퀵 정렬은 분할 정복과 재귀 구현을 확인하기 좋습니다.

각 정렬의 핵심 불변식, 안정성, 시간·공간복잡도를 설명하면서 구현하는 것이 중요합니다.

핵심 키워드

Insertion Sort
Merge Sort
Quick Sort
Stable Sort

구현 포인트

Insertion Sort: 현재 값을 앞쪽 정렬된 구간의 적절한 위치에 삽입합니다.
Merge Sort: 배열을 반으로 나누고 정렬된 두 배열을 병합합니다.
Quick Sort: pivot 기준으로 작은 값과 큰 값을 분할한 뒤 재귀 정렬합니다.

구현 예시

#include <bits/stdc++.h>
using namespace std;

void insertionSort(vector<int>& a) {
    for (int i = 1; i < (int)a.size(); i++) {
  int value = a[i];
  int j = i - 1;
  while (j >= 0 && a[j] > value) {
      a[j + 1] = a[j];
      j--;
  }
  a[j + 1] = value;
    }
}

void mergeRange(vector<int>& a, vector<int>& temp, int left, int mid, int right) {
    int i = left, j = mid + 1, k = left;
    while (i <= mid && j <= right) {
  temp[k++] = a[i] <= a[j] ? a[i++] : a[j++];
    }
    while (i <= mid) temp[k++] = a[i++];
    while (j <= right) temp[k++] = a[j++];
    for (int p = left; p <= right; p++) a[p] = temp[p];
}

void mergeSort(vector<int>& a, vector<int>& temp, int left, int right) {
    if (left >= right) return;
    int mid = left + (right - left) / 2;
    mergeSort(a, temp, left, mid);
    mergeSort(a, temp, mid + 1, right);
    mergeRange(a, temp, left, mid, right);
}

void mergeSort(vector<int>& a) {
    vector<int> temp(a.size());
    if (!a.empty()) mergeSort(a, temp, 0, (int)a.size() - 1);
}

void quickSort(vector<int>& a, int left, int right) {
    if (left >= right) return;
    int pivot = a[(left + right) / 2];
    int i = left, j = right;

    while (i <= j) {
  while (a[i] < pivot) i++;
  while (a[j] > pivot) j--;
  if (i <= j) swap(a[i++], a[j--]);
    }

    quickSort(a, left, j);
    quickSort(a, i, right);
}

import java.util.*;

class Main {
    static void insertionSort(int[] a) {
  for (int i = 1; i < a.length; i++) {
      int value = a[i];
      int j = i - 1;
      while (j >= 0 && a[j] > value) {
          a[j + 1] = a[j];
          j--;
      }
      a[j + 1] = value;
  }
    }

    static void mergeSort(int[] a) {
  if (a.length > 1) mergeSort(a, new int[a.length], 0, a.length - 1);
    }

    static void mergeSort(int[] a, int[] temp, int left, int right) {
  if (left >= right) return;
  int mid = left + (right - left) / 2;
  mergeSort(a, temp, left, mid);
  mergeSort(a, temp, mid + 1, right);
  int i = left, j = mid + 1, k = left;
  while (i <= mid && j <= right) {
      temp[k++] = a[i] <= a[j] ? a[i++] : a[j++];
  }
  while (i <= mid) temp[k++] = a[i++];
  while (j <= right) temp[k++] = a[j++];
  for (int p = left; p <= right; p++) a[p] = temp[p];
    }

    static void quickSort(int[] a, int left, int right) {
  if (left >= right) return;
  int pivot = a[(left + right) / 2];
  int i = left, j = right;

  while (i <= j) {
      while (a[i] < pivot) i++;
      while (a[j] > pivot) j--;
      if (i <= j) {
          int tmp = a[i];
          a[i++] = a[j];
          a[j--] = tmp;
      }
  }

  quickSort(a, left, j);
  quickSort(a, i, right);
    }
}

def insertion_sort(arr):
    for i in range(1, len(arr)):
        value = arr[i]
        j = i - 1
        while j >= 0 and arr[j] > value:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = value
    return arr

def merge_sort(arr):
    if len(arr) <= 1:
        return arr[:]
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    result = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    return result + left[i:] + right[j:]

def quick_sort(arr):
    if len(arr) <= 1:
        return arr

    pivot = arr[len(arr) // 2]
    left = [x for x in arr if x < pivot]
    mid = [x for x in arr if x == pivot]
    right = [x for x in arr if x > pivot]
    return quick_sort(left) + mid + quick_sort(right)

복잡도

Insertion Sort 평균 및 최악: O(N^2), 최선: O(N)
Merge Sort: O(N log N), 추가 메모리 O(N)
Quick Sort 평균: O(N log N), 최악: O(N^2)

주의할 점

Quick Sort는 pivot 선택이 중요합니다.
Merge Sort 병합 과정에서 인덱스 경계 처리를 조심해야 합니다.

2. 배열을 이용해 Stack과 원형 Queue를 직접 구현해 보세요.

접근 방법

표준 컬렉션의 push/pop이나 queue 연산을 그대로 감싸지 않고, 고정 크기 배열과 인덱스로 핵심 동작을 구현합니다.

스택은 top 인덱스, 원형 큐는 front/rear와 현재 크기를 관리하는 것이 핵심입니다.

핵심 키워드

Stack
Queue
Array
Top
Circular Buffer
Front/Rear

구현 포인트

Stack: push, pop, peek, isEmpty, overflow 검사
Queue: offer, poll, peek, modulo를 이용한 원형 인덱스 처리

구현 예시

#include <bits/stdc++.h>
using namespace std;

class ArrayStack {
    vector<int> data;
    int topIndex = -1;
public:
    explicit ArrayStack(int capacity) {
  if (capacity <= 0) throw invalid_argument("capacity must be positive");
  data.resize(static_cast<size_t>(capacity));
    }
    bool isEmpty() const { return topIndex < 0; }
    void push(int x) {
  if (topIndex + 1 == (int)data.size()) throw overflow_error("stack is full");
  data[++topIndex] = x;
    }
    int pop() {
  if (isEmpty()) throw underflow_error("stack is empty");
  return data[topIndex--];
    }
    int peek() const {
  if (isEmpty()) throw underflow_error("stack is empty");
  return data[topIndex];
    }
};

class CircularQueue {
    vector<int> data;
    int front = 0, rear = 0, count = 0;
public:
    explicit CircularQueue(int capacity) {
  if (capacity <= 0) throw invalid_argument("capacity must be positive");
  data.resize(static_cast<size_t>(capacity));
    }
    bool isEmpty() const { return count == 0; }
    void offer(int x) {
  if (count == (int)data.size()) throw overflow_error("queue is full");
  data[rear] = x;
  rear = (rear + 1) % data.size();
  count++;
    }
    int poll() {
  if (isEmpty()) throw underflow_error("queue is empty");
  int value = data[front];
  front = (front + 1) % data.size();
  count--;
  return value;
    }
    int peek() const {
  if (isEmpty()) throw underflow_error("queue is empty");
  return data[front];
    }
};

class ArrayStack {
    private final int[] data;
    private int top = -1;

    ArrayStack(int capacity) {
  if (capacity <= 0) throw new IllegalArgumentException("capacity must be positive");
  data = new int[capacity];
    }
    boolean isEmpty() { return top < 0; }
    void push(int x) {
  if (top + 1 == data.length) throw new IllegalStateException("stack is full");
  data[++top] = x;
    }
    int pop() {
  if (isEmpty()) throw new IllegalStateException("stack is empty");
  return data[top--];
    }
    int peek() {
  if (isEmpty()) throw new IllegalStateException("stack is empty");
  return data[top];
    }
}

class CircularQueue {
    private final int[] data;
    private int front = 0;
    private int rear = 0;
    private int size = 0;

    CircularQueue(int capacity) {
  if (capacity <= 0) throw new IllegalArgumentException("capacity must be positive");
  data = new int[capacity];
    }
    boolean isEmpty() { return size == 0; }
    void offer(int x) {
  if (size == data.length) throw new IllegalStateException("queue is full");
  data[rear] = x;
  rear = (rear + 1) % data.length;
  size++;
    }
    int poll() {
  if (isEmpty()) throw new IllegalStateException("queue is empty");
  int value = data[front];
  front = (front + 1) % data.length;
  size--;
  return value;
    }
    int peek() {
  if (isEmpty()) throw new IllegalStateException("queue is empty");
  return data[front];
    }
}

class ArrayStack:
    def __init__(self, capacity):
        if capacity <= 0:
            raise ValueError("capacity must be positive")
        self.data = [0] * capacity
        self.top = -1

    def is_empty(self):
        return self.top < 0
    def push(self, x):
        if self.top + 1 == len(self.data):
            raise OverflowError("stack is full")
        self.top += 1
        self.data[self.top] = x
    def pop(self):
        if self.is_empty():
            raise IndexError("stack is empty")
        value = self.data[self.top]
        self.top -= 1
        return value
    def peek(self):
        if self.is_empty():
            raise IndexError("stack is empty")
        return self.data[self.top]

class CircularQueue:
    def __init__(self, capacity):
        if capacity <= 0:
            raise ValueError("capacity must be positive")
        self.data = [0] * capacity
        self.front = self.rear = self.size = 0

    def is_empty(self):
        return self.size == 0
    def offer(self, x):
        if self.size == len(self.data):
            raise OverflowError("queue is full")
        self.data[self.rear] = x
        self.rear = (self.rear + 1) % len(self.data)
        self.size += 1
    def poll(self):
        if self.is_empty():
            raise IndexError("queue is empty")
        value = self.data[self.front]
        self.front = (self.front + 1) % len(self.data)
        self.size -= 1
        return value
    def peek(self):
        if self.is_empty():
            raise IndexError("queue is empty")
        return self.data[self.front]

복잡도

Stack/Queue 기본 연산: O(1)
고정 용량 배열 공간: O(capacity)

주의할 점

빈 자료구조, 원소 1개, 가득 찬 상태, 원형 인덱스가 배열 끝을 넘는 케이스를 확인해야 합니다.

3. 배열에 1,000,000개의 수가 있을 때, 원하는 수가 몇 번째 인덱스에 위치해 있는지 확인하는 프로그램을 작성해 보세요. 단, 원하는 수가 하나가 아닐 수 있습니다.

접근 방법

한 번만 찾는다면 배열을 처음부터 끝까지 순회하며 원하는 값과 같은 인덱스를 모두 수집하면 됩니다.

같은 배열에서 여러 번 조회해야 한다면 값별 인덱스 목록을 해시맵으로 미리 만들어두는 방식이 좋습니다.

핵심 키워드

Linear Search
HashMap
Index List
Preprocessing

구현 포인트

단일 조회: for문으로 모든 인덱스를 확인합니다.
다중 조회: Map<Value, List<Index>>를 구성합니다.
값이 없을 때 빈 리스트나 -1을 반환하도록 정책을 정합니다.

구현 예시

#include <bits/stdc++.h>
using namespace std;

vector<int> findAllIndexes(const vector<int>& arr, int target) {
    vector<int> indexes;
    for (int i = 0; i < (int)arr.size(); i++) {
  if (arr[i] == target) indexes.push_back(i);
    }
    return indexes;
}

import java.util.*;

class Main {
    static List<Integer> findAllIndexes(int[] arr, int target) {
  List<Integer> indexes = new ArrayList<>();
  for (int i = 0; i < arr.length; i++) {
      if (arr[i] == target) indexes.add(i);
  }
  return indexes;
    }
}

def find_all_indexes(arr, target):
    result = []
    for i, value in enumerate(arr):
        if value == target:
            result.append(i)
    return result

복잡도

단일 조회: 시간 O(N), 추가 공간 O(K)
전처리 방식: 전처리 O(N), 조회 평균 O(1), 공간 O(N)

주의할 점

“원하는 수가 하나가 아닐 수 있다”는 조건 때문에 첫 번째 발견에서 멈추면 안 됩니다.

4. 20개의 숫자가 주어졌을 때, 이 수중 일부 숫자들을 더해서 원하는 수를 만들 수 있는지 확인하는 프로그램을 작성해 보세요.

접근 방법

부분집합 합 문제입니다.

숫자가 20개라면 모든 부분집합을 탐색해도 2^20이라 약 100만 개 수준이므로 브루트포스가 가능합니다.

더 일반화하면 DP나 meet-in-the-middle을 고려할 수 있습니다.

핵심 키워드

Subset Sum
Backtracking
Bitmask
Dynamic Programming
Meet-in-the-middle

구현 포인트

비트마스크로 0부터 (1 << 20) - 1까지 순회하며 선택된 숫자의 합을 계산합니다.
백트래킹으로 현재 인덱스에서 선택/미선택 분기를 만들 수도 있습니다.
목표 합을 찾으면 즉시 true를 반환합니다.

구현 예시

#include <bits/stdc++.h>
using namespace std;

bool canMakeSum(const vector<int>& nums, int target) {
    if (nums.size() > 20) throw invalid_argument("at most 20 numbers");
    long long subsetCount = 1LL << nums.size();
    for (long long mask = 0; mask < subsetCount; mask++) {
  long long sum = 0;
  for (int i = 0; i < (int)nums.size(); i++) {
      if (mask & (1LL << i)) sum += nums[i];
  }
  if (sum == target) return true;
    }
    return false;
}

class Main {
    static boolean canMakeSum(int[] nums, int target) {
  if (nums.length > 20) throw new IllegalArgumentException("at most 20 numbers");
  int subsetCount = 1 << nums.length;
  for (int mask = 0; mask < subsetCount; mask++) {
      long sum = 0;
      for (int i = 0; i < nums.length; i++) {
          if ((mask & (1 << i)) != 0) sum += nums[i];
      }
      if (sum == target) return true;
  }
  return false;
    }
}

def can_make_sum(nums, target):
    if len(nums) > 20:
        raise ValueError("at most 20 numbers")
    for mask in range(1 << len(nums)):
        total = sum(nums[i] for i in range(len(nums)) if mask & (1 << i))
        if total == target:
            return True
    return False

복잡도

브루트포스: O(2^N * N) 또는 누적합 최적화 시 O(2^N)
N=20이면 충분히 시도 가능합니다.

주의할 점

예시는 N=20 조건을 활용한 비트마스크 완전탐색이므로 음수도 처리할 수 있습니다.
N이 더 커질 때 DP를 사용한다면 음수 포함 여부와 target 범위를 먼저 확인해야 합니다.

5. 1 ~ 999 까지의 아라비아 숫자가 주어졌을 때, 이 숫자를 로마숫자로 변환하는 프로그램을 작성해 보세요.

접근 방법

큰 값부터 대응되는 로마 숫자를 빼면서 문자열을 만들어갑니다.

900, 400, 90, 40, 9, 4처럼 감산 표기 케이스를 테이블에 포함하면 구현이 단순해집니다.

핵심 키워드

Roman Numeral
Greedy
Mapping Table
Subtractive Notation

구현 포인트

값과 문자를 배열로 둡니다: 900 CM, 500 D, 400 CD, 100 C, ...
숫자가 현재 값 이상이면 값을 빼고 해당 문자를 결과에 추가합니다.
1부터 999 범위 검증을 먼저 합니다.

구현 예시

#include <bits/stdc++.h>
using namespace std;

string toRoman(int n) {
    if (n < 1 || n > 999) throw invalid_argument("n must be between 1 and 999");
    vector<pair<int, string>> table = {
  {900, "CM"}, {500, "D"}, {400, "CD"}, {100, "C"},
  {90, "XC"}, {50, "L"}, {40, "XL"}, {10, "X"},
  {9, "IX"}, {5, "V"}, {4, "IV"}, {1, "I"}
    };

    string result;
    for (auto [value, symbol] : table) {
  while (n >= value) {
      result += symbol;
      n -= value;
  }
    }
    return result;
}

class Main {
    static String toRoman(int n) {
  if (n < 1 || n > 999) {
      throw new IllegalArgumentException("n must be between 1 and 999");
  }
  int[] values = {900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
  String[] symbols = {"CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};
  StringBuilder result = new StringBuilder();

  for (int i = 0; i < values.length; i++) {
      while (n >= values[i]) {
          result.append(symbols[i]);
          n -= values[i];
      }
  }
  return result.toString();
    }
}

def to_roman(n):
    if not 1 <= n <= 999:
        raise ValueError("n must be between 1 and 999")
    table = [
        (900, "CM"), (500, "D"), (400, "CD"), (100, "C"),
        (90, "XC"), (50, "L"), (40, "XL"), (10, "X"),
        (9, "IX"), (5, "V"), (4, "IV"), (1, "I"),
    ]
    result = []
    for value, symbol in table:
        while n >= value:
            result.append(symbol)
            n -= value
    return "".join(result)

복잡도

테이블 크기가 고정이라 시간과 공간은 사실상 O(1)입니다.

주의할 점

4, 9, 40, 90, 400, 900 감산 표기를 빼먹기 쉽습니다.

6. 배열을 정렬하지 않고, 배열의 중앙값을 구하는 코드를 작성해 보세요.

접근 방법

정렬하지 않는다는 조건이 있으므로 Quickselect를 사용해 k번째 원소를 찾습니다.

이 예시에서는 길이가 홀수면 N/2번째 값을, 짝수면 가운데 두 값의 산술평균을 중앙값으로 정의합니다.

핵심 키워드

Median
Quickselect
Partition
K-th Element

구현 포인트

Quick Sort의 partition을 사용합니다.
pivot의 최종 위치가 k이면 답입니다.
k보다 크면 왼쪽, 작으면 오른쪽만 재탐색합니다.

구현 예시

#include <bits/stdc++.h>
using namespace std;

int quickSelect(vector<int>& a, int k) {
    int left = 0, right = (int)a.size() - 1;
    while (left <= right) {
  int pivot = a[(left + right) / 2];
  int i = left, j = right;
  while (i <= j) {
      while (a[i] < pivot) i++;
      while (a[j] > pivot) j--;
      if (i <= j) swap(a[i++], a[j--]);
  }
  if (k <= j) right = j;
  else if (k >= i) left = i;
  else return a[k];
    }
    return a[k];
}

double median(const vector<int>& values) {
    if (values.empty()) throw invalid_argument("median of empty array");
    vector<int> a = values;
    int upper = quickSelect(a, a.size() / 2);
    if (a.size() % 2 == 1) return upper;
    int lower = quickSelect(a, a.size() / 2 - 1);
    return ((long long)lower + upper) / 2.0;
}

class Main {
    static double median(int[] values) {
  if (values.length == 0) throw new IllegalArgumentException("median of empty array");
  int[] a = values.clone();
  int upper = quickSelect(a, a.length / 2);
  if (a.length % 2 == 1) return upper;
  int lower = quickSelect(a, a.length / 2 - 1);
  return ((long) lower + upper) / 2.0;
    }

    static int quickSelect(int[] a, int k) {
  int left = 0, right = a.length - 1;
  while (left <= right) {
      int pivot = a[(left + right) / 2];
      int i = left, j = right;
      while (i <= j) {
          while (a[i] < pivot) i++;
          while (a[j] > pivot) j--;
          if (i <= j) {
              int t = a[i]; a[i++] = a[j]; a[j--] = t;
          }
      }
      if (k <= j) right = j;
      else if (k >= i) left = i;
      else return a[k];
  }
  return a[k];
    }
}

def quick_select(arr, k):
    left, right = 0, len(arr) - 1
    while left <= right:
        pivot = arr[(left + right) // 2]
        i, j = left, right
        while i <= j:
            while arr[i] < pivot:
                i += 1
            while arr[j] > pivot:
                j -= 1
            if i <= j:
                arr[i], arr[j] = arr[j], arr[i]
                i += 1
                j -= 1
        if k <= j:
            right = j
        elif k >= i:
            left = i
        else:
            return arr[k]
    return arr[k]

def median(arr):
    if not arr:
        raise ValueError("median of empty array")
    copied = arr[:]
    upper = quick_select(copied, len(copied) // 2)
    if len(copied) % 2 == 1:
        return upper
    lower = quick_select(copied, len(copied) // 2 - 1)
    return (lower + upper) / 2

복잡도

평균 시간 O(N), 최악 O(N^2)
Quickselect 자체는 반복 구현 시 추가 공간 O(1)이지만, 예시는 원본 보존을 위한 복사 때문에 O(N)을 사용합니다.

주의할 점

빈 배열은 중앙값이 없으므로 오류로 처리합니다.
짝수 길이에서 평균, 하위 중앙값, 상위 중앙값 중 어떤 정의를 원하는지 면접관에게 확인하는 것이 좋습니다.

7. 알파벳으로 이뤄진 단어가 있을 때, 이 단어에서 중복된 값을 제거하고 오름차순으로 정렬하는 코드를 작성해 보세요.

접근 방법

알파벳 범위가 제한되어 있으므로 boolean 배열이나 bitmask로 등장 여부를 기록한 뒤, a부터 z까지 순회하며 등장한 문자만 출력하면 됩니다.

핵심 키워드

Deduplication
Counting
Boolean Array
Bitmask
Alphabet

구현 포인트

소문자만 있다면 크기 26 boolean 배열을 사용합니다.
대소문자가 섞이면 범위를 확장하거나 정규화 정책을 정합니다.
결과는 알파벳 순서로 boolean 배열을 순회해 만듭니다.

구현 예시

#include <bits/stdc++.h>
using namespace std;

string uniqueSorted(string word) {
    vector<bool> seen(26, false);
    for (char c : word) {
  if ('a' <= c && c <= 'z') seen[c - 'a'] = true;
    }

    string result;
    for (int i = 0; i < 26; i++) {
  if (seen[i]) result += char('a' + i);
    }
    return result;
}

class Main {
    static String uniqueSorted(String word) {
  boolean[] seen = new boolean[26];
  for (char c : word.toCharArray()) {
      if ('a' <= c && c <= 'z') seen[c - 'a'] = true;
  }

  StringBuilder result = new StringBuilder();
  for (int i = 0; i < 26; i++) {
      if (seen[i]) result.append((char) ('a' + i));
  }
  return result.toString();
    }
}

def unique_sorted(word):
    seen = [False] * 26
    for ch in word:
        if "a" <= ch <= "z":
            seen[ord(ch) - ord("a")] = True

    return "".join(chr(ord("a") + i) for i in range(26) if seen[i])

복잡도

시간 O(N + 26), 공간 O(26)

주의할 점

입력이 영어 알파벳만인지, 대소문자 구분을 하는지 확인해야 합니다.

8. 두 배열이 주어졌을 때, 이 배열의 교집합을 구하는 코드를 작성해 보세요. 단, 배열을 제외한 추가적인 자료구조는 사용하지 말아주세요.

접근 방법

추가 자료구조를 사용할 수 없으므로 배열 자체를 정렬한 뒤 투 포인터로 교집합을 찾는 방식이 적합합니다.

정렬이 허용되지 않는다면 한 배열을 순회하며 다른 배열에서 선형 탐색해야 합니다.

핵심 키워드

Intersection
Sorting
Two Pointers
In-place
Duplicate Handling

구현 포인트

두 배열을 정렬합니다.
포인터 i, j를 두고 작은 값을 가진 쪽을 이동합니다.
값이 같으면 첫 번째 배열의 앞쪽 결과 구간에 덮어쓰고 둘 다 이동합니다.
중복을 제거할지 유지할지 정책을 정합니다.

구현 예시

#include <bits/stdc++.h>
using namespace std;

int intersectionInPlace(vector<int>& a, vector<int>& b) {
    sort(a.begin(), a.end());
    sort(b.begin(), b.end());

    int i = 0, j = 0, write = 0;
    while (i < (int)a.size() && j < (int)b.size()) {
  if (a[i] == b[j]) {
      if (write == 0 || a[write - 1] != a[i]) a[write++] = a[i];
      i++; j++;
  } else if (a[i] < b[j]) i++;
  else j++;
    }
    return write;
}

import java.util.*;

class Main {
    static int intersectionInPlace(int[] a, int[] b) {
  Arrays.sort(a);
  Arrays.sort(b);

  int i = 0, j = 0, write = 0;
  while (i < a.length && j < b.length) {
      if (a[i] == b[j]) {
          if (write == 0 || a[write - 1] != a[i]) a[write++] = a[i];
          i++; j++;
      } else if (a[i] < b[j]) i++;
      else j++;
  }
  return write;
    }
}

def intersection_in_place(a, b):
    a.sort()
    b.sort()
    i = j = write = 0

    while i < len(a) and j < len(b):
        if a[i] == b[j]:
            if write == 0 or a[write - 1] != a[i]:
                a[write] = a[i]
                write += 1
            i += 1
            j += 1
        elif a[i] < b[j]:
            i += 1
        else:
            j += 1

    return write

복잡도

정렬 기반: O(N log N + M log M)
투 포인터 병합: O(N + M)
예시처럼 결과를 첫 번째 배열의 앞부분에 저장하면 별도 결과 컨테이너 없이 처리할 수 있습니다.

주의할 점

예시는 반환한 길이만큼 첫 번째 배열의 앞부분을 교집합 결과로 사용합니다.
중복 원소를 한 번만 반환할지, 등장 횟수만큼 반환할지 정책을 확인해야 합니다.

9. 길이가 N인 배열에서 K번째로 큰 수를 평균 O(N)에 찾는 프로그램을 작성해 보세요.

접근 방법

전체 정렬은 O(N log N)이므로 평균 O(N)인 Quickselect로 필요한 위치만 찾습니다.

최악 시간까지 O(N)을 보장해야 한다면 median-of-medians 같은 pivot 선택 전략이 필요합니다.

핵심 키워드

K-th Largest
Quickselect
Min Heap
Partition

구현 포인트

K번째 큰 수는 오름차순 기준 N-K번째 원소입니다.
Quickselect로 해당 인덱스를 찾습니다.
입력 배열을 복사한 뒤 partition을 반복해 원본 배열은 보존합니다.

구현 예시

#include <bits/stdc++.h>
using namespace std;

int quickSelect(vector<int>& a, int target) {
    int left = 0, right = (int)a.size() - 1;
    while (left <= right) {
  int pivot = a[left + (right - left) / 2];
  int i = left, j = right;
  while (i <= j) {
      while (a[i] < pivot) i++;
      while (a[j] > pivot) j--;
      if (i <= j) swap(a[i++], a[j--]);
  }
  if (target <= j) right = j;
  else if (target >= i) left = i;
  else return a[target];
    }
    return a[target];
}

int kthLargest(const vector<int>& values, int k) {
    if (k < 1 || k > (int)values.size()) throw invalid_argument("k out of range");
    vector<int> a = values;
    return quickSelect(a, (int)a.size() - k);
}

class Main {
    static int kthLargest(int[] values, int k) {
  if (k < 1 || k > values.length) {
      throw new IllegalArgumentException("k out of range");
  }
  int[] a = values.clone();
  return quickSelect(a, a.length - k);
    }

    static int quickSelect(int[] a, int target) {
  int left = 0, right = a.length - 1;
  while (left <= right) {
      int pivot = a[left + (right - left) / 2];
      int i = left, j = right;
      while (i <= j) {
          while (a[i] < pivot) i++;
          while (a[j] > pivot) j--;
          if (i <= j) {
              int temp = a[i]; a[i++] = a[j]; a[j--] = temp;
          }
      }
      if (target <= j) right = j;
      else if (target >= i) left = i;
      else return a[target];
  }
  return a[target];
    }
}

def quick_select(arr, target):
    left, right = 0, len(arr) - 1
    while left <= right:
        pivot = arr[left + (right - left) // 2]
        i, j = left, right
        while i <= j:
            while arr[i] < pivot:
                i += 1
            while arr[j] > pivot:
                j -= 1
            if i <= j:
                arr[i], arr[j] = arr[j], arr[i]
                i += 1
                j -= 1
        if target <= j:
            right = j
        elif target >= i:
            left = i
        else:
            return arr[target]
    return arr[target]

def kth_largest(values, k):
    if not 1 <= k <= len(values):
        raise ValueError("k out of range")
    copied = values[:]
    return quick_select(copied, len(copied) - k)

복잡도

Quickselect 평균 O(N), 최악 O(N^2)
예시는 원본 보존을 위해 추가 공간 O(N)을 사용합니다.

주의할 점

K는 1부터 N까지의 1-based 값으로 검증합니다.
중복 값 처리 기준을 확인해야 합니다.
일반적인 Quickselect는 최악 O(N^2)이므로 평균 시간 조건임을 명시해야 합니다.

10. 범위가 주어졌을 때 랜덤 함수를 사용하지 않고, 20개의 수를 랜덤으로 추첨해주는 프로그램을 작성해 보세요. (Hint: 시간)

접근 방법

진짜 난수는 아니지만 시간 값을 seed처럼 사용해 pseudo-random 값을 만들 수 있습니다.

예를 들어 현재 시간의 나노초나 밀리초를 기반으로 선형 합동 생성기(LCG)를 구현할 수 있습니다.

핵심 키워드

Pseudo Random
Seed
Time
LCG
Range Mapping

구현 포인트

현재 시간 값을 seed로 잡습니다.
seed = (a * seed + c) % m 형태로 다음 값을 만듭니다.
범위는 min + seed % (max - min + 1)로 맞춥니다.
중복 없이 뽑아야 한다면 이미 뽑은 값 확인이 필요합니다.

구현 예시

#include <bits/stdc++.h>
using namespace std;

vector<int> pick20(int low, int high) {
    if (low > high) throw invalid_argument("low must not exceed high");
    const uint64_t width = static_cast<uint64_t>(static_cast<int64_t>(high) - low) + 1;
    uint64_t seed = static_cast<uint64_t>(
  chrono::high_resolution_clock::now().time_since_epoch().count()
    );
    vector<int> result;
    for (int i = 0; i < 20; i++) {
  seed = seed * 6364136223846793005ULL + 1442695040888963407ULL;
  int64_t value = static_cast<int64_t>(low) + static_cast<int64_t>(seed % width);
  result.push_back(static_cast<int>(value));
    }
    return result;
}

import java.util.*;

class Main {
    static List<Integer> pick20(int low, int high) {
  if (low > high) throw new IllegalArgumentException("low must not exceed high");
  long width = (long) high - low + 1;
  long seed = System.nanoTime();
  List<Integer> result = new ArrayList<>();

  for (int i = 0; i < 20; i++) {
      seed = seed * 6364136223846793005L + 1442695040888963407L;
      long offset = Long.remainderUnsigned(seed, width);
      result.add((int) ((long) low + offset));
  }
  return result;
    }
}

import time

def pick_20(low, high):
    if low > high:
        raise ValueError("low must not exceed high")
    width = high - low + 1
    if width > 1 << 64:
        raise ValueError("range is too wide")
    seed = time.time_ns()
    result = []

    for _ in range(20):
        seed = (seed * 6364136223846793005 + 1442695040888963407) & ((1 << 64) - 1)
        result.append(low + seed % width)

    return result

복잡도

중복 허용: O(20)
중복 불허: 범위가 충분히 크면 평균 O(20), 범위가 작으면 재시도 비용 증가

주의할 점

보안적으로 안전한 난수가 아닙니다.
범위가 20개보다 작고 중복 불허라면 불가능합니다.

11. 2,000,000 자리의 숫자 여러개가 있고, 이 숫자들을 모두 더해야 한다고 합니다. 어떻게 코드를 작성하면 좋을까요?

접근 방법

기본 정수 타입 범위를 넘으므로 문자열 기반 큰 수 덧셈을 구현합니다.

모든 입력 문자열의 가장 오른쪽 자리부터 같은 자릿값을 한 번에 더하면서 carry를 관리하면 여러 수를 중간 결과 문자열 없이 한 번에 합산할 수 있습니다.

핵심 키워드

Big Integer
String Addition
Carry
Digit
Reverse

구현 포인트

각 숫자를 문자열로 입력받습니다.
가장 긴 입력의 길이를 기준으로 오른쪽부터 각 문자열의 같은 자릿값을 더합니다.
합이 10 이상이면 carry를 다음 자리로 넘깁니다.
각 자리의 합과 carry를 기록하고 마지막에 결과를 뒤집습니다.

구현 예시

#include <bits/stdc++.h>
using namespace std;

string addBigNumbers(const vector<string>& numbers) {
    size_t maxLength = 0;
    for (const string& number : numbers) {
  if (number.empty() || !all_of(number.begin(), number.end(), [](unsigned char ch) {
      return ch >= '0' && ch <= '9';
  })) {
      throw invalid_argument("numbers must contain decimal digits only");
  }
  maxLength = max(maxLength, number.size());
    }

    if (maxLength == 0) return "0";
    vector<long long> columns(maxLength, 0);
    for (const string& number : numbers) {
  for (size_t offset = 0; offset < number.size(); offset++) {
      columns[offset] += number[number.size() - 1 - offset] - '0';
  }
    }

    string reversed;
    long long carry = 0;
    for (long long column : columns) {
  long long total = column + carry;
  reversed += char('0' + total % 10);
  carry = total / 10;
    }
    while (carry > 0) {
  reversed += char('0' + carry % 10);
  carry /= 10;
    }
    reverse(reversed.begin(), reversed.end());
    size_t first = reversed.find_first_not_of('0');
    return first == string::npos ? "0" : reversed.substr(first);
}

import java.util.*;

class Main {
    static String addBigNumbers(List<String> numbers) {
  int maxLength = 0;
  for (String number : numbers) {
      if (number.isEmpty() || !number.chars().allMatch(ch -> ch >= '0' && ch <= '9')) {
          throw new IllegalArgumentException("numbers must contain decimal digits only");
      }
      maxLength = Math.max(maxLength, number.length());
  }

  if (maxLength == 0) return "0";
  long[] columns = new long[maxLength];
  for (String number : numbers) {
      for (int offset = 0; offset < number.length(); offset++) {
          columns[offset] += number.charAt(number.length() - 1 - offset) - '0';
      }
  }

  StringBuilder reversed = new StringBuilder();
  long carry = 0;
  for (long column : columns) {
      long total = column + carry;
      reversed.append(total % 10);
      carry = total / 10;
  }
  while (carry > 0) {
      reversed.append(carry % 10);
      carry /= 10;
  }

  String value = reversed.reverse().toString();
  int first = 0;
  while (first < value.length() - 1 && value.charAt(first) == '0') first++;
  return value.substring(first);
    }
}

def add_big_numbers(numbers):
    for number in numbers:
        if not number or not all("0" <= digit <= "9" for digit in number):
            raise ValueError("numbers must contain decimal digits only")

    max_length = max((len(number) for number in numbers), default=0)
    if max_length == 0:
        return "0"

    columns = [0] * max_length
    for number in numbers:
        for offset, digit in enumerate(reversed(number)):
            columns[offset] += ord(digit) - ord("0")

    result = []
    carry = 0
    for column in columns:
        total = column + carry
        result.append(str(total % 10))
        carry = total // 10
    while carry:
        result.append(str(carry % 10))
        carry //= 10

    return "".join(reversed(result)).lstrip("0") or "0"

복잡도

전체 자릿수를 D라고 하면 시간 O(D), 결과 공간 O(D)

주의할 점

앞자리 0 처리, 음수 여부, 입력 숫자 개수를 확인해야 합니다.

12. 정렬된 두 LinkedList를 합쳐 하나의 정렬된 LinkedList로 만드는 코드를 작성해 보세요.

접근 방법

두 리스트의 head를 비교하면서 작은 노드를 결과 리스트에 붙입니다.

dummy head를 사용하면 head 처리 분기가 단순해집니다.

핵심 키워드

LinkedList
Merge
Two Pointers
Dummy Node

구현 포인트

p1, p2, tail 포인터를 둡니다.
더 작은 값을 가진 노드를 tail.next에 연결합니다.
한쪽이 끝나면 남은 리스트를 그대로 붙입니다.

구현 예시

struct Node {
    int value;
    Node* next;
    Node(int v) : value(v), next(nullptr) {}
};

Node* merge(Node* a, Node* b) {
    Node dummy(0);
    Node* tail = &dummy;

    while (a && b) {
  if (a->value <= b->value) {
      tail->next = a;
      a = a->next;
  } else {
      tail->next = b;
      b = b->next;
  }
  tail = tail->next;
    }
    tail->next = a ? a : b;
    return dummy.next;
}

class Node {
    int value;
    Node next;
    Node(int value) { this.value = value; }
}

class Main {
    static Node merge(Node a, Node b) {
  Node dummy = new Node(0);
  Node tail = dummy;

  while (a != null && b != null) {
      if (a.value <= b.value) {
          tail.next = a;
          a = a.next;
      } else {
          tail.next = b;
          b = b.next;
      }
      tail = tail.next;
  }
  tail.next = (a != null) ? a : b;
  return dummy.next;
    }
}

class Node:
    def __init__(self, value):
        self.value = value
        self.next = None

def merge(a, b):
    dummy = Node(0)
    tail = dummy

    while a and b:
        if a.value <= b.value:
            tail.next = a
            a = a.next
        else:
            tail.next = b
            b = b.next
        tail = tail.next

    tail.next = a if a else b
    return dummy.next

복잡도

시간 O(N + M)
추가 공간 O(1) 또는 새 노드 생성 시 O(N + M)

주의할 점

기존 노드를 재사용할지 새 노드를 만들지 면접관에게 확인하면 좋습니다.

13. 어떤 수가 주어졌을 때, 이 수의 소인수를 모두 구하는 코드를 작성해 보세요.

접근 방법

2부터 sqrt(N)까지 나누어떨어지는 수를 찾고, 나누어떨어지는 동안 계속 나눕니다.

마지막에 남은 수가 1보다 크면 그 수도 소인수입니다.

핵심 키워드

Prime Factorization
sqrt(N)
Trial Division
Remainder

구현 포인트

먼저 2로 나누고, 이후 홀수만 검사하면 조금 최적화됩니다.
정수 overflow를 피하기 위해 i <= n / i 조건으로 반복합니다.
나누어떨어질 때마다 결과에 추가하고 n /= i를 수행합니다.

구현 예시

#include <bits/stdc++.h>
using namespace std;

vector<long long> primeFactors(long long n) {
    vector<long long> result;
    if (n < 2) return result;
    for (long long d = 2; d <= n / d; d++) {
  while (n % d == 0) {
      result.push_back(d);
      n /= d;
  }
    }
    if (n > 1) result.push_back(n);
    return result;
}

import java.util.*;

class Main {
    static List<Long> primeFactors(long n) {
  List<Long> result = new ArrayList<>();
  if (n < 2) return result;
  for (long d = 2; d <= n / d; d++) {
      while (n % d == 0) {
          result.add(d);
          n /= d;
      }
  }
  if (n > 1) result.add(n);
  return result;
    }
}

def prime_factors(n):
    result = []
    if n < 2:
        return result
    d = 2
    while d <= n // d:
        while n % d == 0:
            result.append(d)
            n //= d
        d += 1
    if n > 1:
        result.append(n)
    return result

복잡도

기본 trial division은 O(sqrt(N))

주의할 점

i * i가 overflow될 수 있는 언어에서는 i <= n / i 조건이 안전합니다.

14. 1 부터 1,000,000 까지의 수를 이어 붙인다고 가정할 때, 이 수에서 0이 몇 번이나 등장하는지 확인하는 코드를 작성해 보세요.

접근 방법

단순하게는 1부터 1,000,000까지 문자열로 바꿔 0을 세면 됩니다.

범위가 고정되어 있고 100만 정도라면 충분히 가능합니다.

더 수학적으로는 자리수별 0의 등장 횟수를 계산할 수도 있습니다.

핵심 키워드

Counting
Digit
String Conversion
Positional Counting

구현 포인트

쉬운 구현: 반복문으로 String.valueOf(i) 후 문자 0 개수를 셉니다.
수학적 구현: 각 자리수별로 high/current/low 값을 나눠 0 등장 횟수를 계산합니다.

구현 예시

#include <bits/stdc++.h>
using namespace std;

long long countZero(int n) {
    long long count = 0;
    for (int x = 1; x <= n; x++) {
  int value = x;
  while (value > 0) {
      if (value % 10 == 0) count++;
      value /= 10;
  }
    }
    return count;
}

class Main {
    static long countZero(int n) {
  long count = 0;
  for (int x = 1; x <= n; x++) {
      int value = x;
      while (value > 0) {
          if (value % 10 == 0) count++;
          value /= 10;
      }
  }
  return count;
    }
}

def count_zero(n):
    count = 0
    for x in range(1, n + 1):
        value = x
        while value > 0:
            if value % 10 == 0:
                count += 1
            value //= 10
    return count

복잡도

문자열 방식: 전체 자릿수만큼 O(D), 여기서는 충분히 작습니다.
수학적 방식: 자리수 개수만큼 O(log N)

주의할 점

0 자체를 포함하는 범위인지 확인해야 합니다. 현재는 1부터라 숫자 0은 포함하지 않습니다.

15. 스택 두개로 큐를, 큐 두개로 스택을 구현하는 코드를 작성해 보세요.

접근 방법

스택 두 개로 큐를 만들 때는 입력 스택과 출력 스택을 나눕니다.

enqueue는 입력 스택에 넣고, dequeue는 출력 스택이 비었을 때 입력 스택의 모든 원소를 옮긴 뒤 꺼냅니다.

큐 두 개로 스택을 만들 때는 push를 비싸게 만들거나 pop을 비싸게 만들 수 있습니다.

push 비싼 방식은 새 원소를 빈 큐에 넣고 기존 큐 원소를 뒤에 붙여 front가 항상 top이 되게 합니다.

핵심 키워드

Stack
Queue
LIFO
FIFO
Amortized O(1)

구현 포인트

스택 2개 큐:
- inStack에 push
- dequeue 시 outStack이 비어 있으면 inStack을 모두 옮김
- outStack.pop() 반환
큐 2개 스택:
- push 시 새 원소를 보조 큐에 넣고 기존 큐를 모두 옮김
- 두 큐를 swap
- pop은 메인 큐에서 poll

구현 예시

#include <bits/stdc++.h>
using namespace std;

class QueueByStacks {
    stack<int> in, out;
    void move() {
  if (out.empty()) {
      while (!in.empty()) {
          out.push(in.top());
          in.pop();
      }
  }
    }
public:
    void offer(int x) { in.push(x); }
    int poll() {
  move();
  if (out.empty()) throw underflow_error("queue is empty");
  int value = out.top();
  out.pop();
  return value;
    }
};

class StackByQueues {
    queue<int> primary, helper;
public:
    void push(int x) {
  helper.push(x);
  while (!primary.empty()) {
      helper.push(primary.front());
      primary.pop();
  }
  swap(primary, helper);
    }
    int pop() {
  if (primary.empty()) throw underflow_error("stack is empty");
  int value = primary.front();
  primary.pop();
  return value;
    }
};

import java.util.*;

class QueueByStacks {
    private final Deque<Integer> in = new ArrayDeque<>();
    private final Deque<Integer> out = new ArrayDeque<>();

    void offer(int x) { in.push(x); }

    int poll() {
  if (out.isEmpty()) {
      while (!in.isEmpty()) out.push(in.pop());
  }
  if (out.isEmpty()) throw new NoSuchElementException("queue is empty");
  return out.pop();
    }
}

class StackByQueues {
    private Deque<Integer> primary = new ArrayDeque<>();
    private Deque<Integer> helper = new ArrayDeque<>();

    void push(int x) {
  helper.offer(x);
  while (!primary.isEmpty()) helper.offer(primary.poll());
  Deque<Integer> temp = primary;
  primary = helper;
  helper = temp;
    }

    int pop() {
  if (primary.isEmpty()) throw new NoSuchElementException("stack is empty");
  return primary.remove();
    }
}

from collections import deque

class QueueByStacks:
    def __init__(self):
        self.in_stack = []
        self.out_stack = []

    def offer(self, x):
        self.in_stack.append(x)

    def poll(self):
        if not self.out_stack:
            while self.in_stack:
                self.out_stack.append(self.in_stack.pop())
        if not self.out_stack:
            raise IndexError("queue is empty")
        return self.out_stack.pop()

class StackByQueues:
    def __init__(self):
        self.primary = deque()
        self.helper = deque()

    def push(self, x):
        self.helper.append(x)
        while self.primary:
            self.helper.append(self.primary.popleft())
        self.primary, self.helper = self.helper, self.primary

    def pop(self):
        if not self.primary:
            raise IndexError("stack is empty")
        return self.primary.popleft()

복잡도

스택 2개 큐: enqueue O(1), dequeue amortized O(1)
큐 2개 스택: 구현 방식에 따라 push 또는 pop이 O(N)

주의할 점

amortized 시간복잡도와 worst-case 시간복잡도를 구분해서 설명해야 합니다.

16. 정수 키와 값을 저장하는 고정 용량 LRU Cache를 평균 O(1)의 get, put으로 구현해 보세요.

접근 방법

해시맵으로 키의 노드를 평균 O(1)에 찾고 이중 연결 리스트로 최근 사용 순서를 관리합니다.

조회하거나 갱신한 노드를 리스트 앞으로 옮기고, 새 항목 추가 후 용량을 넘으면 가장 오래 사용하지 않은 마지막 노드를 맵과 리스트에서 함께 제거합니다.

핵심 키워드

LRU
HashMap
Doubly Linked List
Sentinel Node
Eviction

구현 포인트

연결 리스트를 직접 구현한다면 head와 tail sentinel로 경계 분기를 줄입니다.
get도 사용으로 간주해 노드를 앞으로 옮깁니다.
기존 키의 put은 크기를 늘리지 않고 값과 순서만 갱신합니다.
용량은 양수인지 검증합니다.

구현 예시

#include <cstddef>
#include <iterator>
#include <list>
#include <optional>
#include <stdexcept>
#include <unordered_map>
#include <utility>

class LRUCache {
    using Entry = std::pair<int, int>;
    std::size_t capacity;
    std::list<Entry> order;
    std::unordered_map<int, std::list<Entry>::iterator> byKey;
public:
    explicit LRUCache(std::ptrdiff_t requestedCapacity) {
  if (requestedCapacity <= 0) throw std::invalid_argument("capacity must be positive");
  capacity = static_cast<std::size_t>(requestedCapacity);
    }
    std::optional<int> get(int key) {
  auto found = byKey.find(key);
  if (found == byKey.end()) return std::nullopt;
  order.splice(order.begin(), order, found->second);
  return found->second->second;
    }
    void put(int key, int value) {
  auto found = byKey.find(key);
  if (found != byKey.end()) {
      found->second->second = value;
      order.splice(order.begin(), order, found->second);
      return;
  }
  order.emplace_front(key, value);
  byKey[key] = order.begin();
  if (byKey.size() > capacity) {
      auto leastRecent = std::prev(order.end());
      byKey.erase(leastRecent->first);
      order.pop_back();
  }
    }
};

import java.util.*;

class LRUCache {
    private static final class Node {
  final int key;
  int value;
  Node prev, next;
  Node(int key, int value) { this.key = key; this.value = value; }
    }
    private final int capacity;
    private final Map<Integer, Node> byKey = new HashMap<>();
    private final Node head = new Node(0, 0);
    private final Node tail = new Node(0, 0);

    LRUCache(int capacity) {
  if (capacity <= 0) throw new IllegalArgumentException("capacity must be positive");
  this.capacity = capacity;
  head.next = tail;
  tail.prev = head;
    }
    OptionalInt get(int key) {
  Node node = byKey.get(key);
  if (node == null) return OptionalInt.empty();
  moveToFront(node);
  return OptionalInt.of(node.value);
    }
    void put(int key, int value) {
  Node node = byKey.get(key);
  if (node != null) { node.value = value; moveToFront(node); return; }
  Node added = new Node(key, value);
  byKey.put(key, added);
  addAfterHead(added);
  if (byKey.size() > capacity) {
      Node leastRecent = tail.prev;
      unlink(leastRecent);
      byKey.remove(leastRecent.key);
  }
    }
    private void moveToFront(Node node) { unlink(node); addAfterHead(node); }
    private void addAfterHead(Node node) {
  node.prev = head; node.next = head.next;
  head.next.prev = node; head.next = node;
    }
    private void unlink(Node node) { node.prev.next = node.next; node.next.prev = node.prev; }
}

class _Node:
    def __init__(self, key=0, value=0):
        self.key, self.value = key, value
        self.prev = self.next = None

class LRUCache:
    def __init__(self, capacity):
        if capacity <= 0:
            raise ValueError("capacity must be positive")
        self.capacity = capacity
        self.by_key = {}
        self.head, self.tail = _Node(), _Node()
        self.head.next, self.tail.prev = self.tail, self.head

    def get(self, key):
        node = self.by_key.get(key)
        if node is None:
            return None
        self._move_to_front(node)
        return node.value

    def put(self, key, value):
        node = self.by_key.get(key)
        if node is not None:
            node.value = value
            self._move_to_front(node)
            return
        added = _Node(key, value)
        self.by_key[key] = added
        self._add_after_head(added)
        if len(self.by_key) > self.capacity:
            least_recent = self.tail.prev
            self._unlink(least_recent)
            del self.by_key[least_recent.key]

    def _move_to_front(self, node):
        self._unlink(node)
        self._add_after_head(node)

    def _add_after_head(self, node):
        node.prev, node.next = self.head, self.head.next
        self.head.next.prev = node
        self.head.next = node

    @staticmethod
    def _unlink(node):
        node.prev.next, node.next.prev = node.next, node.prev

복잡도

get, put: 평균 O(1)
공간: O(capacity)

주의할 점

해시맵과 연결 리스트에서 반드시 같은 노드를 제거해야 합니다.
부재를 실제 저장값과 충돌하는 magic number로 표현하지 않습니다.

17. 문자열에서 중복 문자가 없는 가장 긴 부분 문자열의 길이를 O(N)에 구해 보세요.

접근 방법

슬라이딩 윈도우의 왼쪽·오른쪽 경계와 각 문자의 마지막 등장 위치를 관리합니다.

현재 윈도우 안에서 중복을 만나면 왼쪽 경계를 이전 위치 다음으로 옮기되, 왼쪽 경계가 뒤로 이동하지 않도록 합니다.

핵심 키워드

Sliding Window
Two Pointers
Last Seen Index
HashMap
Unicode Code Point

구현 포인트

이전 위치가 현재 left 이상일 때만 경계를 갱신합니다.
각 위치에서 right - left + 1로 길이를 계산합니다.
빈 문자열은 0을 반환합니다.

구현 예시

#include <algorithm>
#include <cstddef>
#include <string>
#include <unordered_map>

std::size_t longestUniqueSubstring(const std::u32string& text) {
    std::unordered_map<char32_t, std::size_t> lastSeen;
    std::size_t left = 0, best = 0;
    for (std::size_t right = 0; right < text.size(); ++right) {
  char32_t ch = text[right];
  auto found = lastSeen.find(ch);
  if (found != lastSeen.end() && found->second >= left) left = found->second + 1;
  lastSeen[ch] = right;
  best = std::max(best, right - left + 1);
    }
    return best;
}

import java.util.*;

class LongestUniqueSubstring {
    static int length(String text) {
  Map<Integer, Integer> lastSeen = new HashMap<>();
  PrimitiveIterator.OfInt iterator = text.codePoints().iterator();
  int left = 0, right = 0, best = 0;
  while (iterator.hasNext()) {
      int codePoint = iterator.nextInt();
      Integer previous = lastSeen.put(codePoint, right);
      if (previous != null && previous >= left) left = previous + 1;
      best = Math.max(best, right - left + 1);
      right++;
  }
  return best;
    }
}

def longest_unique_substring(text):
    last_seen = {}
    left = best = 0
    for right, char in enumerate(text):
        previous = last_seen.get(char)
        if previous is not None and previous >= left:
            left = previous + 1
        last_seen[char] = right
        best = max(best, right - left + 1)
    return best

복잡도

시간: O(N)
공간: O(min(N, U)), U는 문자 집합 크기

주의할 점

C++ 예시는 Unicode code point로 디코딩된 u32string을 입력받습니다.
사용자에게 보이는 grapheme cluster와 Unicode code point는 다를 수 있습니다.

18. 여러 개의 닫힌 구간 [start, end]가 주어졌을 때 겹치는 구간을 모두 병합해 보세요.

접근 방법

구간을 시작점과 종료점 순으로 정렬한 뒤 현재 시작점이 마지막 병합 구간의 종료점 이하라면 종료점을 확장합니다.

겹치지 않으면 새 구간을 결과에 추가합니다. 예시는 입력 원본을 바꾸지 않도록 복사본을 정렬합니다.

핵심 키워드

Interval
Sorting
Greedy
Sweep
Closed Interval

구현 포인트

각 구간이 start <= end인지 검증합니다.
닫힌 구간이므로 [1,4]와 [4,5]는 병합합니다.
빈 입력은 빈 결과를 반환합니다.

구현 예시

#include <algorithm>
#include <stdexcept>
#include <utility>
#include <vector>

using Interval = std::pair<long long, long long>;

std::vector<Interval> mergeIntervals(std::vector<Interval> intervals) {
    for (const auto& interval : intervals) {
  if (interval.first > interval.second) throw std::invalid_argument("invalid interval");
    }
    std::sort(intervals.begin(), intervals.end());
    std::vector<Interval> merged;
    for (const auto& current : intervals) {
  if (merged.empty() || current.first > merged.back().second) merged.push_back(current);
  else merged.back().second = std::max(merged.back().second, current.second);
    }
    return merged;
}

import java.util.*;

class IntervalMerger {
    static long[][] merge(long[][] intervals) {
  long[][] copy = new long[intervals.length][];
  for (int i = 0; i < intervals.length; i++) {
      if (intervals[i] == null || intervals[i].length != 2 || intervals[i][0] > intervals[i][1]) {
          throw new IllegalArgumentException("invalid interval");
      }
      copy[i] = intervals[i].clone();
  }
  Arrays.sort(copy, Comparator.comparingLong((long[] value) -> value[0]).thenComparingLong(value -> value[1]));
  List<long[]> merged = new ArrayList<>();
  for (long[] current : copy) {
      if (merged.isEmpty() || current[0] > merged.get(merged.size() - 1)[1]) merged.add(current.clone());
      else {
          long[] last = merged.get(merged.size() - 1);
          last[1] = Math.max(last[1], current[1]);
      }
  }
  return merged.toArray(new long[merged.size()][]);
    }
}

def merge_intervals(intervals):
    normalized = []
    for interval in intervals:
        if len(interval) != 2 or interval[0] > interval[1]:
            raise ValueError("invalid interval")
        normalized.append((interval[0], interval[1]))
    normalized.sort()
    merged = []
    for start, end in normalized:
        if not merged or start > merged[-1][1]:
            merged.append([start, end])
        else:
            merged[-1][1] = max(merged[-1][1], end)
    return [tuple(interval) for interval in merged]

복잡도

정렬: O(N log N)
병합: O(N)
입력 복사와 결과 공간: O(N)

주의할 점

반열린 구간에서는 경계가 같은 구간의 병합 정책이 달라질 수 있습니다.
결과가 입력 객체를 공유해 호출자의 원본을 바꾸지 않도록 주의합니다.