IT-garden

문제

1부터 N까지의 수로 이루어진 순열이 있다. 이때, 사전순으로 바로 이전에 오는 순열을 구하는 프로그램을 작성하시오.

사전 순으로 가장 앞서는 순열은 오름차순으로 이루어진 순열이고, 가장 마지막에 오는 순열은 내림차순으로 이루어진 순열이다.

N = 3인 경우에 사전순으로 순열을 나열하면 다음과 같다.

• 1, 2, 3
• 1, 3, 2
• 2, 1, 3
• 2, 3, 1
• 3, 1, 2
• 3, 2, 1

입력

첫째 줄에 N(1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄에 순열이 주어진다.

출력

첫째 줄에 입력으로 주어진 순열의 이전에 오는 순열을 출력한다. 만약, 사전순으로 가장 처음에 오는 순열인 경우에는 -1을 출력한다.

예제 입력과 출력

알고리즘 분류

순열

정답

n = int(input())
a = list(map(int, input().split()))

def _10973(a):
    n=len(a)-1
    i = n
    
    while i>0 and a[i-1]<=a[i]: 
        i-=1

    if i==0:
        return False
    
    j = n
    while a[i-1]<=a[j]:
        j-=1
    
    a[i-1],a[j]=a[j],a[i-1]
    
    j=n
    while i<j:
        a[i],a[j]=a[j],a[i]
        i+=1
        j-=1
    return True

if _10973(a) is True:
    for i in a:
        print(i, end=' ')
else:
    print(-1)

백준 알고리즘 10973번 : www.acmicpc.net/problem/10973

문제

1부터 N까지의 수로 이루어진 순열이 있다. 이때, 사전순으로 다음에 오는 순열을 구하는 프로그램을 작성하시오.

사전 순으로 가장 앞서는 순열은 오름차순으로 이루어진 순열이고, 가장 마지막에 오는 순열은 내림차순으로 이루어진 순열이다.

N = 3인 경우에 사전순으로 순열을 나열하면 다음과 같다.

• 1, 2, 3
• 1, 3, 2
• 2, 1, 3
• 2, 3, 1
• 3, 1, 2
• 3, 2, 1

입력

첫째 줄에 N(1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄에 순열이 주어진다.

출력

첫째 줄에 입력으로 주어진 순열의 다음에 오는 순열을 출력한다. 만약, 사전순으로 마지막에 오는 순열인 경우에는 -1을 출력한다.

예제 입력과 출력

알고리즘 분류

순열

정답

n = int(input())
a = list(map(int, input().split()))

def _10972(a):
    n=len(a)-1
    i = n
    
    while i>0 and a[i-1]>=a[i]:
        i-=1

    if i==0:
        return False
        
    j = n
    while a[i-1]>=a[j]:
        j-=1
    
    a[i-1],a[j]=a[j],a[i-1]
    
    j=n
    while i<j:
        a[i],a[j]=a[j],a[i]
        i+=1
        j-=1
    return True

if _10972(a) is True:
    for i in a:
        print(i, end=' ')
else:
    print(-1)

백준 알고리즘 10972번 : https://www.acmicpc.net/problem/10972

문제

N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.

• N개의 자연수 중에서 M개를 고른 수열

입력

첫째 줄에 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)

둘째 줄에 N개의 수가 주어진다. 입력으로 주어지는 수는 10,000보다 작거나 같은 자연수이다.

출력

한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.

수열은 사전 순으로 증가하는 순서로 출력해야 한다.

예제 입력과 출력

정답

from itertools import permutations

n,m=map(int,input().split())

a=list(map(int,input().split()))

a=list(permutations(a, m))

a=sorted(list(set(a)))

for i in a:
    print(*i)

백준 알고리즘 15663번 : www.acmicpc.net/problem/15663

문제

N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다.

• N개의 자연수 중에서 M개를 고른 수열

입력

첫째 줄에 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)

둘째 줄에 N개의 수가 주어진다. 입력으로 주어지는 수는 10,000보다 작거나 같은 자연수이다.

출력

한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.

수열은 사전 순으로 증가하는 순서로 출력해야 한다.

예제 입력과 출력

정답

from itertools import permutations

n,m=map(int,input().split())

a=list(map(int,input().split()))
a.sort()

a=list(permutations(a,m))

for i in a:
    print(*i)

백준 알고리즘 15654번 : www.acmicpc.net/problem/15654

문제

자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.

• 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열

입력

첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)

출력

한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.

