2025 NC soft 신입공채 게임 프로그래머 채용 코딩테스트 후기

20251025

엔씨소프트 코딩테스트가 있었다. 프로그래머스 사이트로 시험이 진행되었고 총 3문제 120분이 주어졌다. 문제의 난이도는 크게 어렵지 않았다. 1,2번은 간단한 구현 문제여서 문제만 잘 읽고 그대로 표현하면 되는 문제였다.

진짜 문제는 3번이었다.

 

주어진 벡터의 원소들이 각각 무한히 뻗어가는 배수열을 가질 때,
그 전체 수열에서 k번째로 작은 수를 구하는 문제와 비슷하였다.

처음 문제를 읽었을 때는 “이건 간단하겠는데?” 싶었다.
배수들을 전부 나열해서 정렬한 다음, k번째 원소를 찾으면 되겠다고 생각했다.
하지만 곧바로 그 방식은 TLE(Time Limit Exceeded) 이 날 수밖에 없다는 걸 깨달았다.
왜냐하면 각 원소의 배수열이 무한히 이어지기 때문에
모든 수를 직접 생성하고 정렬하는 건 불가능한 접근이었기 때문이다.

그때부터 본격적으로 “이걸 어떻게 유한하게 줄일 수 있을까?”라는 고민이 시작됐다.

---

첫 시도: 이분 탐색

평소처럼 “k번째 원소를 찾는 문제”를 보고 k의 범위가 아주 큰 값이면 자연스럽게 이분 탐색이 떠오른다.
범위를 잡고 mid 이하의 원소 개수를 세서 조정하면 되겠지 했다.

그런데 금방 벽에 부딪혔다.
배수들이 서로 겹치기 때문에 단순히 “<= mid”인 값의 개수를 정확히 셀 수 없었다.
예를 들어,

• 12는 3×4로도, 4×3으로도 만들어질 수 있다.
  이 중복이 정렬 순서를 교란시켜버리기 때문에,
  이분 탐색으로는 정확한 순서를 구할 수 없었다.

---

사고 전환: 유한한 부분으로 줄이기

‘무한히 뻗어가니 답이 없다고 생각했지만,
k번째 작은 수는 어차피 유한한 구간 안에 존재한다.’

예를 들어 {1,2,3,4}에서 k = 29라면,
벡터 크기 n이 4이므로 k보다 큰 4의 배수 중 가장 작은 값은 32다.
즉, 8배수까지만 보면 된다.

그럼 가능한 값들은 다음과 같다:

 

1,2,3,4,5,6,7,8, 2,4,6,8,10,12,14,16, 3,6,9,12,15,18,21,24, 4,8,12,16,20,24,28,32

여기서 정렬하면 29번째 원소는 24가 된다.
즉, 문제는 **무한한 수열이 아니라,
‘k보다 큰 벡터 크기의 배수까지 제한된 부분 문제’**로 축소할 수 있었다.

---

전환점: priority_queue(우선순위 큐)

문제를 다시 바라보다가 문득 priority_queue가 떠올랐다.
‘가장 큰 값들만 관리하면서 하나씩 줄여나가면 되지 않을까?’

그 순간 퍼즐이 맞춰졌다.
각 배수열의 마지막 값(가장 큰 배수)과 어떤 수의 배수인지 알 수 있는 수를 pair 형식으로 힙에 넣고,
가장 큰 수를 하나씩 꺼내며 줄여가면 된다.

예를 들어

 

pq = { {32,4}, {24,3}, {16,2}, {8,1} }

형태로 넣어두면, top은 항상 가장 큰 수(32)가 된다.

1. top을 꺼내서 4를 빼고 다시 넣는다 → {28,4}
2. 다시 top을 꺼내서 4를 빼고 → {24,4}
3. …이 과정을 k번째까지 반복하면,
   마지막으로 꺼낸 값이 곧 k번째로 작은 값이다.

이 방식의 핵심은

• 배수 중복이 자연스럽게 처리되고,
• 항상 최대 n개의 값만 관리하기 때문에
  k가 아무리 커도 O(n log n) 수준의 효율로 해결된다는 점이다.

---

시간복잡도 직관

• n = 벡터 크기
• k = 매우 큰 수 (최대 10⁸ 이상 가능)
• 하지만 힙에는 n개의 원소만 유지되므로,
  각 pop/push가 O(log n), 전체는 O(n log n) 내에 해결 가능하다.

즉,

n이 10,000이고 k가 100,000,000이라도
최대 10,000번만 순회하면 된다.

 예시: k = 29일 때의 과정

 

초기 힙: {32,4}, {24,3}, {16,2}, {8,1} 32번째: top {32,4} → {28,4} 31번째: top {28,4} → {24,4} 30번째: top {24,4} → {20,4}   29번째: top {24,3} → 답 = 24

결과: 24

---

마무리하며

이 문제는 단순한 구현 문제가 아니라,
“무한을 유한으로 바꾸는 사고의 전환”이 필요한 문제였다.

처음엔 단순히 모든 배수를 나열하고 정렬하는 단순한 brute-force 접근이 떠올랐고,
그다음엔 이분 탐색으로 풀 수 있지 않을까 시도했지만 실패했다.
결국 핵심은 정렬을 뒤집어 시뮬레이션하는 우선순위 큐의 관점이었다.

이 경험을 통해 배운 점은 명확하다.

문제를 풀 때는 풀어야 할 데이터의 크기가 아니라,
“진짜 필요한 범위”를 먼저 찾아내야 한다.