알고리즘: 웨브바짐 문제 분해 - 2

주어진 알고리즘을 직관적으로 생각하기 어렵다고 생각하여 문제를 4개의 작은 문제들로 분리해보았습니다.

먼저, 원본 문제의 링크입니다: https://algospot.com/judge/problem/read/ZIMBABWE

입력받은 양의 정수형 숫자 num에 대하여 각 자릿수의 숫자의 순서를 바꾸어 나타낼 수 있는 모든 경우의 수를 출력하라. 단, num의 각 자릿수의 숫자는 중복될 수 있다. (예: 123, 385,9285, 2738, 2288, 1233)

for (int i = 0; i < size; i++){
    if (usedVec[i])
        continue;
    if (i != 0 && vec[i - 1] == vec[i] && !usedVec[i - 1])
        continue;
    logVec.push_back(vec[i]);
    usedVec[i] = true;
    cnt += price(idx + 1);
    usedVec[i] = false;
    logVec.pop_back();
}

분해1에서 보여드릴 소스코드 중에서 price 함수의 반복문에 일부가 추가되었습니다. 자릿수의 숫자들이 서로 같을 수 있다는 것은 이들이 순서가 바뀌어도 동일한 값이 나올 수 있다는 것을 의미합니다. 예를 들어, num = 2230이라고 한다면, 앞의 2와 뒤의 2의 순서가 바뀐다고 해도 2230이라는 값은 같습니다. 이러한 중복되는 경우를 배제하기 위해 현재 선택할 숫자들 중에서 i 번째 숫자와 i - 1번째 숫자가 같으면서 (즉, vec[i] == vec[i-1]) i-1번째 숫자가 아직까지 선택되지 않았다는 것은 한 가지 의미가 있습니다. 즉, 이미 i-1번째 숫자를 현재 선택했을 경우의 모든 가능한 수들을 구했다는 의미가 되며, 만약 i 번째 숫자를 현재 숫자로 선택하게 된다면 값은 값을 두 번 선택하게 되어 중복된 결과를 출력하게 되는 문제가 발생합니다. 따라서, 라인 4와 같이 vec[i-1]과 vec[i]가 같은 값을 가지면서 i-1번째 값이 선택되지 않았다면 현재 값을 선택하지 않고 넘어가도록 처리를 해주어야 합니다.

결과가 중복되지 않게 출력되는 것을 확인할 수 있습니다.