백준 문제 2992번 크면서 작은 수

문제 출처:

https://www.acmicpc.net/problem/2992

2992번: 크면서 작은 수

백준 2992번 크면서 작은 수 문제

문제를 다시 한번 설명하자면 정수 X[1, 999999]를 인풋으로 받고 같은 구성의 가장 작게 큰 수를 찾으면 되는 것이다. 여기서 같은 구성이라 함은 그 숫자들의 순열을 구하라는 것이다.

1,5,6이라는 3가지 수 중에서 중복되지 않게 3가지를 고른다고 해보자.​

{(1,5,6), (1,6,5),

(5,1,6), (5,6,1),

(6,1,5), (6,5,1)}

​

다음과 같이 표현할 수 있으며, X로 들어온 인풋이랑 크기를 비교해야하기 때문에 sort가 쓰여야 할 것이다.

​

이 문제에 어떻게 접근해야 할지 감을 못잡고 있을 때의 한 블로그를 참고하게 되었습니다.

​

https://blog.naver.com/bestowing/221834118560

[C++] 순열과 조합

이 블로그에서는 next_permutation이라는 c++ STL을 이용해서 구하는 법을 알려주고 있다.

​

해당 블로그와 cpp 레퍼런스 사이트를 참고하여 이런 것도 있다는 것을 알게되었다

#include <algorism>

default (1)	
template <class BidirectionalIterator>
  bool next_permutation (BidirectionalIterator first,
                         BidirectionalIterator last);
custom (2)	
template <class BidirectionalIterator, class Compare>
  bool next_permutation (BidirectionalIterator first,
                         BidirectionalIterator last, Compare comp);

​Rearranges the elements in the range [first,last) into the next lexicographically greater permutation.

http://www.cplusplus.com/reference/algorithm/next_permutation/

next_permutation은 표준 라이브러리(STL: Standard Template Library)에 정의된 함수로서,

순열을 만들어주는 함수이다.

​

http://www.cplusplus.com/reference/algorithm/next_permutation/

next_permutation - C++ Reference

​

C++ Reference를 다루는 사이트에서 예시로 둔 것은 다음과 같다:

사용 예시 : http://www.cplusplus.com/reference/algorithm/next_permutation/

이것에 근거하여 제가 작성한 코드는 이처럼 작성하였는데 visual code에서는 정상 작동 되는 부분이 백준 문제 제출에서는 컴파일 오류를 띄운다 #include의 차이로 보이는데 해당부분을 다음과 같이 수정해 주니 해결되었다.

평상시에 대수롭지 않게 사용하던 strlen, strcat, ... 과 같은 것들 STL의 중요성을 한번 더 깨닫는 날이다.

//P_16112

#include <iostream>
#include <vector>
#include <string>
#include <string.h>
#include <algorithm>

using namespace std;

int main(int argc, const char * argv[]) {
    ios::sync_with_stdio();
    cin.tie(NULL);
    cout.tie(NULL);
    //int X;
    char X[6] ;
    cin >> X ;
    short len = strlen(X) ;
    int x = atoi(X) ;

    vector <int> u;
    string buffer ;

    do {
        for(int i = 0; i < len; i++){
            buffer += X[i] ;
        }
        u.push_back(atoi(buffer.c_str()));
        buffer.clear() ;
    } while(next_permutation(X, X + len)) ;

    sort(u.begin(), u.end());

    for(int i = 0 ; i < u.size(); i++){
        if(x < u[i]){
            printf("%d\n", u[i]);
            return 0 ;
        }
    }

    printf("0\n");

    return 0;
}

 

해당 내용은 다음 Github에서도 보실 수 있습니다

https://github.com/gurcks8989/CodingTest/blob/master/BackJoon/HPS/P2992_Big%26SmallSize.cpp

GitHub - gurcks8989/CodingTest: BackJoon_study_with_c++

 

훈수 및 조언은 언제든지 환영입니다.