BAEKJOON : 15650, 15651, 15652, 4673, 1065

No. 15650

1. Problem

2. My Solution

• N과 M (1) 에서 구한 순열 중에 오름차순 수열만 출력
• 수열과 그 수열을 오름차순 정렬한 수열이 같다면 = 이미 오름차순 수열

import sys

def permutation(level):
    if level >= m:
        res.append(arr.copy())
    else:
        for i in range(1, n+1):
            if visited[i] == True:
                continue
            else:
                arr[level] = i
                visited[i] = True
                permutation(level+1)
                visited[i] = False

n, m = map(int,sys.stdin.readline().rstrip().split())

visited = [False] * (n+1)
arr = [0] * m
res = []

permutation(0)

for i in res:
    if i == sorted(i):
        print(' '.join(map(str,i)))

3. Others' Solutions

• 파이썬의 itertools 모듈의 combinations 함수를 이용하여 조합을 구함
• combinations 함수는 순열에서 중복된 것이 있으면 오름차순을 남기고 나머지 제거

4. Learned

• 파이썬의 itertools 모듈을 이용하면 permutations, ombinations 모두 구할 수 있으며 답은 오름차순으로 정렬 및 나열

---

No. 15651

1. Problem

2. My Solution

• N과 M (1) 에서 visited 를 없애서 백트레킹(가지치기) 제거

import sys

def permutation(level):
    if level >= m:
        res.append(arr.copy())
    else:
        for i in range(1, n+1):
            arr[level] = i
            permutation(level+1)

n, m = map(int,sys.stdin.readline().rstrip().split())

arr = [0] * m
res = []

permutation(0)

for i in res:
    print(' '.join(map(str,i)))

3. Others' Solutions

• itertools 모듈의 product 함수 이용 (Cartesian Product)

import s

n = sys.stdin.readline().rstrip()
res = 0

for i in range(len(n)-1):
    res += 9 * (10 ** i) * (i+1)

print(res + ((int(n) - (10 ** (len(n)-1)) + 1) * len(n)))

4. Learned

• itertools 모듈의 product 함수를 이용하면 주어진 수로 만들 수 있는 모든 수열을 구할 수 있음 (Cartesian Product)

---

No. 15652

1. Problem

2. My Solution

• 위에 15651 문제에서 구한 순열 중에 오름차순 수열만 출력
• 수열과 그 수열을 오름차순 정렬한 수열이 같다면 = 이미 오름차순 수열
• 모든 가능한 수열을 구하는 시간 + 각 수열을 정렬하는 시간 = 시간초과

• 해결 방법
• 수열을 생성할 때 이전 i 값에 대한 정보를 가진채로 생성해나감 (함수의 인자로 넘김)

import sys

def permutation(level,pre):
    if level >= m:
        res.append(arr.copy())
    else:
        for i in range(1, n+1):
            if  pre < i:
                arr[level] = i
            else:
                continue
            permutation(level+1,i)

n, m = map(int,sys.stdin.readline().rstrip().split())

arr = [0] * m
res = []

permutation(0,0)

for i in res:
    print(' '.join(map(str,i)))

4. Learned

• 위에 있는 오름차순 수열을 출력하는 유형의 문제에서 이전 i 값에 대한 정보를 가진채로 수열을 생성하면 시간 단축

---

No. 4673

1. Problem

셀프넘버 복습

2. My Solution

• set 을 이용하지 않고 숫자를 index로 갖는 리스트를 사용

nums = [False] * 10001
for i in range(1,10001):
    res = i
    for num in list(str(i)):
        res += int(num)
    if res <= 10000:
        nums[res] = True

for i in range(1,10001):
    if nums[i] == False:
        print(i)

3. Learned

• 알고리즘의 복잡도, 소요시간, 가독성이 비슷한 범위에서는 나에게 가장 편한 것을 사용해서 좀 더 빠르고 정확하게 문제를 풀자

---

No. 1065

1. Problem

한수 복습

2. My Solution

• 시간 ↑, 코드 ↓

import sys

n = int(sys.stdin.readline())

if n < 100:
    print(n)
    exit()

count = 99

for i in range(100,n+1):
    diff = set()

    for j in range(len(str(i))-1):
        diff.add(int(str(i)[j]) - int(str(i)[j+1]))
       
    if len(diff) == 1:
        count += 1
        
print(count)

3. Learned

• 시간이 조금 더 걸리더라도 심각한 정도가 아니라면 좀 더 가독성이 있고 이해하기 쉽게 구현하자