엘리스 코드 챌린지 예선 [Day 1] 문제풀이

문제

목표량

• 시간 제한: 1초

엘리스 토끼는 목표량을 정해 수학 문제를 열심히 풉니다. 목표량은 정수입니다.

내일 풀 수학 문제의 개수는 오늘 푼 문제 개수의 수와 숫자의 구성이 같으면서, 오늘 푼 문제 개수의 수보다 큰 수 중 가장 작은 수입니다.

예를 들어, 오늘 67문제를 풀었으면 다음 날 76문제를 풉니다.

오늘 푼 문제의 개수를 줬을 때 다음날 풀 문제의 개수를 출력하는 프로그램을 작성하세요.

지시사항

입력

• 첫 번째 줄에 오늘 푼 문제의 개수인 자연수 N을 입력합니다.

1 ≤ N ≤ 999999

• 정답이 반드시 있는 경우만 입력값으로 주어집니다.

출력

• 다음날 풀 문제의 개수를 출력합니다.

입력 예시

364

출력 예시

436

 

풀이

접근

접근 방법에 대해 생각해 보자. 

문제를 보자마자 바로 떠오른 생각이 "경우의 수가 그렇게 많지 않을 것 같다"였다.

1일 차 강의 영상에서 강사님께서 시간 복잡도 영상에서 모든 경우의 수를 구하고 O(1)의 시간 복잡도로 바로 접근하는 방법을 언급하였는데, 응용을 해서 풀어보려고 생각했다.

 

첫 번째 풀이(구현 실패)

주어진 입력값의 범위가 1~999999이므로 입력 값 보다 큰 숫자를 1씩 더해가며 체크해 보자 라는 생각을 했다.

이 풀이를 구현하려고 생각해 보니까 주어진 숫자들을 하나씩 체크하는 것(입력이 364면 3과 6과 4를 하나씩 체크해야 함)이 너무 복잡할 것 같아서 다른 방법을 생각해 봤다.

두 번째 풀이

종이에 주어진 예시 숫자 364로 어떻게 구현해야 할지 하나씩 생각해 봤다.

내가 생각한 풀이는 배열에 자릿수에 해당하는 숫자들을 하나씩 넣고, 인덱스로 체크해 가며 교환하는 방식을 생각했다.

주어진 숫자를 이용하여 N보다 큰 숫자 중 가장 작은 숫자를 구하려면

1. 10의 자릿수(뒤에서 두 번째 인덱스 = size - 2)부터 기준 인덱스를 하나씩 감소시킴(왼쪽으로  이동)
2. 인덱스 왼쪽의 숫자(index + 1)를 현제 확인하고 있는 값(cur)으로 두고 하나씩 오른쪽으로 이동시킴
3. cur에 해당하는 값들 중 index에 해당하는 값보다 큰 값 중 가장 작은 값을 찾음(big)
4. index와 big에 해당하는 값을 교환
5. index 왼쪽 값들을 정렬

과정을 거치면 된다.

 

코드

#include <iostream>
#include <algorithm>
using namespace std;

int main() {

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int N, tmp, cur, index, big;
    int* arr;
    int size = 1, i = 0;
    bool flag = false;
    cin >> N;
    tmp = N;

    // size 계산, 배열 할당
    while (tmp /= 10)
        size++;

    arr = new int[size];

    tmp = N;
    i = size - 1;
    do {
        arr[i--] = tmp % 10;
    } while (tmp /= 10);

    index = size - 2;
    big = cur = index + 1;

    while (index >= 0)
    {
        // arr[index] 보다 큰 값중 가장 작은 값을 찾음
        while (cur < size)
        {
            if (arr[index] < arr[cur] && arr[big] >= arr[cur])
            {
                big = cur;
                flag = true;
            }
            cur++;
        }

        // 만약 값을 찾았다면
        if (flag)
        {
            // 자릿수 교환
            tmp = arr[big];
            arr[big] = arr[index];
            arr[index] = tmp;

            // 뒤에 오름차순 정렬
            sort(&arr[index + 1], &arr[size]);
            break;
        }

        // 인덱스를 이동시킴
        index--;
        big = cur = index + 1;
    }

    for (int i = 0; i < size; i++)
        cout << arr[i];

    delete arr;
    return 0;
}

↑ 더보기 클릭으로 펼치기

좀 어렵게 푼 것 같은데 투 포인터 알고리즘을 응용해서 풀었다.

 

모범답안

#include <algorithm>
#include <iostream>
#include <string>

using namespace std;

int main() {
  int pos1, pos2;
  string N;
  cin >> N;
  for (pos1 = N.length() - 2; N[pos1] >= N[pos1 + 1]; pos1--)
    ;
  for (pos2 = pos1 + 1; N[pos1] < N[pos2] && pos2 < N.length(); pos2++)
    ;
  pos2--;
  swap(N[pos1], N[pos2]);
  sort(N.begin() + pos1 + 1, N.end());
  cout << N;
}

↑ 더보기 클릭으로 펼치기

 

주최 측에서 올려준 모범 답안이다.

알고리즘은 비슷하고 내 코드는 조금 복잡하게 구현해 논 것 같다. 

 

후기

Day 1 문제인데 푸는 게 재밌었다.

이상하게 풀려고 해서 시간낭비를 좀 한 것 같은데 열심히 해봐야겠다.