에.. 그러니까 내가 원하는게 사실 어떤 이름으로 불려야하는지 모르겠다. 일단 문제 설명과 풀이부터..
문제정의
- 갯수가 같은 리스트 A, B에서
- 원소가 매칭되는 모든 경우를 나열하여라.
해결의 핵심
- 리스트 A의 원소를 순서와 상관있게 줄세워본다.
- 리스트 B의 원소는 줄세우지 않고 바로 위의 줄과 일직선 매핑.
구현
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| static void makePair(vector<int>& part1, vector<char>& part2) { | |
| // 0. check parts | |
| if (part1.size() != part2.size()) { | |
| cout << "no same count" << endl; | |
| return; | |
| } | |
| // 1. build permutation of part1 | |
| int cnt = (int)part1.size(); | |
| int num = 0; | |
| sort(part1.begin(), part1.end()); | |
| do { | |
| cout << ++num << "th pairs" << endl; | |
| for (int i = 0; i < cnt; ++i) { | |
| // 2. make pair from part2 | |
| cout << " " << part1[i] << " - " << part2[i] << endl; | |
| } | |
| } while(next_permutation(part1.begin(), part1.end())); | |
| } |
주의사항
탐색공간
- 루프 불변식 혹은
- 이전 - 현재 - 이후 조건 그리고
- 경계 조건
루프는 next_permutation에 의해 이루어지며, next_permutation은 탐색공간이 순서가 있을것을 요구하며, 사전 순서의 마지막에 도달할때까지 탐색공간을 조합하여 변형시켜 나간다.
따라서 루프의 시작은 최초의 sorting된 값을 필요로 하며, 일반적으로 루프를 쓰는것과 다르게 do-while문을 사용한다.
사전 순서대로의 탐색이며 이 작업 또한 stl이 해주므로 다른 경계이슈등은 적은 편이다.