sorting (1) 썸네일형 리스트형 [Leetcode] 406번 - 키에 따른 대기열 재구성 1. 문제 파악문제 링크: https://leetcode.com/problems/queue-reconstruction-by-height/description/문제 정의: 자기 보다 키큰 사람의 수(k)에 맞춰서 큐에 저장해라.입력크기: 1 2. 문제 풀이1. 핵심 문제 풀이 도출(문제 의도 파악): 어떻게 하면 시간 복잡도 내로 줄일수 있을까?이 문제는 '내 앞에 나보다 키가 크거나 같은 사람이 k명 있어야 한다' 라는 점이다. 따라서 핵심은 키 큰 사람부터 위치를 확정하면 나중에 작은 사람을 끼워 넣어도 조건이 깨지지 않는다는 점이다. 큰 키부터 배치해놓으면, 이후에 들어오는 사람은 그보다 작거나 같은 키이므로, 앞에 큰 사람의 수는 변하지 않는다. 따라서 먼저 키(h) 큰 사람 순으로 배치해놓는다. .. 이전 1 다음