문제 이해

1~N까지 자연수 중 M개를 고르는 모든 경우의 수를 출력하는 것이다.
이 때 조건은 2가지이다.

(1) 같은 수를 여러 번 골라도 된다 ⇒ (2,2)도 선택 가능

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

(ex)
(1,3)과 (2,2)가 존재할 때, 2보다 1이 먼저 오기 때문에 (1,3)이 먼저 와야 한다
(1,3)과 (1,4)가 존재할 때, 1은 동일하지만 4보다 3이 먼저 오기 때문에 (1,3)이 먼저 나와야 한다

문제 풀이

모든 경우의 수를 구하는 것이기 때문에 Brute-Force Algorithm 밖에 사용할 수 밖에 없다.

이 때 (1,x)일 경우 (1,1) ⇒ (1,2) ⇒ (1,3) ⇒ .... 으로 모두 Search 이후 (2,1)로 이동하는 것이기 때문에 재귀 함수를 이용하여 (1,x)인 경우를 모두 Search 이후 (2,x)를 모두 Search 하는 방식으로 구현하는 것이 좋지 않을까 라는 생각이 들었다.

또한 (1,1)을 출력하기 위한 재귀함수가 나온 이후 (1,2)를 출력하기 위해서는 뒤쪽 1 원소값을 빼내고 그 위치에 2 data를 넣어야 한다.

마지막에 입력시킨 data를 뺀 이후 다시 data를 입력시켜야 한다는 구조로 보았을 때 FIFO구조를 활용한 Stack이 적절하다는 생각이 들어 Stack을 활용하여 구현하기로 하였다.

코드

import java.util.*;

public class Main {
	
	static StringBuilder sb = new StringBuilder();
	
	static void rec_fun(int N, int length, Stack<Integer> tmp) {
        // length : Stack에서 더 들어갈 수 있는 공간 길이
        // (ex) Stack은 [1,2]이고, 총 3개 data가 들어갈 수 있다면 
        //      length = 3 - 2 = 1
		
		if(length==0) { 
        // Stack의 공간에 더 data가 들어갈 필요가 없는 경우
        // 지금까지 Stack에 쌓여있던 data를 모두 출력해야 한다.
			String answer = tmp.toString();
			sb.append(answer.substring(1,answer.length()-1)
            .replaceAll(",","")+"\n");
			return;
		}
        
        // Stack은 toString을 통해 표현하면 [1, 2, 3]처럼 원소가 표현되는
        // 것을 볼 수 있다.
        // 문제는 1 2 3의 결과값을 원하므로 ,를 replaceAll을 통해 없애고,
        // substring을 통해 '['와 ']'를 없애는 방법을 사용하였다.
		
		for(int i =1;i<=N;i++) {
			tmp.add(i);               //Stack에 (1,x)과정을 추가하는 과정
			rec_fun(N,length-1, tmp); //(1,x)에서 x에 data를 채우는 재귀함수
			tmp.pop();                
            //(2,x) 과정을 수행하기 위해 미리 들어와 있던 1 값을 pop 시킴
		}
	}
	
	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int M = sc.nextInt();
		
		rec_fun(N,M, new Stack<Integer>());
	
		System.out.println(sb.toString());
	}
}

• 참고로 Eclipse로 코딩할 때 코딩을 연습하는 사람이라면 자동 완성 기능을 꺼 놓는 것을 추천한다. 글쓴이 또한 자동 완성 기능을 꺼 놓고 코딩을 하고 있으며, 물론 힘들겠지만 이렇게 코드를 짜다보면 사용하는 라이브러리에 대한 활용도와 이해도가 조금 더 깊어지는 것을 느낄 수 있다.

결과

• 컴파일 에러 이유 : import java.util.*; 구문을 빼먹었다. java.lang 이외의 Library를 활용할 때는 꼭 import 시켰는지 확인하도록 하자.