[C++] 코딩테스트에서 set과 vector + unique를 제대로 쓰는 법

— STL을 “아는 것”과 “문제에 맞게 쓰는 것”의 차이

코딩 테스트를 풀다 보면 set, unique, lower_bound 같은 STL이 자주 등장한다.

문법 자체는 쉬운데, 왜 써야 하는지와 언제 쓰면 망하는지를 모르고 쓰면 오히려 시간 초과나 논리 버그가 난다.

이 글에서는 정렬 알고리즘 자체(sort, stable_sort)는 배제하고,

코테에서 실제로 가장 많이 쓰이는 다음 구조에 집중한다.

set과 vector + sort + unique를 어떻게 선택하고 사용하는가

---

1️⃣ set의 본질: “정렬된 중복 없는 집합”

std::set은 내부적으로 Red-Black Tree(균형 이진 탐색 트리)를 사용한다.

그래서 다음 속성을 가진다.

• 항상 정렬된 상태 유지
• 중복 허용 ❌
• 삽입 / 삭제 / 탐색 → O(log N)

set<int> s;
s.insert(3);
s.insert(1);
s.insert(2);
s.insert(2);
// 결과: {1, 2, 3}

코테에서 이것이 의미하는 것은 단순하다.

“중복 없는 값들을, 항상 정렬된 상태로 관리해야 한다”

이 조건이 보이면 set이 후보가 된다.

---

set vs multiset

자료구조 의미

set	같은 값은 1개만
multiset	같은 값 여러 개 허용

예:

• 서로 다른 좌표 개수 → set
• 같은 숫자가 여러 번 등장해도 의미 있음 → multiset

---

2️⃣ vector + sort + unique가 set보다 자주 쓰이는 이유

많은 사람들은 “중복 제거”하면 바로 set을 떠올린다.

하지만 코딩 테스트에서는 오히려 이 패턴이 더 자주 쓰인다.

vector<int> v = {3,1,2,2,1,3};
sort(v.begin(), v.end());
v.erase(unique(v.begin(), v.end()), v.end());
// {1,2,3}

왜 이 방식이 빠를까?

• vector는 연속 메모리 → 캐시 효율이 매우 좋음
• set은 트리 → 포인터 이동 많음
• “입력을 다 받은 후 한 번에 처리”하는 문제 구조에 잘 맞음

중간에 삽입/삭제가 거의 없다면

→ set보다 이 패턴이 실제로 더 빠다

---

3️⃣ 왜 sort를 unique보다 먼저 해야 할까?

unique는 모든 중복을 제거하지 않는다.

unique는 “서로 인접한 중복만” 뒤로 밀어버리는 함수다.

예:

vector<int> v = {1, 2, 1, 2, 1};
auto it = unique(v.begin(), v.end());

이 상태에서는

1, 2, 1, 2, 1   // 아무것도 안 사라짐

왜냐하면 같은 값이 서로 떨어져 있기 때문이다.

반면:

sort(v.begin(), v.end());   // 1 1 1 2 2
unique(v.begin(), v.end());

이제 같은 값이 붙어 있으므로 제거가 가능해진다.

sort는 중복을 모으는 역할,

unique는 모여 있는 중복을 하나로 만드는 역할

그래서 순서는 반드시:

sort → unique → erase

---

4️⃣ set이 “k번째 원소”에 약한 이유

set은 내부가 트리이기 때문에 랜덤 접근이 불가능하다.

s.begin() + 5   // ❌ 컴파일 에러

대신:

auto it = s.begin();
advance(it, 5);   // O(N)

이 말은:

k번째 원소를 자주 쓰는 문제라면

set은 구조적으로 잘못된 선택

이런 문제는 정렬된 vector가 맞다.

---

5️⃣ set에서 가장 많이 터지는 버그: Comparator

set은 두 원소 A, B에 대해 다음을 만족하면

같은 원소로 간주한다.

!comp(A,B) && !comp(B,A)

그래서 다음 코드는 절대 쓰면 안 된다.

return a <= b;   // ❌

이렇게 하면:

• a <= a 가 true → 비교 규칙 붕괴
• set 내부 트리가 깨짐
• 원소가 사라지거나 런타임 에러 발생

안전한 비교 함수

if(a.x != b.x) return a.x < b.x;
return a.id < b.id;   // 반드시 고유값으로 tie-break

비교 기준이 여러 개면

마지막에 항상 고유한 값(ID, index)을 넣어야 한다

---

6️⃣ 구조체 정렬의 정석

