[ 백준 ] 2336 굉장한 학생 ( Python )
안녕하세요! 오늘은 세 번의 시험 성적을 기준으로 ‘굉장한’ 학생을 찾아내는 알고리즘 문제에 대해 소개해 드리려고 합니다.
문제의 내용은 다음과 같습니다. N명의 학생이 세 번의 시험을 치렀고, 각 시험마다 1등부터 N등까지 등수가 매겨졌습니다. 만약 어떤 학생 A가 다른 학생 B보다 세 번의 시험에서 모두 더 좋은 등수를 받았다면, A는 B보다 ‘대단하다’고 합니다. 그리고 어떤 학생 C가 다른 그 어떤 학생보다도 ‘대단하지’ 않다면, C를 ‘굉장한’ 학생이라고 부릅니다. 문제는 주어진 시험 등수를 바탕으로 ‘굉장한’ 학생이 몇 명인지 구하는 것입니다.
처음 이 문제를 접했을 때, 가장 먼저 떠오른 접근 방식은 모든 학생 쌍에 대해 일일이 비교를 하는 것이었습니다. 하지만 이는 O(N^2)의 시간 복잡도를 가지므로, N이 최대 500,000이라는 점을 감안하면 제한 시간 내에 통과하기 어려운 방법이었죠.
그래서 저는 좀 더 효율적인 알고리즘을 고민하기 시작했습니다. 먼저 학생들을 첫 번째 시험 등수를 기준으로 정렬하면 어떨까 하는 생각이 들었습니다. 첫 번째 시험에서 더 좋은 등수를 받은 학생은 적어도 한 과목에서는 자신보다 뒤에 있는 학생들보다 ‘대단할’ 가능성이 있기 때문이죠.
하지만 단순히 정렬을 한다고 해서 문제가 해결되는 것은 아니었습니다. 여전히 각각의 학생에 대해, 자신보다 첫 번째 시험 등수가 낮은 학생들과 일일이 비교를 해야 했기 때문입니다.
그런데 여기서 좋은 아이디어가 떠올랐습니다. 바로 세그먼트 트리(segment tree)를 활용하는 것이었죠. 세그먼트 트리는 구간에 대한 질의를 빠르게 처리할 수 있는 자료구조입니다. 이를 활용하면 각 학생에 대해 자신보다 첫 번째 시험 등수가 낮은 학생들 중 최고 등수를 O(log N)의 시간 복잡도로 구할 수 있습니다.
세그먼트 트리를 활용한 풀이는 다음과 같습니다.
- 학생들을 첫 번째 시험 등수 기준으로 정렬합니다.
- 세그먼트 트리를 만들어 초기화합니다. 이때 각 노드는 해당 구간에서의 두 번째 시험 최고 등수와 세 번째 시험 최고 등수를 저장합니다.
- 첫 번째 시험 등수가 높은 학생부터 순서대로 살펴봅니다. 현재 보고 있는 학생을 A라고 합시다.
- 세그먼트 트리를 통해 A보다 첫 번째 시험 등수가 낮은 학생들 중 최고 두 번째 시험 등수와 최고 세 번째 시험 등수를 구합니다.
- 만약 이 두 값이 모두 A의 등수보다 크다면, A는 ‘굉장한’ 학생입니다.
- A의 두 번째, 세 번째 시험 등수를 세그먼트 트리에 반영합니다.
- ‘굉장한’ 학생의 수를 출력합니다.
이와 같은 방식으로 문제를 해결하면 O(N log N)의 시간 복잡도로 정답을 구할 수 있습니다.
사실 이 문제는 상당히 까다로운 문제입니다. 단순한 접근 방식으로는 시간 제한을 만족시키기 어렵죠. 저 역시 처음에는 브루트 포스로 접근했다가 시간 초과를 받았고, 그 다음에는 정렬만 가지고 해결하려 해 보았지만 역시 시간 초과를 면할 수 없었습니다.
하지만 포기하지 않고 계속해서 고민한 끝에 세그먼트 트리라는 핵심 아이디어를 떠올릴 수 있었습니다. 문제 해결에는 때로 이런 창의적인 통찰이 필요한 것 같아요. 그리고 그런 통찰을 해내기 위해서는 평소에 꾸준히 다양한 알고리즘과 자료구조를 학습하고 연습해 두는 것이 도움이 된다고 생각합니다.
이 문제를 통해 자료구조의 중요성도 다시 한번 깨달을 수 있었는데요, 세그먼트 트리라는 적절한 도구 덕분에 효율적인 알고리즘을 설계할 수 있었습니다. 앞으로도 다양한 문제 상황에 맞는 최적의 자료구조와 알고리즘을 선택하는 안목을 기르는 것이 중요할 것 같네요.
이상으로 ‘굉장한’ 학생을 찾는 문제에 대한 풀이를 마치겠습니다. 알고리즘 문제를 푸는 것이 결코 쉽지만은 않지만, 포기하지 않는 도전 정신과 꾸준한 학습을 통해 여러분 모두 멋진 개발자로 성장할 수 있을 거라 믿습니다.
긴 글 읽어 주셔서 감사합니다!
전체 코드 보기
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
import sys
input = sys.stdin.readline
class Student:
def __init__(self, a=0, b=0, c=0):
self.a = a
self.b = b
self.c = c
def compare(s):
return s.a
MAX_SIZE = 500000 + 10
students = [Student() for _ in range(MAX_SIZE)]
segment_tree = [0] * (4 * MAX_SIZE)
def update(node, start, end, idx, value):
if idx < start or end < idx:
return segment_tree[node]
if start == end:
segment_tree[node] = value
return segment_tree[node]
mid = (start + end) // 2
segment_tree[node] = min(
update(node * 2, start, mid, idx, value),
update(node * 2 + 1, mid + 1, end, idx, value)
)
return segment_tree[node]
def query(node, start, end, left, right):
if right < start or end < left:
return float('inf')
if left <= start and end <= right:
return segment_tree[node]
mid = (start + end) // 2
return min(
query(node * 2, start, mid, left, right),
query(node * 2 + 1, mid + 1, end, left, right)
)
n = int(input().strip())
a_ranks = list(map(int, input().strip().split()))
b_ranks = list(map(int, input().strip().split()))
c_ranks = list(map(int, input().strip().split()))
for i in range(1, n + 1):
students[a_ranks[i - 1]].a = i
for i in range(1, n + 1):
students[b_ranks[i - 1]].b = i
for i in range(1, n + 1):
students[c_ranks[i - 1]].c = i
students = sorted(students[1:n+1], key=compare)
for i in range(1, n + 1):
update(1, 1, n, i, float('inf'))
count = 0
for i in range(1, n + 1):
if query(1, 1, n, 1, students[i - 1].b) > students[i - 1].c:
count += 1
update(1, 1, n, students[i - 1].b, students[i - 1].c)
print(count)