You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
reacted with thumbs up emoji reacted with thumbs down emoji reacted with laugh emoji reacted with hooray emoji reacted with confused emoji reacted with heart emoji reacted with rocket emoji reacted with eyes emoji
Uh oh!
There was an error while loading. Please reload this page.
문제 링크
https://fastcampus.co.kr/classroom/203934
문제 조건
아이디어
이 문제는 전형적인 위상정렬 문제이다.
학생들 간의 위상 관계가 주어지고, 이에 맞게 줄을 세우면 된다.
먼저 그래프를 통해 키를 비교한 결과를 나타낸 뒤 위상정렬 시켜주자
정점: 학생 번호(1~N)
간선: 작은 사람이 앞에 와야 하므로 X<Y일 때 X -> Y
시간 복잡도
정점의 최대수는 32000이고, 간선의 최대 수는 10만이기 때문에 위상정렬하는데 약 O(10만)이므로 시간 안 풀이가 가능하다.
구현
All reactions