BEAKJOON / 백준 - JAVA 15663번 N과 M (9)

2024.08.24기준 - 실버2

백준, BEAKJOON, BOJ, JAVA, 자바

 

풀이

이 문제는 주어진 자연수들로 수열을 만들 때, 수열의 중복없이 사전순으로 출력하는 문제입니다.

 

예제 2번을 통해 같이 설명을 진행하도록 하겠습니다.

//예제2
4 2
9 7 9 1

 

1. 입력된 자연수들을 리스트에 저장시켜 정렬을 해줍니다.

수를 미리 정렬을 시켜 수열을 출력할 때, 정렬된 수열을 차례로대로 출력하기 위해서 입니다.

st = new StringTokenizer(br.readLine());
for (int i = 0; i < n; i++) {
    list.add(Integer.parseInt(st.nextToken()));
}

// 수를 미리 정렬해 출력될 때 정렬된 수열이 출력되게 만듭니다.
Collections.sort(list);

2. 입력된 수들로 수열을 만들어 문자열로 출력을 해줍니다.

// 수열을 만들어 문자열로 출력해주는 함수.
private static void function(int len) {
    if (len == m) { // 길이가 같다면 출력
        StringBuilder sub = new StringBuilder();

        for (int i = 0; i < m; i++) {
            sub.append(str[i]).append(" ");
        }

        set.add(sub.toString());

    } else { // 같지 않다면 다음 인덱스 수를 설정
        for (int i = 0; i < n; i++) {
            if (!visit[i]) { // 사용하지 않은 수라면
                visit[i] = true;
                str[len] = list.get(i);
                function(len + 1);
                visit[i] = false; // 다 사용하고 난 후에는 다시 false로 체크
            }
        }
    }
}

 

 

 

코드

package Main;

import java.io.*;
import java.util.*;

public class Main {
	
	static int n, m;
	static int[] str;
	static List<Integer> list;
	static Set<String> set = new LinkedHashSet<>();
	static boolean[] visit;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringBuilder sb = new StringBuilder();
		StringTokenizer st = new StringTokenizer(br.readLine());
		n = Integer.parseInt(st.nextToken()); // 자연수의 개수
		m = Integer.parseInt(st.nextToken()); // 수열의 길이
		
		str = new int[m];
		list = new LinkedList<>();
		visit = new boolean[n];
		
		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < n; i++) {
			list.add(Integer.parseInt(st.nextToken()));
		}
		
		// 수를 미리 정렬해 출력될 때 정렬된 수열이 출력되게 만듭니다.
		Collections.sort(list);
		
		// 함수 호출
		function(0);
		
		set.forEach(s -> sb.append(s).append("\n"));
		bw.write(sb.toString());
		bw.flush();
		bw.close();
		br.close();
	}
	
	// 수열을 만들어 문자열로 출력해주는 함수.
	private static void function(int len) {
		if (len == m) { // 길이가 같다면 출력
			StringBuilder sub = new StringBuilder();
			
			for (int i = 0; i < m; i++) {
				sub.append(str[i]).append(" ");
			}
			
			set.add(sub.toString());
			
		} else { // 같지 않다면 다음 인덱스 수를 설정
			for (int i = 0; i < n; i++) {
				if (!visit[i]) { // 사용하지 않은 수라면
					visit[i] = true;
					str[len] = list.get(i);
					function(len + 1);
					visit[i] = false; // 다 사용하고 난 후에는 다시 false로 체크
				}
			}
		}
	}
}