ksjb2897   1년 전

코드는 구체적으로 보지 않으셔도 됩니다.

대충 arr[800000]까지 만들고, 각 sum마다 그 인덱스가 합이 되는 두개의 goods의 인덱스를 pair로 넣었어요.

예를 들어, 0 1 2 3 4가 있으면 arr[5] = {{1, 4}, {2, 3}}이 되도록요.

여긴 다른 사람들 풀이와 비슷한 것 같고, 근데 저는 arr안에 여러개의 pair가 있도록 vector로 만들었거든요. 그렇게 함으로써 모든 쌍을 저장하게 해뒀어요. 그리고 대충 머리 조금 써서 36~59라인에 있는 코드처럼 상수시간만에 arr[i]와 arr[w-i]에서 겹치는 쌍이 있는지 없는지 테스트 하는 분기를 만들었습니다. 이 코드는 안보셔도 무방해요!

무튼 그렇게 해서,

처음 goods 정렬 O(NlogN) (정렬하는 이유는 아까 36~59라인에 있는 코드를 위해서 그랬습니다)

arr 생성 O(N^2)

각 무게마다 확인 O(w*상수) (여기서 상수가 좀 크긴함)

이여서 최대 O(N^2)일 것 같은데, 왜 초과가 날까요?

그리고 생각해보니, 대충 5000*5000/2의 연산동안, push_back 을 통해서 이중벡터를 만드는데, 이게 혹시 문제가 있을까요? 아무래도 동적배열이다보니 연산의 소모량이 많이 큰가요..?

zenith82114   1년 전

마찬가지로 O(N^2) 시간의 이중 순회를 하지만 O(N) 배열 하나만을 사용하는 풀이는 매우 빠르게 동작하기 때문에 마지막 줄에 쓰신 추측이 맞을 가능성이 큽니다. Dynamic array에서 임의의 삽입/삭제 시간은 이론적으로는 amortized O(1)이나 원소의 개수가 아주 많아지면 실제 메모리 시스템 구조상 더 느려집니다.

ksjb2897   1년 전

감사합니다!

댓글을 작성하려면 로그인해야 합니다.