99클럽 코테 스터디 7일차 TIL + C++ 순열 만들기

오늘의 문제 

https://school.programmers.co.kr/learn/courses/30/lessons/1835

프로그래머스

 

C++ 순열 만들기

문제에서 우선 가능한 string 전체를 만들려고 시도했다. 

그래서 가능한 모든 순열을 만들어야 했다. 

 

어떻게 가능한 모든 순열을 만들어야 하나 고민했는데 C++에 함수가 정의되어 있었다. 

next_permutation이라는 함수를 사용하면 된다. 

next_permutation 함수는 algorithm 헤더에 정의되어 있다. 

 

next_permutation 함수는 파라미터로 Bidirectional Iterator (iterator의 일종 같다) 2개를 받는다. 

순열을 만들 범위를 의미하는 first, last에 해당하는 iterator를 받는다. 

그래서 first~last 범위에 있는 요소들을 사전순 순열로 바꾸는 것이다

. 

다음 순열이 존재하면 true, 그렇지 않으면 false를 반환한다.

false를 반환한 후 첫번째 순열로 재배열 된다고 한다. 

 

가능한 모든 순열 만드는 방법

1. 정렬을 수행한다 (string, vector 등 iterator 있는 것 모두 가능)
2. do-while문과 next_permutation 함수를 사용해 가능한 모든 순열을 만든다.

 

코드르 보면 아래와 같다. 

아래 코드는 string에서 모든 순열을 만드는 코드이다. 

    vector<string> allStr;
    string str="ACFJMNRT";
    
    // 모든 순열 생성
    do {
        allStr.push_back(str);
    } while (next_permutation(str.begin(), str.end()));

 

do-while을 사용하는 이유는 첫번째 순열도 저장하기 위함이다. 

next_permutation을 사용하면 바로 다음 순열을 만들기 때문에 do-while을 사용하지 않으면 첫번째 순열이 무시된다. 

 

next_permutation을 사용하면 중복이 있는 원소들의 경우 중복인 경우를 제외하고 순열을 만들어준다고 한다. 

그리고 next_permutation을 사용해 순열 말고도 조합도 만들 수 있다고 한다. 

 

참고 자료

• https://taehun0933.tistory.com/18
• https://twpower.github.io/90-combination-by-using-next_permutation

 

 

회고

우선 어떻게 풀지가 감이 안 왔다.

조건을 보고 조건에 맞는 블록을 만든 후 이동 시켜야 하나 이런 생각이 들었다. 

그런데 어떻게 구현해야 할지 감이 안 왔고 또 구현이 너무 어려울 것 같았다. 

 

다른 사람의 풀이를 보니 우선 전체 순열을 만들고 조건에 맞는 것의 갯수를 세었다는 풀이를 보았다. 

생각해보니 8! = 40320 밖에 안되니 시간 초과가 그렇게 쉽게 나지 않겠다고 생각했다. 

물론 시간 제한이 얼마인지 나와있지는 않았지만...

 

그래서 우선 전체 순열을 만드는 것까지 구현을 했다. 

그 이후 이제 조건을 어떻게 분리하고 조건에 맞는 것을 어떻게 찾아야할지 고민해야 한다. 

풀이를 완성한다면 후기를 공유해 보겠다.