BOJ 15663

2020-08-22

위 문제는 백준 사이트의 알고리즘 15663 문제에 관한 설명입니다.

Set을 사용한 방식과 그렇지 않은 방식으로 풀이가 되어있습니다.

문제

N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.

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

제한 사항

첫째 줄에 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)
둘째 줄에 N개의 수가 주어진다. 입력으로 주어지는 수는 10,000보다 작거나 같은 자연수이다.

출력

한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다.

중복되는 수열을 여러 번 출력하면 안되며,

각 수열은 공백으로 구분해서 출력해야 한다.

수열은 사전 순으로 증가하는 순서로 출력해야 한다.

처음 풀었던 방식

package baekjoon;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
	static StringTokenizer st;
	static BufferedWriter bw;
	static int N, M;
	static int[] input;
	static boolean[] visited;
	static int[] number;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		bw = new BufferedWriter(new OutputStreamWriter(System.out));
		st = new StringTokenizer(br.readLine());

		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());

		input = new int[N];
		number = new int[M];
		visited = new boolean[N];

		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < N; i++) {
			input[i] = Integer.parseInt(st.nextToken());
		}

		Arrays.sort(input);

		recur(0);
		bw.flush();
		bw.close();
	}

	static void recur(int count) throws IOException {
		if (count == M) {
			for (int i = 0; i < M; i++) {
				bw.append(number[i] + " ");
			}
			bw.newLine();
			return;
		}
		int before = 0;
		for (int i = 0; i < N; i++) {
			if (visited[i])continue;
			else if(!visited[i] && (i==0||before !=input[i])) {
				before = input[i];  
				number[count] = input[i];
				visited[i] = true;
				recur(count + 1);
				visited[i] = false;
			}
			
		}
	}
}

이 방식의 문제 해결에 대해서 설명하겠습니다.

해결책1

이번 문제에선 중복의 경우가 조금 까다로운 문제 였습니다.

input에 숫자들을 입력을 받고 정렬을 합니다.

그렇게 했을 때 예제입력2의 값을 예로 들어서 input에는

1 7 9 9 라는 순으로 값이 들어가 있겠죠?

이 후 재귀 함수로 넘어가게 된다면

해당 숫자에 방문했을 때(visited 가 true)와 이전 값이 방문한 값인지 등의 조건들을 확인 후

아니라면 순열의 방식을 따라서 숫자들을 number에 저장시켜 출력하면 됩니다.

해결책2

바로 Set 컬렉션 클래스 입니다.

Set 인터페이스를 구현한 모든 Set 컬렉션 클래스는 다음과 같은 특징을 가집니다.

요소의 저장 순서를 유지하지 않습니다.
같은 요소의 중복 저장을 허용하지 않습니다.

크게 2가지로 나뉘는 데 첫번째는 HashSet입니다.

1. HashSet 클래스

Set 컬렉션 클래스에서 가장 많이 사용되는 클래스 중 하나입니다.

JDK 1.2부터 제공된 HashSet 클래스는 해시 알고리즘(hash algorithm)을 사용하여 검색 속도가 매우 빠릅니다.

이러한 HashSet 클래스는 내부적으로 HashMap 인스턴스를 이용하여 요소를 저장합니다.

HashSet 클래스는 Set 인터페이스를 구현하므로,

요소를 순서에 상관없이 저장하고 중복된 값은 저장하지 않습니다.

만약 요소의 저장 순서를 유지해야 한다면 JDK 1.4부터 제공하는 LinkedHashSet 클래스를 사용하면 됩니다.

문제에 LinkedHashSet을 적용시켜서 풀어봅시다.

package baekjoon;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedHashSet;
import java.util.StringTokenizer;
 
public class Main {
 
    static int N,M;
    static int[] array;
    static boolean[] visited;
    static LinkedHashSet<String> set = new LinkedHashSet<>();
    static StringBuffer sb = new StringBuffer();
    
    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());
        
        array = new int[N];
        visited = new boolean[N];
        st = new StringTokenizer(br.readLine());
        
        for (int i = 0; i < N; i++) {
            array[i] = Integer.parseInt(st.nextToken());
        }

        Arrays.sort(array);

        recur(0,"");

        for(String s : set) {
            sb.append(s+"\n");
        }

        System.out.print(sb.toString());
    }
    
    static void recur(int count, String str) {
        
        if(count == M) {
            set.add(str);
            return ;
        }
        
        for (int i = 0; i < N; i++) {
            if(visited[i]) continue;
            visited[i] = true;
            recur(count+1,str+array[i]+" ");
            visited[i] = false;
        }
    }
 
}

array에 정렬된 값들이 재귀함수에 들어가고, 순열의 과정을 거치는데

set 함수가 있음으로써 중복되는 값들이 걸러집니다.

LinkedHashSet 클래스를 사용하면 저장 순서를 유지할 수 있다했습니다.

만약 저장 요소 순서를 고려하지 않고 HashSet 클래스를 사용하면 어떤 결과가 나올까요?

아래와 같습니다.

HashSet을 사용했을 때

LinkedHashSet을 사용했을 때

그렇습니다.

삽입한 순서와 다르게 나오는 HashSet과

삽입 순서에 따라 순서를 만들어 주는 LinkedHashSet를 확인할 수 있었습니다.

2. TreeSet 클래스

TreeSet 클래스는 데이터가 정렬된 상태로 저장되는 이진 검색 트리(binary search tree)의 형태로 요소를 저장합니다.

이진 검색 트리는 데이터를 추가하거나 제거하는 등의 기본 동작 시간이 매우 빠릅니다.

JDK 1.2부터 제공되는 TreeSet 클래스는 NavigableSet 인터페이스를 기존의 이진 검색 트리의 성능을 향상시킨 레드-블랙 트리(Red-Black tree)로 구현합니다.

TreeSet 클래스는 Set 인터페이스를 구현하므로, 요소를 순서에 상관없이 저장하고 중복된 값은 저장하지 않습니다.

NavigableSet은 SortedSet을 확장한 인터페이스입니다.

TreeSet 관련 예제는 다음에 알아봅시다!

잘못된 사항이 있다면 댓글로 달아주세요! 확인하자마자 수정하겠습니다..

N과 M(9)

« Programmers-멀쩡한 사각형 Programmers-땅따먹기 »