[algorithm]더미에서 효율적으로 양말을 어떻게 켤 수 있습니까?

더미에서 효율적으로 양말을 어떻게 켤 수 있습니까? 질문 어제 나는 양말을 깨끗 한 세탁물에서 페어링하고 제가 수행하는 방식을 알아 냈습니다. 매우 효율적이지는 않습니다.나는 쌍을 찾기 위해 하나의 양말을 선택하고 "반복"을 선택하고 있습니다.N / 2 * N / 4 = N2 / 8 양말을 평균적으로 반복해야합니다.컴퓨터 과학자로서 내가 할 수있는 일을 생각하고 있었습니까?물론 정렬 (크기 / 색상 / ...)에 따라 O (NLOgn) 솔루션을 달성하기 위해 마음에 왔습니다.해시 또는 다른 솔루션이없는 솔루션은 옵션이 아닙니다. 왜냐하면 나는 양말을 복제 할 수 없기 때문입니다 (내가 할 수 있지만 좋을 수 있습니다).그래서 질문은 기본적으로 다음과 같습니다.2N 요소가 들어있는 N 쌍의 양말의 더미를 ..