[BAEKJOON]15666 N과 M (12)

문제 요약

• 알고리즘 분류: 백트래킹
• 난이도: Silver3
• 문제내용:
  • 같은 수를 여러 번 골라도 된다.
  • 길이가 K인 수열 A가 A1 ≤ A2 ≤ ... ≤ AK-1 ≤ AK를 만족하고 M개의 수열을 예제와 같이 중복없이 사전순으로 출력해라.
• 사이트 주소: https://www.acmicpc.net/problem/15666

15663번: N과 M (9)

 

문제풀이

 이번 문제는 백트레킹 문제이다. 백트레킹 관련 자세한 내용은 아래의 사이트에 참조하면된다.

https://jih3508.tistory.com/84

[알고리즘 이론] 백트래킹(Backtracking)

 이것 풀기전에 아래의 문제를 풀고 보는것을 추천한다. 그 이유는 아래 두 문제를 썩어서 내는 문제라서 밑에 두 문제를 풀고 보면 이해하기가 더 쉬울것이다.

• N과  M(8): https://jih3508.tistory.com/115

[BAEKJOON]15657 N과 M (8)

• N과  M(9): https://jih3508.tistory.com/116

[BAEKJOON]15663 N과 M (9)

접근 방법 

  이번에 출력순서가 아래봐 같다.

1. 수열의 크기 순으로 출력
2. 수열의 결과들은 중복없게 출력

 1번조건은 N과 M(8)이고 2번 조건은 N과 M(9) 유형인 문제이다.

다시 1번 조건은 배열/리스트를 정렬한후 재귀 함수 파라미터를 배열을 시작할 index와 깊이로 한다음 시작할 index부터 반복문으로 돌리면 해결된다.

2번 조건은 수열이 다 만들어지면 list/배열에 포함되어 있는지 여부를 하면되는데 일반 적으로 list/배열에 담고 비교하면 O(n^2)이 걸려서 set으로 포함 여부를 판단하면 O(1)걸려서 set에다가 저장을 해야한다. 하지만 set에 list/배열 저장하기가 힘들어서 결과를 문자열로 만들어서 저장하면된다.

 

Code

Python

def NM(x, p =[]):
    if(len(p) == M):
        string = ' '.join(map(str, p))
        if string not in set_list:
            print(string)
            set_list.add(string)
        return
    for i in range(x, N):
        NM(i, p + [array[i]])
        
N, M = map(int, input().split())
array = sorted(list(map(int, input().split())))
set_list = set({})
NM(0)

 Java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;
import java.util.StringTokenizer;

public class Main {
		
	static int[] array, result;
	static int N, M;
	static Set<String> set = new HashSet<String>();
	static StringBuilder sb = new StringBuilder();
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		st = new StringTokenizer(br.readLine());
		array = new int[N];
		result = new int[M];
		for(int i = 0; i < N; i++) {
			array[i] = Integer.parseInt(st.nextToken());
		}
		Arrays.sort(array);
		
		NM(0, 0);
		System.out.println(sb);
	}
	
	public static void NM(int x, int k) {
		StringBuilder NMsb = new StringBuilder();
		if (k == M) {
			for(int i = 0; i < M; i++) {
				NMsb.append(result[i]).append(" ");
			}
			if(!set.contains(NMsb.toString())) {
				sb.append(NMsb).append("\n");
				set.add(NMsb.toString());
			}
			return ;
		} 
		
		for(int i = x; i < N; i++) {
			result[k] = array[i];
			NM(i, k + 1);
		}
	}

}