Yunsu's Log

BOJ 15663: N과 M (9)

7 min read

Note

백트래킹을 활용하여 중복된 원소가 있는 배열에서 중복 수열을 제거한 순열을 생성하는 문제입니다.

문제 링크

문제 요약

N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하세요.

  • N개의 자연수 중에서 M개를 고른 수열

  • 중복되는 수열을 여러 번 출력하면 안 됨

  • 수열은 사전 순으로 증가하는 순서로 출력

  • 입력: N, M과 N개의 자연수

  • 출력: 조건을 만족하는 수열을 한 줄에 하나씩 출력

핵심 아이디어

백트래킹과 중복 제거

이 문제는 백트래킹을 사용하여 순열을 생성하되, 중복된 수열을 제거해야 합니다.

입력 배열에 중복된 원소가 있을 수 있으므로, 같은 수열이 여러 번 생성될 수 있습니다.

중복 제거 방법

  1. 딕셔너리 사용: 생성된 수열을 문자열로 변환하여 딕셔너리에 저장
  2. 이전 값 체크: 정렬된 배열에서 같은 레벨에서 이전에 사용한 값과 같은 값은 건너뛰기

알고리즘 설계

1. 입력 정렬

arr = list(map(int, readline().split()))
arr.sort()
  • 사전순 출력을 위해 입력 배열을 정렬

2. 백트래킹

def dfs(v):
    if len(s) == m:  # M개를 모두 선택
        seq = []
        for i in range(len(s)):
            seq.append(arr[s[i]])
        
        s_str = ' '.join(map(str, seq))
        if s_str in dict:  # 이미 출력한 수열
            return
        else:
            print(s_str)
            dict[s_str] = True
        return
    
    for i in range(0, len(arr)):
        if i not in s:  # 아직 사용하지 않은 인덱스
            s.append(i)
            dfs(i)
            s.pop()

3. 중복 체크

딕셔너리를 사용하여 이미 출력한 수열인지 확인합니다.

전체 코드

import sys
readline = sys.stdin.readline
 
n, m = map(int, readline().split())
 
arr = list(map(int, readline().split()))
arr.sort()
 
dict = {}
s = []
def dfs(v):
    if len(s) == m:
        seq = []
        for i in range(len(s)):
            seq.append(arr[s[i]])
 
        s_str = ' '.join(map(str, seq))
        if s_str in dict:
            return
        else:
            print(s_str)
            dict[s_str] = True
        return
 
    for i in range(0, len(arr)):
        if not i in s:
            s.append(i)
            dfs(i)
            s.pop()
 
dfs(0)

코드 설명

1. 입력 처리

n, m = map(int, readline().split())
arr = list(map(int, readline().split()))
arr.sort()
 
dict = {}
s = []
  • arr: 입력 배열을 정렬 (사전순 출력을 위해)
  • dict: 출력한 수열을 저장하는 딕셔너리
  • s: 현재 선택한 인덱스들을 저장하는 리스트

2. 백트래킹 함수

def dfs(v):
    if len(s) == m:  # 기저 조건: M개를 모두 선택
        seq = []
        for i in range(len(s)):
            seq.append(arr[s[i]])  # 인덱스를 값으로 변환
        
        s_str = ' '.join(map(str, seq))  # 문자열로 변환
        if s_str in dict:  # 이미 출력한 수열
            return
        else:
            print(s_str)
            dict[s_str] = True
        return
    
    for i in range(0, len(arr)):
        if i not in s:  # 아직 사용하지 않은 인덱스
            s.append(i)  # 선택
            dfs(i)  # 재귀 호출
            s.pop()  # 되돌리기
  • 기저 조건: M개를 모두 선택했으면 수열을 생성하고 출력
  • 중복 체크: 딕셔너리에 이미 있는 수열이면 출력하지 않음
  • 선택과 되돌리기: 인덱스를 선택하고 재귀 호출 후 되돌리기

3. 인덱스 기반 선택

이 코드는 값이 아닌 인덱스를 사용하여 중복을 처리합니다:

  • 같은 값이 여러 개 있어도 인덱스가 다르면 다른 원소로 취급
  • 하지만 결과적으로 같은 수열이 생성될 수 있으므로 딕셔너리로 중복 제거

시간 복잡도

  • 시간 복잡도: O(N! / (N-M)! × M)

    • 가능한 순열의 수: N개에서 M개를 선택하는 순열
    • 각 순열을 문자열로 변환: O(M)
    • 딕셔너리 조회: 평균 O(1)

  • 공간 복잡도: O(N! / (N-M)! × M)

    • 딕셔너리에 저장되는 수열의 수
    • 각 수열의 길이: M

풀이 포인트

1. 인덱스 기반 선택

값이 아닌 인덱스를 사용하는 이유:

  • 같은 값이 여러 개 있어도 인덱스가 다르면 다른 원소로 취급
  • 예: [1, 1, 2]에서 첫 번째 1과 두 번째 1은 다른 원소

2. 중복 수열 제거

딕셔너리를 사용하여 이미 출력한 수열을 체크:

  • 수열을 문자열로 변환하여 딕셔너리의 키로 사용
  • 이미 출력한 수열이면 건너뛰기

3. 정렬

입력 배열을 정렬하여 사전순 출력을 보장:

  • 정렬된 배열에서 순서대로 선택하면 자동으로 사전순

개선된 코드

이전 값 체크를 사용하는 더 효율적인 방법:

import sys
readline = sys.stdin.readline
 
n, m = map(int, readline().split())
arr = list(map(int, readline().split()))
arr.sort()
 
s = []
used = [False] * n
 
def dfs():
    if len(s) == m:
        print(' '.join(map(str, s)))
        return
    
    prev = -1  # 이전에 사용한 값
    for i in range(n):
        if not used[i] and arr[i] != prev:
            prev = arr[i]
            used[i] = True
            s.append(arr[i])
            dfs()
            s.pop()
            used[i] = False
 
dfs()

장점:

  • 딕셔너리 없이도 중복 수열 제거 가능
  • 메모리 사용량 감소
  • 같은 레벨에서 이전 값과 같은 값은 건너뛰기

관련 문제

그래프 뷰

백링크