프로그래머스 LV.2 피로도

 

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

프로그래머스

푸는 방법은 크게 2가지이다.

 

1. 배열의 모든 경우의 수를 싹 돌아보는 것

2. DFS로 푸는 것이다.

 

1번째의 경우에는 

next_permutation 알고리즘을 써서 모든 경우의 수를 탐색할 수 있다.

 

next_permutation함수는 std의 algorithm 라이브러리 안에 내장된 함수이다.

next_permutation함수는 해당 집합의 모든 순열을 구해준다.

 

예를 들어 {1,2,3}이라는 원소를 가진 집합이 있다면

{1,2,3}

{1,3,2}

{2,1,3}

{2,3,1}

{3,1,2}

{3,2,1}

이라는 모든 경우를 다른 방법으로 보는 것이다.

 

next_premutation 함수의 기본적인 문법은 다음과 같이 정의되어 있다.

template<class BidirectionalIterator>
bool next_permutation(
    BidirectionalIterator first,
    BidirectionalIterator last);

template<class BidirectionalIterator, class BinaryPredicate>
bool next_permutation(
    BidirectionalIterator first,
    BidirectionalIterator last,
    BinaryPredicate pred);

 

각 매개 변수는 다음을 의미한다.

first

순열할 범위의 첫 번째 요소 위치의 주소를 가리키는 양방향 반복기

last

순열할 범위의 마지막 요소 하나 다음 위치의 주소를 가리키는 양방향 반복기

pred

순서에 따라 연속적인 요소에 대해 충족될 비교 조건을 정의하는 사용자 정의 조건자 함수 개체

이진 조건자는

두 개의 인수를 사용하여 조건이 충족되면 true를 반환하고, 충족되지 않으면 false를 반환한다.

 

#include <vector>
#include <deque>
#include <algorithm>
#include <iostream>
#include <ostream>

using namespace std;

// CInt 클래스 선언 및 관련 연산자 오버로딩
class CInt;
ostream& operator<<( ostream& osIn, const CInt& rhs );

class CInt
{
public:
    // 생성자 및 복사 생성자 정의
    CInt( int n = 0 ) : m_nVal( n ) {}
    CInt( const CInt& rhs ) : m_nVal( rhs.m_nVal ) {}

    // 할당 연산자 오버로딩
    CInt& operator=( const CInt& rhs ) {
        m_nVal = rhs.m_nVal;
        return *this;
    }

    // 비교 연산자 '<' 오버로딩 (정렬에 사용)
    bool operator<( const CInt& rhs ) const {
        return ( m_nVal < rhs.m_nVal );
    }

    // 출력 연산자 오버로딩을 위해 friend 선언
    friend ostream& operator<<( ostream& osIn, const CInt& rhs );

private:
    int m_nVal;
};

// CInt 출력 연산자 오버로딩 정의
inline ostream& operator<<( ostream& osIn, const CInt& rhs )
{
    osIn << "CInt( " << rhs.m_nVal << " )";
    return osIn;
}

// 모듈러 값을 기준으로 비교하는 함수 (음수도 양수로 취급)
bool mod_lesser(int elem1, int elem2)
{
    if ( elem1 < 0 )
        elem1 = -elem1;
    if ( elem2 < 0 )
        elem2 = -elem2;
    return elem1 < elem2;
};

