구글 코딩 인터뷰 문제 풀이: 원형 시계 최소 시간 차를 비둘기집 원리로 O(1) 최적화하기

핵심 메시지

• 영상은 한 유튜버가 마이크로소프트 수석(프린시펄) 엔지니어에게 실제 구글 코딩 인터뷰 문제를 내고 푸는 과정을 보여준다. 발표자는 구글 합격률이 1% 미만이라 통계적으로 MIT 입학보다 어렵다고 말한다.
• 문제는 'HH:MM 형식의 24시간 시각 목록이 주어질 때, 임의의 두 시각 사이의 최소 분(分) 차이를 반환하라'이며, 시계는 자정을 넘어 이어지는 '원형'으로 다뤄야 한다. 예: [23:59, 00:00]은 1, [00:00, 23:59, 00:00]은 중복이 있어 0이다.
• 엔지니어는 시각을 정렬한 뒤 인접한 두 시각만 비교한다. 문자열은 ASCII 순으로 정렬되므로 HH:MM 문자열을 굳이 분으로 바꾸지 않아도 시간순으로 정렬된다는 점을 활용한다.
• 원형 차이는 '앞으로 가는 거리'와 '하루(24*60분)를 돌아 뒤로 가는 거리' 중 작은 값으로 계산하고, 코드를 모듈화하기 위해 시각→분 변환과 두 시각의 델타를 구하는 헬퍼 함수를 따로 만든다.
• 핵심 통찰은 비둘기집 원리다. 하루의 분은 24*60=1440개뿐이라, 입력 길이가 1440을 넘으면 반드시 중복이 있어 즉시 0을 반환할 수 있다. 그래서 정렬 대상은 항상 1440개 이하로 묶이고, 입력이 아무리 커져도 작업량이 하루의 분 수로 상한이 잡혀 점근적으로 O(1) 시간·공간이 된다.

쉽게 이해하기

발표자는 구글 합격률이 1% 미만이라 통계적으로 MIT에 들어가기보다 어렵다고 운을 떼며, 실제 구글 코딩 인터뷰 문제를 마이크로소프트 수석 엔지니어에게 던진다. 그는 수석이 시니어보다 한 단계 위 직급이고 직접 많은 엔지니어를 면접해 왔다며, 면접관이 후보를 평가할 때 보는 포인트에도 주목하라고 안내한다. 문제는 'HH:MM 형식의 24시간 시각들이 주어질 때 임의의 두 시각 사이 최소 분 차이를 구하라'이고, [23:59, 00:00]은 1분, 자정이 두 번 들어간 목록은 중복이라 0을 반환해야 한다는 두 예시로 명확히 한다.

엔지니어는 먼저 질문을 던지며 조건을 확정한다. 모두 군용(24시간) 표기라 오전·오후 구분이 없고, 하루를 넘기는 게 아니라 하나의 '원형 시계' 위에서 도는 구조이며, 배열에는 최소 두 개의 원소가 보장되고 입력 형식은 항상 올바르다는 점을 확인한다. 그는 가장 가까운 두 시각은 정렬했을 때 인접한 두 점 사이에 있을 수밖에 없다고 보고 정렬로 접근한다. 이때 문자열이 ASCII 값 기준으로 정렬되기 때문에, '0'으로 시작하는 값이 먼저 오는 성질을 이용하면 HH:MM 문자열 배열을 분으로 변환하지 않고 정렬해도 자연스럽게 시간순이 된다는 점을 활용한다.

