240226 [BOJ/백준] 15650. N과 M (2)

 

https://www.acmicpc.net/problem/15650

15650번: N과 M (2)

---

나의 코드

# n과 m(2)

def n_m():
    if len(lst) == M:
        a = sorted(lst)      # 고른 수열이 오름차순이어야 해서 오름차순으로 저장
        if a not in result:  # 빈 리스트(result)에 수열이 없을 경우에 append
            result.append(a)
            return

    else:
        for i in range(1, N+1):
            if i not in lst:
                lst.append(i)
                n_m()
                lst.pop()


N, M = map(int, input().split())
lst = []
result = []

n_m()

for i in range(len(result)):
    print(*result[i])

 

결과

---

이제 시간초과가 걸릴까봐 PyPy3로 먼저 제출하고 Python3로 제출한다. 재귀함수를 통한 백트래킹과정이라 그런지 걸리는 시간이 적은 것 같다. 입력하는 데이터도 1에서 8까지의 자연수로 작기도 하고!

n과m(1) 문제로 재귀함수로 리스트를 뽑아내는 과정을 이해했지만 오름차순의 결과만 추가된 것인데도 꽤 애먹었다.

이유 1. 일단 함수니까 return을 lst로 받아주고 함수밖에서 lst를 처리해주려고 했다. 하지만 함수 중간에 리스트들이 만들어지는 것이었고 그것들을 출력하면서 n과m(1)문제를 해결했기에 이번 문제에서는 lst가 만들어지면 다른 리스트에 넣어주었다.

이유 2. 오름차순을 적용하는 과정에서 나는 항상 lst.sort()와 같은 함수(?)를 썼는데 그렇게 되면 그 값을 저장하지는 못했다. 그래서 오름차순의 값을 저장할 수 있는 함수 sorted(lst)를 변수에 저장했고 그것을 빈 리스트에 저장할 수 있도록 했다.

이유 3. 오름차순된 리스트를 중복된 값을 처리하기 위해 set함수를 쓰려고 했지만 set은 원소만을 추가할 수 있는 것 같다. 원소 1개 추가는 add라는 메서드를, 2개 이상의 원소 추가는 update([1, 2, 3])과 같은 메서드방식을 사용한다. 아무튼 set으로 리스트 중복은 제거할 수 없어서 조건문으로 리스트에 값이 없을 때만 추가하는 방식을 썼다.

N과 M(2)는 N과 M(1)에서 약간의 조건이 추가되었지만 기초적인 지식과 구조를 더욱 탄탄히 할 수 있는 좋은 문제였다고 생각한다. 지금보니 추가된 것도 얼마 없는 것 같은데...?ㅎㅎㅎㅎ