[백준 15649,Java] N과 M(1) renew

문제분석

1부터 N까지 M개를 뽑는데 중복을 허락하지 않고, 오름차순으로 뽑아야한다.

 

재귀함수

 

위의 문장을 "숫자를 뽑는다"를 중심으로 생각해보자. 

  숫자를 언제까지 뽑아야하나 ? 현재까지 뽑은 숫자의 갯수가 M개 미만이면 숫자를 뽑는다

  뽑은 숫자의 갯수가 M개이면? 현재까지 뽑은 숫자를 출력한다

로 나타낼 수 있다. 

 

* 슷자를 뽑는다/ 숫자를 출력한다의 기준이 되는 상황을 생각해볼 것 

→ 현재까지 뽑은 숫자의 갯수

public static void pickNumber(뽑아야하는 숫자의 갯수, 현재까지 뽑은 숫자의 갯수) {
	if(현재까지 뽑은 숫자의 갯수 = 뽑아야 하는 숫자의 갯수) {
		현재까지 뽑은 숫자를 출력한다
	}
	else if(현재까지 뽑은 숫자의 갯수 > 뽑아야 하는 숫자의 갯수) {
		유효하지 않음
	}
	else {
		숫자를 뽑아야한다
	}
}

 

숫자뽑기

 

이제 else 부분의 "숫자를 뽑아야 한다"를 구현해보자. 

 

숫자는 1부터 N까지 숫자를 뽑는다. 이때 뽑은 숫자를 저장할 배열이 필요한 데, m개를 뽑으므로 크기가 m인 배열을 매개변수에 추가한다. 

 

public static void pickNumber(int n,int m, int pickCount,int[] numArray) throws Exception{
	if(pickCount == m) {
		//현재까지 뽑은 숫자를 출력한다
		for(int i = 0; i<numArray.length; i++) {
			bw.write(String.valueOf(numArray[i])+" ");
		}
		bw.write("\n");
	}
	else if(pickCount > m) {
		//유효하지 않음
	}
	else {
		//숫자를 뽑아야한다
		
	}
}

 

숫자를 뽑을 때 후보가 되는 숫자는 1부터 n까지이다. 뽑을 숫자를 선택했다면, 배열에 저장을 하는데, 이때 저장하는 인덱스는 pickCount(현재까지 뽑은 숫자의 갯수)가 된다. 바로 다음에 재귀호출을 하기때문이다. 

 

public static void pickNumber(int n,int m, int pickCount,int[] numArray) throws Exception{
	if(pickCount == m) {
		//현재까지 뽑은 숫자를 출력한다
		for(int i = 0; i<numArray.length; i++) {
			bw.write(String.valueOf(numArray[i])+" ");
		}
		bw.write("\n");
	}
	else if(pickCount > m) {
		//유효하지 않음
	}
	else {
		//숫자를 뽑아야한다
		for(int candiNum = 1; candiNum <=n; candiNum++) {
			numArray[pickCount] = candiNum; 
			pickNumber(n,m,pickCount+1, numArray);
		}
		
	}
}

 

다시말해, pickNumber( pickCount=0)가 호출될 때는 "현재까지 뽑은 숫자가 0개"라는 의미이므로 numArray에 숫자가 없다. pickNumer(pickCount=1)이 호출될 때는 "현재까지 뽑은 숫자가 1개"라는 의미이므로 numArray에 숫자가 1개 있다. 숫자가 1개 있다라는 의미는 index=0에 숫자가 있다는 뜻이므로 pickNumber(pickCount=1)이 호출되기전에 numArray[0] = 뽑은 숫자 를 저장한다. 

 

* 함수가 호출되었을 때의 상황을 생각할 것.

 

위와 같이 구현을 한 결과는 (n=4, m=2)

1 1 
1 2 
1 3 
1 4 
2 1 
2 2 
2 3 
2 4 
3 1 
3 2 
3 3 
3 4 
4 1 
4 2 
4 3 
4 4

 

가 된다. 중복을 구현하지 않았기 때문이다. 

 

중복처리

중복을 허락하지 않는다는 의미는 이전에 뽑은 숫자를 뽑지 않는다는 의미이다. 따라서 이전에 뽑은 숫자를 기록해둬야한다. 매개변수에 크기가 n+1이고 boolean타입의 배열을 추가한다.

 

 그러면 이제 numArray에 숫자를 넣기 전에, 이전에 뽑은 숫자인지를 확인해야한다. 

	public static void pickNumber(int n,int m, int pickCount,int[] numArray, boolean[] isExist) throws Exception{
		if(pickCount == m) {
			//현재까지 뽑은 숫자를 출력한다
			for(int i = 0; i<numArray.length; i++) {
				bw.write(String.valueOf(numArray[i])+" ");
			}
			bw.write("\n");
		}
		else if(pickCount > m) {
			//유효하지 않음
		}
		else {
			//숫자를 뽑아야한다
			for(int candiNum = 1; candiNum <=n; candiNum++) {
				if(!isExist[candiNum]) {
					isExist[candiNum] = true;
					numArray[pickCount] = candiNum; 
					pickNumber(n,m,pickCount+1, numArray,isExist);
					// -> pickNumber가 호출되고 return 되었을 때
					isExist[candiNum]= false;
				}
			
			}
		}
	}

여기서 주의해야할 점은 pickNumber(n,m,pickCount_1, numArray, isExist)가 호출되고 return이 되었을 때는 pickCount+1에서 pickCount로 return 될때다. 이때는 뽑았던 candiNum이 해제되므로 isExist[candiNum] = false로 바꿔줘야 한다.