Java - [백준] 15649번 : N과 M (1)

1. 문제

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

• 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열
• https://www.acmicpc.net/problem/15649

15649번: N과 M (1)

---

2. 생각

 본 문제는 길이가 M인 수열을 구해야 하기 때문에 state-space tree를 이용하여 해가 될 수 있는 모든 노드에 직접 방문하여 찾아야 하기 때문에 1) Depth-first search, 2) BackTracking, 3) Recursion 알고리즘을 이용했다.

 

두 가지의 배열(includedNumber, include)을 준비했다.

• includedNumber는 1부터 N까지 자연수 중에서 선택받은 자연수들의 집합을 담고 있는 배열
• include는 1부터 N까지 자연수 중에서 어떤 숫자가 선택받았는지를 boolean으로 표현한 배열

 

먼저 Recursion을 사용하기 위해서 Base case와 Recursion case를 정의할 필요가 있다.

• Base case는 "어떤 조건을 만족할 때까지 Recursion을 실행할 것인가?"를 알려줘야 하기 때문에 level 변수를 도입하여 level 변수를 통해 "현재 몇 개의 숫자들이 뽑혔으며, 앞으로 얼마만큼 숫자를 더 뽑야하는가?"를 알려준다. 
  만약 level 변수가 0부터 시작해서 점차 값을 증가하다가 M과 동일해지면 "M개 숫자를 모두 뽑았다."를 의미하기 때문에 더 이상 숫자를 뽑을 필요 없이 선택받은 숫자들(includedNumber)를 출력하면 된다.
• Recursion는 Base case에 수렴하는 방향으로 진행해야 하며, Base case 조건에 충족하지 못하면 실행된다. for문을 이용하여 0부터 N까지 숫자들 중 하나를 선택하는데, 단, include 배열을 이용하여 해당 숫자가 이미 선택된 숫자인지를 확인하고, 선택해야 한다. 

 

위 내용들을 바탕으로 수열을 찾는 메서드(findSequence)를 구현하면 다음과 같다.

private static void findSequence(int level, int n, int m) {
       // ** Base case
       if(level == m) {
            for(int element: includedNumber)
                System.out.print(element+" ");
			
            System.out.println();
            return;
       }
		
       // ** Recursion case
       for(int i=0; i<n; i++) {
            if(!include[i]) {
               include[i] = true;
               includedNumber[level] = i+1;
               findSequence(level+1, n, m);
               include[i] = false;
            }
        }
}

위 코드를 작성함에 있어 주의해야 할 점이 있다. (무의식적으로 사용했다가 예상과 다르게 작동하여 시간을 잡아 먹었다.)

• Recursion case에서 1부터 N사이의 숫자들 중 하나를 선택하고, level 변수 값을 1씩 증가시킨 다음, 재호출하게 되는데, 이과정에서 level++를 하게 되면 Recursion을 수행하고 해당 level로 돌아왔을 때, 1이 증가된 level로 저장되기 때문에 예상과 다른 알고리즘을 수행하게 된다. 따라서 level++ 대신 level+1를 이용하는 것이 오류를 막을 수 있다.

---

3. 풀이 및 코드 분석

첫 번째 시도) 시간 초과 

import java.util.Scanner;

public class Try1 {
	static boolean[] include;
	static int[] number;
	static int[] sequence;
	public static void main(String[] args) {
		// *** Get N and M, Initialization.
		number = getNumber();
		include = new boolean[number[0]];
		sequence = new int[number[0]];
		
		// *** Find sequence & print sequence.
		findTheSequence(0);
	}
	
	// *** Get N & M
	private static int[] getNumber() {
		Scanner scan = new Scanner(System.in);
		int[] input = new int[2];
		
		while(true) {
			input[0] = scan.nextInt();
			input[1] = scan.nextInt();
			
			if(input[0]<1 || input[0]>8 || input[1]<1 || input[1]>8)
				System.out.println("The numbers is out of bounds.");
			else if(input[1]>input[0])
				System.out.println("N is less than M.");
			else 
				break;
		}
		
		return input;
	}

	// *** Find sequence & print that.
	private static void findTheSequence(int level) {
		if(level == number[1]) {
			int index = 0;
			while(index<number[1] && sequence[index]!=0) {
				System.out.printf("%d ", sequence[index]);
				index++;
			}
			System.out.println();
			return;
		}
		
		for(int j=0; j<include.length; j++) {
			if(!include[j]) {
				include[j] = true;
				sequence[level] = j+1;
				findTheSequence(level+1);
				include[j] = false;
				sequence[level] = 0;
			}		
		}
		return;
	}
}

• 첫 번째 시도는 이클립스에서 정상적으로 작동하였지만, 백준에서 시간 초과로 인해 문제가 발생하였다.
• 0 ≤ M ≤ N ≤ 8 조건을 충족하시키기 위해 getNumber 메서드를 이용했지만, "이 과정에서 시간이 오래 소요되었는가?" 싶어서 getNumber 메서드를 제외하고, 다시 작성해 보았다.
• N과 M값을 한 번에 관리하기 위해 number라는 배열에 넣고 관리하였지만, N과 M을 꺼내는 과정에서도 시간이 오래 소요된 것으로 추정하여 N과 M을 전역 변수에서 매개 변수로 전환하여 재작성해 보았다.

 

 두 번째 시도) 시간 초과 

import java.util.Scanner;

public class Main {
	static int[] includedNumber;
	static boolean[] include;
	public static void main(String[] args) {
		// *** Get N, M & Initialization.
		Scanner scan = new Scanner(System.in);
		int n = scan.nextInt();
		int m = scan.nextInt();
		include = new boolean[n];
		includedNumber = new int[m];
		
		// *** Find sequences.
		findSequence(0, n, m);
	}
	
	// *** Find the sequence & print that.
	private static void findSequence(int level, int n, int m) {
		if(level == m) {
			for(int i=0; i<m; i++)
				System.out.print(includedNumber[i]+" ");
			
			System.out.println();
			return;
		}
		
		for(int i=0; i<n; i++) {
			if(!include[i]) {
				include[i] = true;
				includedNumber[level] = i+1;
				findSequence(level+1, n, m);
				include[i] = false;
			}
		}
	}

• 코드를 단순화 했음에도 시간 초과 문제가 발생하여 이번에는 Base case의 출력 과정에서 인덱스를 이용한 출력에서 advanced for문을 이용하여 코드를 재작성을 하였다.

세 번째 시도) 성공

import java.util.Scanner;

public class Main {
	static int[] includedNumber;
	static boolean[] include;
	public static void main(String[] args) {
		// *** Get N, M & Initialization.
		Scanner scan = new Scanner(System.in);
		int n = scan.nextInt();
		int m = scan.nextInt();
		include = new boolean[n];
		includedNumber = new int[m];
		
		// *** Find sequences.
		findSequence(0, n, m);
	}
	
	// *** Find the sequence & print that.
	private static void findSequence(int level, int n, int m) {
		if(level == m) {
			for(int element: includedNumber)
				System.out.print(element+" ");
			
			System.out.println();
			return;
		}
		
		for(int i=0; i<n; i++) {
			if(!include[i]) {
				include[i] = true;
				includedNumber[level] = i+1;
				findSequence(level+1, n, m);
				include[i] = false;
			}
		}
	}

---

4. 메모

• 본 문제를 통해 문제를 해결하는 것 뿐만 아니라 알고리즘의 시간 복잡도를 최소화 할 수 있도록 생각하고, 작성해야 할 필요가 있다고 생각했다.