struct Node {
    int x, y;
    bool operator<(const Node& o) const {
        if(x != o.x) return x < o.x;
        return y < o.y;
    }
};

이렇게 정의하면:

• set<Student>
• sort(vector<Student>)
• priority_queue<Student>

모두에서 동일한 기준으로 작동한다.

코테에서는 이런 방식이 가장 안전하고 유지보수도 쉽다.

여기서 const가 두 번 들어간다.

const Node& o

→ 비교 중에 o를 바꾸지 않겠다는 약속

→ STL 컨테이너는 이를 요구함

뒤의 const

→ this 객체도 바꾸지 않겠다는 의미

→ set과 sort는 내부적으로 const 객체를 비교함

이게 없으면:

error: no viable overloaded '<'

같은 컴파일 에러가 난다.

---

7️⃣ lower_bound와 upper_bound의 진짜 의미

이 두 함수는 정렬된 컨테이너에서만 의미가 있다.

(vector, set, multiset 모두 가능)

정의

lower_bound(x)  →  x 이상(>= x)인 첫 위치
upper_bound(x)  →  x 초과(> x)인 첫 위치

예시:

v = {1, 2, 2, 2, 4, 5}

x lower_bound(x) upper_bound(x)

2	첫 번째 2	4
3	4	4
0	1	1
6	end()	end()

---

왜 이게 코테에서 중요한가?

이 두 개만 있으면 다음을 전부 O(log N)에 처리할 수 있다.

1) x가 존재하는지?

auto it = lower_bound(v.begin(), v.end(), x);
if(it != v.end() && *it == x)  // 존재

2) x의 개수

cnt = upper_bound(v.begin(), v.end(), x)
    - lower_bound(v.begin(), v.end(), x);

3) [l, r] 구간에 몇 개?

cnt = upper_bound(v.begin(), v.end(), r)
    - lower_bound(v.begin(), v.end(), l);

이게 정렬된 vector가 set보다 강한 이유다.

k번째 접근도 되고, 개수도 바로 구할 수 있다.

---

8️⃣ set에서의 lower_bound 사용법 (중요!)

이 부분은 코테에서 시간 초과를 결정짓는 매우 중요한 포인트이다.

• 틀린 방법: lower_bound(s.begin(), s.end(), x) → O(N) ◦ 이 방식은 일반적인 순차 반복자용 lower_bound를 사용하여 트리 구조를 무시하고 하나씩 확인한다.

• 맞는 방법: s.lower_bound(x) → O(log N) ◦ set의 멤버 함수 버전을 사용해야 트리의 특성을 이용해 빠르게 찾는다.

예:

set<int> s = {1,3,5,7};

auto it = s.lower_bound(4);  // 5
auto it2 = s.upper_bound(5); // 7

⚠️ 하지만:

s.upper_bound(r) - s.lower_bound(l)   // ❌ 불가능

set iterator는 뺄 수 없으므로:

int cnt = distance(s.lower_bound(l), s.upper_bound(r));  // O(N)

그래서 범위 개수를 자주 물으면 set이 느려진다.

---

9️⃣ 코테에서 가장 많이 쓰는 STL 함수들

// ===== vector =====
sort(v.begin(), v.end());
// 정렬 (중복 모으기 + 이진탐색 가능하게 만들기)

unique(v.begin(), v.end());
// 인접한 중복을 뒤로 밀고, 새 끝 iterator 반환

v.erase(it, v.end());
// unique로 밀려난 쓰레기 영역 제거

lower_bound(v.begin(), v.end(), x);
// x 이상 첫 위치 (이진 탐색)

upper_bound(v.begin(), v.end(), x);
// x 초과 첫 위치

binary_search(v.begin(), v.end(), x);
// x가 존재하는지만 O(logN)으로 확인

// ===== set / multiset =====
s.insert(x);
// x 삽입 (자동 정렬 + 중복 처리)

s.erase(x);
// 값 x 삭제 (set: 1개, multiset: 전부)

s.find(x);
// x의 iterator 반환 or s.end()

s.lower_bound(x);
// x 이상 첫 원소

s.upper_bound(x);
// x 초과 첫 원소

s.begin();
// 최소값

s.rbegin();
// 최대값

---

최종 코테 관점 정리

중복 + 정렬 + 동적 삽입	set
입력 다 받고 중복 제거	vector + sort + unique
k번째 원소 필요	vector
범위 개수 질의 많음	vector + lower/upper_bound
set에서 원소가 사라짐	comparator 오류 의심