[CLASS 4]백준 15663번, 15666번 - N과 M

15663번 : N과 M (9)

 

또다시 나온 N과 M문제이다. Itertools내장 모듈을 쓴다면 엄청 쉽게 풀리겠지만 그러면 재미없으므로 그냥 풀어보았다.

 

내 코드:

# dawitblog.tistory.com
def comb(length):
    if length == m:
        temp = len(resultList)
        resultList.add(tuple(result))
        if temp != len(resultList):
            print(*result)
    else:
        for i in range(n):
            if not used[i]:
                used[i] = True
                result.append(l[i])
                comb(length+1)
                result.pop()
                used[i] = False

n, m = map(int,input().split())
# 각각의 결과를 임시로 저장
result = []
# 이미 사용한 인덱스 확인용
used = [False] * n
# 이미 출력한 결과
resultList = set()
l = sorted(list(map(int,input().split())))
comb(0)

 

몇 번의 시행착오와 시간초과를 거치고 나온 코드이다. 이미 사용한 인덱스는 used 리스트에 추가해서 다시 사용하는것을 막았다. 중복되는 결과가 있으면 안되기 때문에 set을 사용했다. 그리고 출력은 set에 성공적으로 해당 결과가 추가되었을 때마다 그 결과를 추가해주면 된다.

 

15666번 : N과 M (12)

 

비슷한 문제인데 출력 조건만 비내림차순으로 바뀌었다.

 

내 코드:

# dawitblog.tistory.com
def comb(length,startIdx):
    if length == m:
        temp = len(resultList)
        resultList.add(tuple(result))
        if temp != len(resultList):
            print(*result)
    else:
        for i in range(startIdx,n):
                result.append(l[i])
                comb(length+1,i)
                result.pop()

n, m = map(int,input().split())
# 각각의 결과를 임시로 저장
result = []
# 이미 출력한 결과
resultList = set()
l = sorted(list(map(int,input().split())))
comb(0,0)

 

이미 사용한 인덱스를 다시 사용해도 되기 때문에 used 리스트는 필요가 없어졌다. 따라서 더 간편한 코드로 완료할 수 있다.