그는 코드를 깔끔하게 유지하려 두 개의 헬퍼 함수를 만든다. 하나는 ':'로 나눠 시와 분을 뽑아 '시*60+분'으로 바꾸는 변환 함수이고, 다른 하나는 두 시각의 차이를 구하는 함수다. 단순히 큰 값에서 작은 값을 빼면 되지만, 원형이기 때문에 23:59와 00:00처럼 하루 경계를 가로지르는 경우를 놓친다. 그래서 '앞으로 빼는 차이'와 '하루 전체(24*60)에서 큰 시각을 빼고 작은 시각을 더해 거꾸로 도는 차이' 두 가지를 모두 계산해 더 작은 값을 취하고, 계산 전 두 시각의 대소를 맞춰 스왑한다. 본 루프에서는 각 시각을 바로 앞 시각과 비교하되, 파이썬에서 인덱스 -1이 배열의 끝을 가리키는 성질을 이용해 첫 원소를 배열의 마지막과 비교함으로써 원형을 자연스럽게 처리한다.

정렬이 O(n log n), 순회가 O(n)이라 전체는 O(n log n) 시간이고, 파이썬 정렬이 제자리(in-place)이므로 공간은 O(1)이라고 분석한다. 면접관이 더 효율적으로 만들 수 있냐고 묻자 그는 비둘기집 원리를 꺼낸다. 하루에는 1440분(24*60)밖에 없으므로 입력 배열의 길이가 1440을 넘으면 반드시 중복이 존재하고, 그때는 정렬할 것도 없이 곧장 0을 반환할 수 있다. 따라서 실제 정렬은 언제나 1440개 이하에서만 일어나 정렬 비용이 입력 크기와 무관해지고, 입력이 10억 개여도 같은 양의 일만 하므로 점근적으로 시간·공간 모두 O(1)이 된다고 결론짓는다.

그는 같은 발상을 쓰는 O(n) 대안도 제시한다. 하루의 분 수만큼(1440) 불리언 배열을 만들어 각 인덱스를 '그 분이 등장했는지' 표시하고, 만드는 도중 이미 true인 칸을 다시 true로 바꾸려 하면 중복이므로 곧바로 0을 반환한다. 이후 배열을 훑어 첫 시각과 마지막 시각을 기억해 두고, 원형이므로 마지막에서 첫 시각으로 돌아가는 경계 차이까지 따로 확인한다. 이 방식은 보조 배열 크기가 1440으로 고정돼 공간은 O(1)이지만, 입력의 모든 시각을 훑어야 하므로 시간은 O(n)이다. 마지막에 그는 정렬되지 않은 입력으로도 테스트하고, 역으로 면접관에게 성장·멘토십 기회를 되묻는 것으로 인터뷰를 마무리한다.

주요 인사이트

• 원형(순환) 구조의 거리 문제는 '앞으로 가는 거리'와 '한 바퀴를 돌아 뒤로 가는 거리'를 모두 계산해 더 작은 값을 취하는 것이 정석이다. 단순 뺄셈만 하면 경계를 넘는 가장 가까운 쌍을 놓친다.
• 정렬은 늘 비싼 단계가 아니다. 값의 범위가 유한하면(여기선 하루 1440분) 비둘기집 원리로 '입력이 범위보다 길면 중복 확정'이라는 지름길을 만들어, 정렬 비용을 입력 크기와 분리해 점근적으로 상수로 만들 수 있다.
• HH:MM처럼 자리수가 고정된 문자열은 ASCII 사전식 정렬이 곧 시간순 정렬과 일치한다. 변환 없이 정렬할 수 있는 이런 성질을 알아채면 코드가 간결해진다.
• 헬퍼 함수로 '시각→분 변환'과 '두 시각 델타'를 분리해 두면 첫 번째 풀이와 두 번째 풀이에서 그대로 재사용할 수 있다. 모듈화는 가독성뿐 아니라 다른 접근으로 확장할 때의 비용도 줄인다.
• 면접관이 보는 것은 정답 자체보다 사고 과정이다. 조건을 되묻고, 시간·공간 복잡도를 스스로 분석하고, 예시·엣지 케이스로 검증하며, 사소한 실수를 차분히 고치는 태도가 평가의 핵심이다.

자주 묻는 질문

관련 AI 소식