int main()
{
    // CInt 타입의 deque 순열 변경 예제
    CInt c1 = 5, c2 = 1, c3 = 10;
    deque<CInt> deq1;
    deque<CInt>::iterator d1_Iter;

    // deque에 CInt 객체 추가
    deq1.push_back(c1);
    deq1.push_back(c2);
    deq1.push_back(c3);

    // 초기 deque 출력
    cout << "The original deque of CInts is deq1 = (";
    for ( d1_Iter = deq1.begin(); d1_Iter != --deq1.end(); d1_Iter++ )
        cout << " " << *d1_Iter << ",";
    d1_Iter = --deq1.end();
    cout << " " << *d1_Iter << " )." << endl;

    // next_permutation으로 순열 생성
    bool deq1Result = next_permutation(deq1.begin(), deq1.end());

    // 결과 출력
    if ( deq1Result )
        cout << "The lexicographically next permutation exists and has\nreplaced the original ordering of the sequence in deq1." << endl;
    else
        cout << "The lexicographically next permutation doesn't exist\n and the lexicographically smallest permutation\n has replaced the original ordering of the sequence in deq1." << endl;

    // next_permutation 후의 deque 출력
    cout << "After one application of next_permutation,\n deq1 = (";
    for ( d1_Iter = deq1.begin(); d1_Iter != --deq1.end(); d1_Iter++ )
        cout << " " << *d1_Iter << ",";
    d1_Iter = --deq1.end();
    cout << " " << *d1_Iter << " )." << endl << endl;

    // vector의 next_permutation 예제 (mod_lesser 비교 함수 사용)
    vector<int> v1;
    vector<int>::iterator Iter1;

    // 벡터에 -3부터 3까지 숫자 추가
    for ( int i = -3; i <= 3; i++ )
    {
        v1.push_back(i);
    }

    // 초기 벡터 출력
    cout << "Vector v1 is ( " ;
    for ( Iter1 = v1.begin(); Iter1 != v1.end(); Iter1++ )
        cout << *Iter1 << " ";
    cout << ")." << endl;

    // next_permutation을 모듈러 기준으로 적용
    next_permutation(v1.begin(), v1.end(), mod_lesser);

    // 첫 번째 next_permutation 후 벡터 출력
    cout << "After the first next_permutation, vector v1 is:\n v1 = ( " ;
    for ( Iter1 = v1.begin(); Iter1 != v1.end(); Iter1++ )
        cout << *Iter1 << " ";
    cout << ")." << endl;

    // 벡터에 대해 추가적인 next_permutation 반복
    int iii = 1;
    while ( iii <= 5 ) {
        next_permutation(v1.begin(), v1.end(), mod_lesser);
        cout << "After another next_permutation of vector v1,\n v1 =   ( " ;
        for ( Iter1 = v1.begin(); Iter1 != v1.end(); Iter1++ )
            cout << *Iter1 << " ";
        cout << ")." << endl;
        iii++;
    }
}

주요 포인트:

1. CInt 클래스 정의:
   이 클래스는 정수를 저장하며,
   출력(<<)과 비교(<) 연산자를 오버로딩하여 정렬과 출력에 사용할 수 있도록 한다.
2. next_permutation 함수 사용:
   • deque와 vector에 대해 next_permutation을 사용해서
     원소들을 사전식으로 다음 순열로 정렬하고 있다.
   • 벡터에서는 mod_lesser라는 사용자 정의 함수로
     순열을 생성하여 절대값을 기준으로 비교하도록 하고 있다.
3. 출력 과정:
   순열의 변화를 확인하기 위해 deque와 vector의 원소들을 반복적으로 출력하고 있다

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int solution(int k, vector<vector<int>> dungeons) {
    int answer = 0;
    
    sort(dungeons.begin(),dungeons.end());
    do{
        int num = k;
        int cnt = 0;
        
        for(int i = 0; i < dungeons.size(); i++){
            if(num < dungeons[i][0]){
                continue; 
            }
            num -= dungeons[i][1];
            cnt++;
        }
        answer = max(answer, cnt);
    }while(next_permutation(dungeons.begin(),dungeons.end()));
    
    return answer;
}

 

 

2. DFS의 풀이

 

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int ans = 0;
int visit[9];

int DFS(vector<vector<int>> dungeons, int k, int n)
{
    ans = max(ans, n);

    for (int i = 0; i < dungeons.size(); i++) {
        if (visit[i] || dungeons[i][0] > k) {
            continue;
        }

        visit[i] = true;
        DFS(dungeons, k - dungeons[i][1], n+1);
        visit[i] = false;
    }

    return ans;
}

int solution(int k, vector<vector<int>> dungeons) {
    int ans = -1;

    ans = DFS(dungeons, k, 0);
    return ans;
}