백준 15655번: N과 M (6) with Java

N과 M (6)

 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

1 초

512 MB

23712

19868

16068

84.422%

문제

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

• N개의 자연수 중에서 M개를 고른 수열
• 고른 수열은 오름차순이어야 한다.

입력

첫째 줄에 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)

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

출력

한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.

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

예제 입력 1 복사

3 1
4 5 2

예제 출력 1 복사

2
4
5

예제 입력 2 복사

4 2
9 8 7 1

예제 출력 2 복사

1 7
1 8
1 9
7 8
7 9
8 9

예제 입력 3 복사

4 4
1231 1232 1233 1234

예제 출력 3 복사

1231 1232 1233 1234

 

 

---

 

 

어린왕자로 너무 심각하게 미뤄놓은 탓에 이제 일요일까지 풀로 하루에 한 문제씩 풀어야 한다....... 에휴!!!!!

21만원 주고 씨쁠을 산 것 같다는 슬픔 때문에 문제가 눈에 들어오질 않는다(근데 핑계인 듯 사실 원래 안 들어왔음)

 

 

N개의 자연수와 자연수 M이 주어졌을 때... 지금 나랑 말장난하나

아래 조건...

 

입력 N과 M

N개의 수

 

N개의 자연수 중 M개를 고른 수열(오름차순)

에휴

여름에는 컨디션이 왔다갔다하는 게 너무 싫어... 그냥 있으면 너무 더워서 열 오르고 에어컨 속에 있으면 첨엔 시원해서 좋은데 계속 있으면 뭔가 디멘터가 날 머리부터 빨아들이는 느낌이 난다니까... 기력이... 없다.......

응 그래도 해야해~

 

저번에 했던 것 같은데 이거..? 뭔 차이지 똑같은 조합 같은디 뭐가 다른 거임 그 때 DFS식으로 해보겠다고 해놓고 싹 까먹었었지 ㅎ

이건.. 기억이 안 나서 자료구조 시간에 했던 걸 찾아봐야한다ㅎㅎ;; 방문 표시하고서 다시 돌아가고 했던 것 같긴 함....

봐도 잘 모르겠어서 구글링해서 봤는데 코드가 다 똑같드라... 글고 보다 보니까 걍 그게 그거 같아서 작성하다 보니 그냥 다시 내 코드로 돌아온 듯...

걍 내 코드가 DFS였던 건가?ㅎ boolean 쓴 코드가 있어서 써보려고 했는데 잘 모르겟서...

 

import java.util.Arrays;
import java.util.Scanner;
public class BJ_15655 {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int n = sc.nextInt();	// 숫자 개수
		int m = sc.nextInt();	// 선택할 숫자 개수
		int[] nums = new int[n];	// n개의 숫자 입력받을 배열
		for (int i = 0; i < n; i++) {
			nums[i] = sc.nextInt();
		}	
		
		Arrays.sort(nums);	// 숫자 오름차순 정렬
		int[] pick = new int[m];	// m개 숫자 뽑아서 담아놓을 배열
		dfs(0, 0, nums, pick);	// start index 0, picked(뽑은 개수) 0, nums배열, 뽑아서 담을 배열 pick
		
		sc.close();
	}
	
	static void dfs(int start, int picked, int[] n, int[] p) {
		// 뽑은 개수랑 p.length(배열 크기, 뽑을 개수)랑 같으면 출력 후 return
		if (picked == p.length) {
			for (int num : p) {
				System.out.print(n[num] + " ");
			}
			System.out.println();
			return;
		}
		
		for (int i = start; i < p.length; i++) {
			p[i + 1] = i;
			dfs(start, picked + 1, n, p);
		}
		
	}
}

 

 

...그런데 안 보고 쳤더니 뭔가 배열에서 아슬아슬함을 느꼈다.

역시나

ㅎㅇ 나 런타임 에러

..

 

1차 수정

import java.util.Arrays;
import java.util.Scanner;
class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int n = sc.nextInt();	// 숫자 개수
		int m = sc.nextInt();	// 선택할 숫자 개수
		int[] nums = new int[n];	// n개의 숫자 입력받을 배열
		for (int i = 0; i < n; i++) {
			nums[i] = sc.nextInt();
		}	
		
		Arrays.sort(nums);	// 숫자 오름차순 정렬
		int[] pick = new int[m];	// m개 숫자 뽑아서 담아놓을 배열
		dfs(0, 0, nums, pick);	// start index 0, picked(뽑은 개수) 0, nums배열, 뽑아서 담을 배열 pick
		
		sc.close();
	}
	
	static void dfs(int start, int picked, int[] n, int[] p) {
		// 뽑은 개수랑 p.length(배열 크기, 뽑을 개수)랑 같으면 출력 후 return
		if (picked == p.length) {
			for (int num : p) {
				System.out.print(num + " ");
			}
			System.out.println();
			return;
		}
		
		for (int i = start; i < p.length; i++) {
			p[i] = n[i];
			dfs(start + 1, picked + 1, n, p);
		}
	}
}

 

응 출력 초과~

 

오늘은 틀렸습니다! 가 아니라 다른 문구를 두 개나 보게 됐다 참 새로운 기분인걸^^...

 

 

오류 발견

n 숫자를 전부 다 돌아야 하는데.. 반복문 루프 조건을 잘못 걸었다

import java.util.Arrays;
import java.util.Scanner;
class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int n = sc.nextInt();	// 숫자 개수
		int m = sc.nextInt();	// 선택할 숫자 개수
		int[] nums = new int[n];	// n개의 숫자 입력받을 배열
		for (int i = 0; i < n; i++) {
			nums[i] = sc.nextInt();
		}	
		
		Arrays.sort(nums);	// 숫자 오름차순 정렬
		int[] pick = new int[m];	// m개 숫자 뽑아서 담아놓을 배열
		dfs(0, 0, nums, pick);	// start index 0, picked(뽑은 개수) 0, nums배열, 뽑아서 담을 배열 pick
		
		sc.close();
	}
	
	static void dfs(int start, int picked, int[] n, int[] p) {
		// 뽑은 개수랑 p.length(배열 크기, 뽑을 개수)랑 같으면 출력 후 return
		if (picked == p.length) {
			for (int num : p) {
				System.out.print(num + " ");
			}
			System.out.println();
			return;
		}
		
		for (int i = start; i < n.length; i++) {
			p[picked] = n[i];
			dfs(i + 1, picked + 1, n, p);
		}
	}
}

 

n.length까지 반복문을 돌려야 n개의 숫자를 다 돌아볼 수 있다... 

p[picked]로 이미 뽑은 개수(picked)를 index로 삼고 n[i]를 넣어준다 그리고 1씩 더해서 다시 호출!

 

 

 

 

오늘도 크고 느린 성공!