[ Day 1 ] 목표량

1일차는 코딩테스트에서 어떤 알고리즘을 쓸지 문제를 풀기전에 지표를 잡아주는 주요 개념인

시간복잡도에 대한 강의였다.

 

나는 학습 자료가 꾸준히 남아있는 줄 알고 블로깅을 미루고 있었는데, 알고보니 그날 자정이 되면 사라진다고 한다.

 

내일부터는 강의 내용도 정리해서 기재할 예정이이다.

 

 

문제 :

목표량

• 시간 제한: 1초

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

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

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

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

지시사항

입력

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

1≤N≤999999

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

출력

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

입력 예시

364

출력 예시

436

 

 

작성 코드 :

the_world_is_flat = True
if the_world_is_flat:
    digits = list(input())
    length = len(digits)
    
    # 뒤에서부터 오름차순이 끊기는 첫 번째 위치 찾기
    i = length - 1
    while i > 0 and digits[i - 1] >= digits[i]:
        i -= 1
    
    # digits[i - 1]보다 큰 숫자를 찾기
    j = length - 1
    while digits[j] <= digits[i - 1]:
        j -= 1
    
    # 숫자 교환
    digits[i - 1], digits[j] = digits[j], digits[i - 1]
    
    # i부터 끝까지의 숫자를 오름차순으로 정렬
    digits = digits[:i] + sorted(digits[i:])
    
    print(''.join(digits))

 

 

정답 코드 :

C ++ 

#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;
}

 

Python 

s = list(input())
for i in range(len(s) - 2, -1, -1):
    if s[i] < s[i + 1]:
        break
else:
    print(0)
    exit()
for j in range(len(s) - 1, i, -1):
    if s[j] > s[i]:
        break
s[i], s[j] = s[j], s[i]
s[i + 1 :] = s[:i:-1]
print("".join(s))

 

Java

import java.util.Scanner;
import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String s = scanner.next();
        char[] charArray = s.toCharArray();
        
        if (nextPermutation(charArray)) {
            System.out.println(new String(charArray));
        } else {
            System.out.println(s);
        }
    }
    
    public static boolean nextPermutation(char[] array) {
        int i = array.length - 2;
        while (i >= 0 && array[i] >= array[i + 1]) {
            i--;
        }
        
        if (i < 0) {
            return false;
        }
        
        int j = array.length - 1;
        while (array[j] <= array[i]) {
            j--;
        }
        
        char temp = array[i];
        array[i] = array[j];
        array[j] = temp;
        
        reverse(array, i + 1, array.length - 1);
        return true;
    }
    
    private static void reverse(char[] array, int start, int end) {
        while (start < end) {
            char temp = array[start];
            array[start] = array[end];
            array[end] = temp;
            start++;
            end--;
        }
    }
}