2.2.1 문제 간단하게 만들기

다음 문제를 살펴봅시다. 여러 명의 부부가 한 줄로 무작위로 서 있습니다. 남편은 H₁, H₂, H₃ ... 아내는 W₁, W₂, W₃ ... 형태로 각각 번호가 있습니다. H₁이 맨 처음에 오고 그다음에 W₁이 오고 그 뒤로 H₂, W₂ ... 형태로 배열해야 합니다.

처음에는 어려워 보이지만 간단한 문제입니다. 마지막 위치의 관계를 찾습니다.

P(H_i) = i × 2 – 1

P(W_i) = i × 2

나머지 알고리즘은 삽입 정렬 등으로 구현해 완성하면 됩니다.