수열은 사전 순으로 증가하는 순서로 출력해야 한다.

예제 입력과 출력

정답

from itertools import permutations

n,m=map(int,input().split())

a=list(permutations(range(1,n+1),m))

for i in a:
    print(*i)

백준 알고리즘 15649번 : www.acmicpc.net/problem/15649

순열(permutation)은 순서를 고려해서 선택한 경우의 수를 의미합니다.

from itertools import permutations

permutations(인자(반복 가능한 것 ex. 리스트, 문자열),뽑을 개수)

순열의 기본 구조입니다.

순열의 개수는 n! / (n-r)! 입니다.

1, 2, 3 숫자 3개가 있다고 할 때 순서를 고려해서 2장을 뽑으면 다음과 같습니다.
개수 : 3! / (3-2)! = 6 / 1 = 6
(1, 2), (1, 3), (2, 1), (2, 3), (3, 1), (3, 2)

순서를 고려한다는 것은 (1, 2)와 (2, 1)를 다른 것으로 생각한다는 의미입니다.

from itertools import permutations

p=list(permutations([1, 2, 3], 2))

# 출력>>[(1, 2), (1, 3), (2, 1), (2, 3), (3, 1), (3, 2)]
print(p)

a=[1,2,3]

for i in permutations(a):
    # 출력>>(1, 2, 3) (1, 3, 2) (2, 1, 3) (2, 3, 1) (3, 1, 2) (3, 2, 1)
    print(i,end=' ')
    
for i in permutations(a,2):
    # 출력>>(1, 2) (1, 3) (2, 1) (2, 3) (3, 1) (3, 2) 
    print(i,end=' ')

조합(combination)은 순서를 고려하지 않고 선택한 경우의 수를 의미합니다.

from itertools import combinations

combinations(인자(반복 가능한 것 ex. 리스트, 문자열),뽑을 개수)

조합의 기본 구조입니다.

조합의 개수는 n! / r! (n-r)! 입니다.

1, 2, 3 숫자 3개가 있다고 할 때 순서를 고려하지 않고 2장을 뽑으면 다음과 같습니다.
개수 : 3! / 2! (3-2)! = 6 * 2 = 3
(1, 2), (1, 3), (2, 3)

순서를 고려하지 않는다는 것은 (1, 2)와 (2, 1)를 같은 것으로 생각한다는 의미입니다.

from itertools import combinations

c=list(combinations([1, 2, 3], 2))

# 출력>>[(1, 2), (1, 3), (2, 3)]
print(c)

a=[1,2,3]
    
for i in combinations(a,2):
    # 출력>>(1, 2) (1, 3) (2, 3)  
    print(i,end=' ')

중복 가능한 순열은 product를 이용해 표현할 수 있습니다.

from itertools import product

product(인자(반복 가능한 것 ex. 리스트, 문자열), repeat)

중복 가능한 순열의 기본 구조입니다.

중복 가능한 순열의 개수는 n^r 입니다.

repeat라는 인자를 통해 앞의 인자를 반복해서 뽑는 기능입니다.

1,2,3 숫자 3개가 있다고 할 때 순서를 고려해서 2장을 뽑으면 다음과 같습니다.
개수 : 3^2 = 9
(1, 1), (1, 2), (1, 3), (2, 1), (2, 2), (2, 3), (3, 1), (3, 2), (3, 3)

from itertools import product

a=list(product([1, 2, 3], repeat=2))

# 출력>>[(1, 1), (1, 2), (1, 3), (2, 1), (2, 2), (2, 3), (3, 1), (3, 2), (3, 3)]
print(a)

중복 가능한 순열은 combinations_with_replacement를 이용해 표현할 수 있습니다.

from itertools import combinations_with_replacement

combinations_with_replacement(인자(반복 가능한 것 ex. 리스트, 문자열),뽑을 개수)

중복 가능한 조합의 기본 구조입니다.

중복 가능한 조합의 개수는 (n+r-1)! / r! / (n-1)!  입니다.

1,2,3 숫자 3개가 있다고 할 때 순서를 고려해서 2장을 뽑으면 다음과 같습니다.

개수 : (3+2-1)! / 2! / (3-1)! = 24 / 2 / 2 = 6 
(1, 1), (1, 2), (1, 3), (2, 2), (2, 3), (3, 3)

from itertools import combinations_with_replacement

a=list(combinations_with_replacement([1,2,3], 2))

# 출력>>[(1, 1), (1, 2), (1, 3), (2, 2), (2, 3), (3, 3)]
print(a)