7568번 - 덩치
각 원소마다 벡터를 한번씩 탐색하는 방법을 사용했는데 시간복잡도를 줄이려고 (1) vector<pair<pair<int,int>, int>> v 로 두고 수가 들어온 순서를 저장한 다음 v를 정렬해서 푸는 방법과 (2) 배열을 만든 뒤 해당 배열 인덱스(몸무게)의 키 다음에는 이전 배열의 키보다 큰 수만 들어갈 수 있도록 지정하는 방법을 생각해봤는데 명확한 답이 떠오르지 않아 질문해요. O(n^2)보다 더 빠르게 푸는 접근법이 있나요?
https://www.acmicpc.net/board/...
댓글을 작성하려면 로그인해야 합니다.
rkddbswn0 1년 전
각 원소마다 벡터를 한번씩 탐색하는 방법을 사용했는데 시간복잡도를 줄이려고 (1) vector<pair<pair<int,int>, int>> v 로 두고 수가 들어온 순서를 저장한 다음 v를 정렬해서 푸는 방법과 (2) 배열을 만든 뒤 해당 배열 인덱스(몸무게)의 키 다음에는 이전 배열의 키보다 큰 수만 들어갈 수 있도록 지정하는 방법을 생각해봤는데 명확한 답이 떠오르지 않아 질문해요. O(n^2)보다 더 빠르게 푸는 접근법이 있나요?