BEAKJOON / 백준 - JAVA 15666번 N과 M (12)

2024.08.23기준 - 실버2

백준, BEAKJOON, BOJ, JAVA, 자바

 

풀이

이 문제는 주어진 자연수를 이용하여 겹치지 않는 수열을 만들어 사전순으로 출력하는 문제입니다.

 

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

// 예제2
4 2
9 7 9 1

 

1. 먼저 중복된 수를 제거해주기 위해 입력된 자연수들을 TreeSet에 저장을 해주었습니다.

TreeSet<Integer> set = new TreeSet<>(); // 수를 저장할 set (중복 제거)

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

TreeSet을 이용해 중복 제거와 정렬을 한 번에 이용했습니다.

 

2. 중복이 제거되면서 정렬이 된 set을 list화 시켰습니다.

// 중복이 제거된 수를 list로 변환
list = new LinkedList<>();
set.forEach(num -> list.add(num));

 

3. 정리된 리스트를 가지고 함수를 호출해 수열을 만들어 출력을 해줍니다.

// 수열을 만들어 문자열로 출력해주는 함수.
private static void function(int index, int len) {
    if (len == m) { // 길이가 같다면 출력
        for (int i = 0; i < m; i++) {
            sb.append(str[i]).append(" ");
        }
        sb.append("\n");

    } else { // 같지 않다면 다음 인덱스 수를 설정
        for (int i = index; i < list.size(); i++) {
            str[len] = list.get(i);
            function(i, len + 1);
        }
    }
}

 

 

 

 

코드

package Main;

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

public class Main {
	
	static int m;
	static int[] str;
	static List<Integer> list;
	static StringBuilder sb = new StringBuilder();
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int n = Integer.parseInt(st.nextToken()); // 자연수의 개수
		m = Integer.parseInt(st.nextToken()); // 수열의 길이
		
		TreeSet<Integer> set = new TreeSet<>(); // 수를 저장할 set (중복 제거)
		str = new int[m];
		
		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < n; i++) {
			set.add(Integer.parseInt(st.nextToken()));
		}
		
		// 중복이 제거된 수를 list로 변환
		list = new LinkedList<>();
		set.forEach(num -> list.add(num));
		
		// 함수 호출
		function(0, 0);
		
		bw.write(sb.toString());
		bw.flush();
		bw.close();
		br.close();
	}
	
	// 수열을 만들어 문자열로 출력해주는 함수.
	private static void function(int index, int len) {
		if (len == m) { // 길이가 같다면 출력
			for (int i = 0; i < m; i++) {
				sb.append(str[i]).append(" ");
			}
			sb.append("\n");
			
		} else { // 같지 않다면 다음 인덱스 수를 설정
			for (int i = index; i < list.size(); i++) {
				str[len] = list.get(i);
				function(i, len + 1);
			}
		}
	}
}