알고리즘 코드 챌린지 1일차 - 시간 복잡도

시간 복잡도 - 문제를 해결하는 데 걸리는 시간과 입력 사이의 관계

빅 오 - 상한 접근 = 최악 경우
빅 오메가 - 하한 접근 = 최선의 경우
빅 세타 - 둘의 평균

빅 오 표기법 종류
1 - 일정한 복잡도 = 입력의 크기와 상관 없이 즉시 출력값을 얻어낼 수 있다.
log N - N이 커질 수록 N보다 1의 복잡도에 가까워진다. = 중간값을 제시하면서 경우의 수를 절반 씩 나누는 법
N - 선형 복잡도 = 입력과 실행시간이 같은 비율로 증가 (입력 값이 커질수록 계수의 의미가 퇴색)
N log N -
N^2 - 2차 복잡도 = 2중 for문에서 보인다.
2^N - 지수 복잡도 = 특별한 경우를 제외하고는 안나오므로 다른 접근 방식을 고민해보는 것이 좋다.
N! - 시간 복잡도가 가장 크다.

시간 복잡도에 따라 실행 시간이 급격하게 변한다.

시간 복잡도를 줄이기 위해서 다양한 방식을 생각할 이유가 있다.

대략적으로 1초에 1억번 연산한다.10^8
시간제한이 2초면 2억번 연산 안에 끝내야 한다.

N범위를 확인 후 완전 탐색으로 해결한지 확인하기
떠오른 방법의 시간 복잡도로 제한 시간 안에 만족할 수 있는지 확인하기
완전 탐색으로는 시간이 부족하면, 시간 복잡도가 낮은 다른 알고리즘 떠올리기

무작정 구현하면 코드를 처움부터 작성해야 할 수 있다. - 시간 복잡도 먼저 고민하자.

1초고 1<= N <= 10^5라면 N^2은 못쓴다. N log N까지 가능하다.

 

문제 

• 시간 제한: 1초

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

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

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

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

지시사항

입력

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

1≤N≤999999

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

출력

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

입력 예시

364

출력 예시

436

 

너무 오랜만에 푸는 문제다 보니 아무렇게나 만들었는데....

a= int(input())
num = a
maxnum = 999999
b = [0] * 6
i = 0

while (a >= 1 ):
    b[i] = int(a%10)
    print(b[i])
    i = i +1
    a /=10

c = 0
for j in range (i) :
    c = b[j]
    for k in range (i) : 
        if j == k:
            continue
        c = c*10 + b[k]
    if(c > maxnum or c < num) :
        continue
    maxnum = c

print(maxnum)

이렇게 했더니 생각해보니까 모든 경우의 수를 다 한것이 아니더라고여

N!로 모든 경우의 수를 다 생각해도 시간 남으니..

할일 하고 와서 다시 고민해보겠씁니다..

 

올바른 방법은 다음과 같습니다:

1. 주어진 숫자를 문자열로 변환합니다.
2. 주어진 숫자를 구성하는 모든 자리 수를 포함하는 다음 큰 수를 찾습니다.
3. 이때, 각 자리 수를 재배열하여 조건을 만족하는 가장 작은 수를 찾습니다.

다음은 이를 구현한 코드입니다:

from itertools import permutations

def next_bigger_number(n):
    digits = list(str(n))
    length = len(digits)

    for i in range(length - 2, -1, -1):
        if digits[i] < digits[i + 1]:
            break
    else:
        return -1  # No higher permutation possible

    for j in range(length - 1, i, -1):
        if digits[j] > digits[i]:
            digits[i], digits[j] = digits[j], digits[i]
            break

    digits = digits[:i + 1] + sorted(digits[i + 1:])
    return int("".join(digits))

a = int(input())
result = next_bigger_number(a)
print(result)

이 코드의 작동 원리는 다음과 같습니다:

1. 입력 숫자를 문자열 리스트로 변환합니다.
2. 맨 뒤에서부터 앞쪽으로 숫자들을 비교하여 오름차순이 깨지는 지점을 찾습니다.
3. 그 지점의 숫자보다 큰 숫자 중 가장 작은 숫자를 찾아 교환합니다.
4. 교환 이후의 숫자들을 오름차순으로 정렬하여 가장 작은 수를 만듭니다.

이 코드를 사용하면 입력된 숫자보다 크고, 숫자의 구성은 동일하며, 가장 작은 수를 찾을 수 있습니다.

물론입니다! 다음은 다양한 접근 방법들을 제시하겠습니다:

방법 1: 순열을 이용한 모든 경우 탐색

입력된 숫자의 자리 수를 바꿀 수 있는 모든 가능한 순열을 생성하고, 그 중에서 입력된 숫자보다 크면서 가장 작은 숫자를 찾는 방법입니다.

from itertools import permutations

def next_bigger_number(n):
    digits = list(str(n))
    perm = sorted(set(int("".join(p)) for p in permutations(digits) if int("".join(p)) > n))
    return perm[0] if perm else -1

a = int(input())
result = next_bigger_number(a)
print(result)

방법 2: 뒤에서부터 스왑하기

주어진 숫자를 뒤에서부터 탐색하여 자리 교환을 통해 다음 큰 숫자를 찾는 방법입니다.

def next_bigger_number(n):
    digits = list(str(n))
    length = len(digits)

    for i in range(length - 2, -1, -1):
        if digits[i] < digits[i + 1]:
            break
    else:
        return -1  # No higher permutation possible

    for j in range(length - 1, i, -1):
        if digits[j] > digits[i]:
            digits[i], digits[j] = digits[j], digits[i]
            break

    digits = digits[:i + 1] + sorted(digits[i + 1:])
    return int("".join(digits))

a = int(input())
result = next_bigger_number(a)
print(result)

방법 3: 정렬 후 비교

현재 숫자를 정렬하여 가능한 모든 조합을 만들고, 그 중에서 입력된 숫자보다 크면서 가장 작은 숫자를 찾는 방법입니다.

def next_bigger_number(n):
    digits = sorted(str(n))
    candidates = sorted(int("".join(p)) for p in permutations(digits))

    for num in candidates:
        if num > n:
            return num
    return -1

a = int(input())
result = next_bigger_number(a)
print(result)

방법들은 각각의 상황에 따라 유용할 수 있습니다. 가장 효율적인 방법을 선택하여 사용하면 됩니다. 특히, 숫자의 자리 수가 많지 않은 경우에는 모든 경우의 수를 탐색하는 방법이 유용할 수 있지만, 자리 수가 많아질수록 효율적인 알고리즘을 선택하는 것이 중요합니다.

 

정답

 

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