[BOJ] 로또

[6603] 로또

• 집합 S와 k가 주어 졌을 때, 6개의 숫자를 고르는 모든 방법을 구하는 프로그램

 

 

Solution 

• 다음 순열을 사용해서 구하는 방법과 재귀를 사용해서 구하는 방법을 생각했다.
• 다음 순열을 사용할 때는 크기가 k인 a[] 배열에 공을 고르는 경우인 0을 6개, 고르지 않는 경우인 1을 k-6 개 담았다.
• 그리고 next_permutation()을 돌리면서 a[] 배열의 요소가 0인 index를 집합 S에서 찾아 출력하였다.
• StringBuffer를 사용했더니 시간이 아주 많이 줄었다.

 

 

소스코드 - 순열

import java.util.Scanner;

public class Main {
	public void go() {
		Scanner sc = new Scanner(System.in);
		while(true) {
			int n = sc.nextInt();
			if(n == 0)
				break;
			int[] a = new int[n];
			int[] s = new int [n];
			for(int i = 0; i<n;i++) {
				if(i > 5)
					a[i] = 1;
					s[i] = sc.nextInt();
			}
			int[] lotto = new int[6];
			do {
				int idx = 0;
			for(int i = 0; i<n;i++) {
				if(a[i] == 0) {
					lotto[idx++] = s[i];
				}
			}
			print(lotto);
			}while(next_permutation(a, n));
			System.out.println();
		}
		
	}

	public boolean next_permutation(int[] a, int n) {
		int i = n - 1;
		while (i > 0 && a[i - 1] >= a[i]) {
			i -= 1;
		}
		if (i <= 0)
			return false;
		int j = n - 1;
		while (a[i - 1] >= a[j]) {
			j -= 1;
		}
		swap(a, i - 1, j);
		j = n - 1;
		while (i < j) {
			swap(a, i, j);
			i += 1;
			j -= 1;
		}
		return true;
	}

	public void swap(int[] a, int i, int j) {
		int temp = a[i];
		a[i] = a[j];
		a[j] = temp;
	}

	public void print(int[] arr) {
		for (int i = 0; i < arr.length; i++) {
			System.out.print(arr[i] + " ");
		}
		System.out.println();
	}

	public static void main(String[] args) {
		Main main = new Main();
		main.go();
	}
}

 

소스코드 - 재귀

import java.util.Scanner;

public class Main {
	StringBuffer sb;

	public void go() {
		Scanner sc = new Scanner(System.in);
		while (true) {
			int n = sc.nextInt();
			if (n == 0)
				break;
			int[] s = new int[n];
			int[] lotto = new int[6];
			sb = new StringBuffer();
			for (int i = 0; i < n; i++) {
				s[i] = sc.nextInt();
			}
			dfs(s, 0, 0, lotto);
			System.out.println(sb.toString());
			
		}
		System.out.println();
	}

	public void dfs(int[] s, int count, int idx, int[] lotto) {
		if (count == 6) {
			for(int i = 0; i<6; i++) {
				sb.append(lotto[i]+ " ");
			}
			sb.append('\n');
			return;
		}
		if (idx >= s.length) {
			return;
		}
		lotto[count] = s[idx];
		dfs(s, count + 1, idx + 1, lotto);
		dfs(s, count, idx + 1, lotto);
	}

	public boolean next_permutation(int[] a, int n) {
		int i = n - 1;
		while (i > 0 && a[i - 1] >= a[i]) {
			i -= 1;
		}
		if (i <= 0)
			return false;
		int j = n - 1;
		while (a[i - 1] >= a[j]) {
			j -= 1;
		}
		swap(a, i - 1, j);
		j = n - 1;
		while (i < j) {
			swap(a, i, j);
			i += 1;
			j -= 1;
		}
		return true;
	}

	public void swap(int[] a, int i, int j) {
		int temp = a[i];
		a[i] = a[j];
		a[j] = temp;
	}

	public void print(int[] arr) {
		for (int i = 0; i < arr.length; i++) {
			System.out.print(arr[i] + " ");
		}
		System.out.println();
	}

	public static void main(String[] args) {
		Main main = new Main();
		main.go();
	}
}

 

근데 소스코드가 왜이렇게 못생기게 나오지,, 노답이네