백준 15656번: N과 M (7) with Java

N과 M (7)

 

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

1 초

512 MB

23278

18250

14923

78.778%

문제

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

• N개의 자연수 중에서 M개를 고른 수열
• 같은 수를 여러 번 골라도 된다.

입력

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

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

출력

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

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

예제 입력 1 복사

3 1
4 5 2

예제 출력 1 복사

2
4
5

예제 입력 2 복사

4 2
9 8 7 1

예제 출력 2 복사

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

예제 입력 3 복사

3 3
1231 1232 1233

예제 출력 3 복사

1231 1231 1231
1231 1231 1232
1231 1231 1233
1231 1232 1231
1231 1232 1232
1231 1232 1233
1231 1233 1231
1231 1233 1232
1231 1233 1233
1232 1231 1231
1232 1231 1232
1232 1231 1233
1232 1232 1231
1232 1232 1232
1232 1232 1233
1232 1233 1231
1232 1233 1232
1232 1233 1233
1233 1231 1231
1233 1231 1232
1233 1231 1233
1233 1232 1231
1233 1232 1232
1233 1232 1233
1233 1233 1231
1233 1233 1232
1233 1233 1233

 

 

---

 

복날이라 애슐리 퀸즈 개많이 먹구 야식은 치킨 먹었다 ㅎㅎ 그러면 해보자..

 

?얜 뭐 시리즈가 끝이 없네

N과 M 시리즈 몇까지 있는 거임?!!

그래 N개의 자연수 자연수 M... N개의 자연수 중 M개를 고른 수열, 같은 수를 여러 번 골라도 된다.

출력을 보니 중복 순열이다. 1 7 7 1 둘다 나옴

 

그러면

해보자...

 

머여 벌써 3주차임 이거 뭔가 잘못됐어... 한 달동안 뭘 한거지 나는??? 

 

암튼 1차 코드

import java.util.Arrays;
import java.util.Scanner;
public class BJ_15656 {
	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];
		for (int i = 0; i < n; i ++) {
			nums[i] = sc.nextInt();
		}
		
		Arrays.sort(nums);	// 오름차순 정렬
		int[] picked = new int[m];
		pick(0, nums, picked);
		
		sc.close();
	}
	
	static void pick(int count, int[] nums, int[] picked) {
		if (count == picked.length) {
			for (int p : picked) {
				System.out.print(p + " ");
			}
			System.out.println();
			return;
		}
		
		for (int i = 0; i < nums.length; i++) {
			picked[count] = nums[i];
			pick(count + 1, nums, picked);
		}
	}
}

 

시간 초과란다!

테스트 케이스는 다 맞게 작동하는 것 같던데.. 역시 스캐너가 문제인가??

 

일단 오늘 제출은 글렀다! 

 

수정 완료~

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.Arrays;

class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        String[] nm = br.readLine().split(" ");	// n하고 m 한 줄로 입력 받아서 공백 기준으로 n m 나눔
        int n = Integer.parseInt(nm[0]);	// 첫 번째가 n(숫자 개수)
        int m = Integer.parseInt(nm[1]);	// 두 번째가 m(고를 개수)
        
        String[] numStr = br.readLine().split(" ");	// 숫자 입력받음, n개의 숫자를 공백으로 구분
        int[] nums = new int[n];	// n개의 숫자 담을 배열
        for (int i = 0; i < n; i++) {
            nums[i] = Integer.parseInt(numStr[i]);
        }	// String으로 입력받았기 때문에 int형으로 바꾸어서 배열에 담아줌
        
        Arrays.sort(nums); // 오름차순 정렬
        int[] picked = new int[m];	// 뽑은 숫자 담을 배열
        StringBuilder sb = new StringBuilder();	// 뽑은 숫자들 한 번에 모아서 출력
        pick(0, nums, picked, sb);
        
        System.out.println(sb.toString());
    }
    
    static void pick(int count, int[] nums, int[] picked, StringBuilder sb) {
        // 다 뽑았으면(count가 picked 길이와 같으면) 뽑은 숫자를 sb에 append한다.
    	if (count == picked.length) {
            for (int i = 0; i < picked.length; i++) {
                sb.append(picked[i]).append(" ");
            }	
            sb.append("\n");
            return;
        }
        
        for (int i = 0; i < nums.length; i++) {
            picked[count] = nums[i];
            pick(count + 1, nums, picked, sb);
        }
    }
}

 

<수정한 부분>

1. Scanner 대신 BufferedReader를 사용

Scanner는 누르면 바로바로 전달되는 거고 BufferedReader는 버퍼 이용해서 꽉 차거나 특정 개행 문자가 입력되면 한 번에 전달되는 거란다. 대신 String으로 고정되어 따로 가공 필요함!

지금까지 와 첫째 줄~ 둘째 줄~ 이렇게 언급하는 지 몰랐는데 지금 알게 됐다.. 저걸 쓰면 저게 중요한 정보였다. split을 해야하기 때문에...

2. 바로 출력하지 않고 StringBuilder를 사용하여 덧붙여서 나중에 한 번에 출력

이것도 같이 검색하다 알게 되었다. 출력 작업은 상대적으로 시간이 많이 소요되어 StringBuilder로 출력을 모아서 한 번에 수행하면 시간을 줄일 수 있다고 함.. 꼭 기억해서 다음 문제에도 입출력 이렇게 써야지

 

 

 

 

성공~~~!!!!!!!