BOJ 15663번: N과 M(9)

www.acmicpc.net/problem/15663

15663번: N과 M (9)

아이디어:

사전 순으로 증가하는 순서로 출력해야 하므로 입력으로 주어진 N개의 자연수 정렬.

중복되는 수열을 체크할 방법이 관건.

-> 일단 각 숫자가 사용되었는지 여부를 확인하는 isUsed = [N]

-> 중복되는 수열인지 체크는 바로 이전에 출력한 수열과 동일한지 체크하면 되지 않을까?(X)

-> 테스트 케이스 2번째의 경우처럼 똑같은 원소가 여러 개 있을 경우 중복 체크가 안됨

-> 바로 이전에 선택한 숫자와 같은지 여부만 확인하면 되는 거였음.. 로직을 잘못 짠 거였음.. 새로운 level에 들어가면 temp를 0으로 초기화 시켜야 함.

 

즉,

1. 정렬

2. 중복 확인 isUsed, temp -> temp는 새로운 레벨에 들어갈 때마다 초기화.

 

코드:

import sys
n, m = map(int, sys.stdin.readline().split())
arr = list(map(int, sys.stdin.readline().split()))

arr.sort()
result = [0]*m
isUsed = [False]*n

def solve(level):
    if (level==m):
        for i in result:
            print(i, end=" ")
        print()
        return
    temp = 0 #새로운 level에 들어왔을 때는 temp 초기화
    for i in range(n):
        if (isUsed[i]==False and arr[i]!=temp):
            isUsed[i]=True
            temp=arr[i]
            result[level]=arr[i]
            solve(level+1)
            isUsed[i]=False
            
solve(0)

어려웠던 부분:

중복 여부를  확인한느 방법, 이전에 사용한 숫자와 겹치게 하지 않으면 된다는 아이디어는 떠올렸는데 로직을 구현하는 부분이 어려웠다.