[백준 알고리즘] 15663. N과 M (9)

 

 

 

 

🎈 숫자를 문자열로 바꾸지 않고 정렬해 오류가 떴다.

1, 2, 3, 4 정렬할 때는 문자나 숫자나 차이가 없지만, 100, 10, 110 같은 경우는 문자와 숫자의 정렬이 달라짐을 간과했었다.

 

 

주로 list를 사용해와서 이번에도 set을 사용할때 list로 넣어준다음 중복제거를 위해 set을 사용했는데,

 

 

'unhashable type' 이라는 에러가 발생했다.  찾아보니 list 말고 tuple에는 해시 값이 있어 tuple을 사용하니 잘 통과됐다.

 

 

 

정렬하고 -> 중복값제거하고 -> 다시 정렬하는게 비효율적이라고 느껴져 다른 풀이를 찾아봤었다.

 

 

t라는 값을 두어 이전의 값을 저장한 뒤 새로운 조합을 만들때 값을 비교하는 풀이가 신박했다.

 

 

 

 

from sys import stdin

n, m = map(int, stdin.readline().split())
## str 정렬순서랑 int정렬은 다름 그러므로 int로 바꿔주는거 필수
nums = list(map(int, stdin.readline().split()))
check = [0] * n
select = [0] * m
ans = []

def comb(idx):
    if idx == m:
        ans.append(tuple(select))
        return
    for i in range(n):
        if check[i] == 0:
            check[i] = 1
            select[idx] = nums[i]
            comb(idx+1)
            check[i] = 0

comb(0)
ans = list(set(ans))
ans.sort()

for i in range(len(ans)):
    for j in range(m):
        print(ans[i][j], end=" ")
    print()



######## 다른 풀이법


def f(idx):
    if idx == m:
        print(' '.join(ans))
        return
    t = 0
    for j in range(n):
        if check[j] or t == nums[j]:
            continue
        check[j] = 1
        ans[idx] = nums[j]
        f(idx+1)
        check[j] = 0
        t = ans[idx]

n, m = map(int, input().split())
nums = sys.stdin.readline().split()
nums.sort(key=int)
ans, check = [0]*m, [0]*n
f(0)