toBin_알고리즘

오늘 포스팅한 문제는 2진수 표현 방법 중, 1의 갯수를 표현하되, 큰 수부터 표현하는 것입니다.

처음에는 Permutation으로 접근하여 경우의 수를 모두 뽑아낸 다음에 대소비교를 통해 출력하려 했으나,

크기 비교 후 표현하기에는 코드가 깔끔하지 못했고, 뿐만 아니라 출력시엔 10진수로 고려하여 출력하기 때문에 

0011과 같은 값을 표현하기에는 어려움이 많았습니다.

이러한 우여곡절을 겪은 뒤에, 재귀 호출을 통해서 1을 먼저 배열에 넣고 1의 갯수를 넘어설 경우 배열에 0을 넣을 수 있도록

구현하는 것입니다. 

이 후에는 배열의 길이가 전체 설정한 길이만큼 커졌을 때 (같을 경우) 배열 요소를 출력하고 함수를 리턴하는 것입니다.

여기서 리턴될 때 1의 갯수를 체크하는 변수부분이 호출 전 상태로 들어오기 때문에 1의 갯수보다 적음에도 불구하고 

한 번 더 출력 함수가 호출될 것입니다.

따라서 출력 함수에서도 한 번 더 1의 갯수를 체크해서 함수를 리턴해주는 코드를 정리해줘야 합니다.

코드는 다음과 같습니다.

  

---

// inx는 앞서 설명한 배열(d라고 표현)의 인덱스 값이며 해당 인덱스 값에 1을 먼저 넣는다.

// count는 1의 갯수입니다. 따라서 inx의 값이 count를 넘어갈 경우 

// 1을 넣어주는 재귀적 호출을 그만 두어야 합니다. 

// 리턴해주고 난 뒤 배열(d)에 0을 넣는 작업을 진행합니다.

// 다음과 같은 작업을 지속적으로 재귀하여 (recursion) inx의 값이 전체 길이와 같아질 경우 

// 배열 전체를 프린트한다. 

// 하지만 앞서 설명하였듯이, 배열 전체를 프린트할때, 리턴을 

private static void dfs(int inx, int count){

if(inx == length){ // 전체 길이 

printAll();

return;

}

if(count > num){ // 1의 갯수가 넘어갈 때 (기존보다) 재귀적 호출 리턴!

return;

}

d[inx] = 1;

dfs(inx+1,count+1);

d[inx] = 0;

dfs(inx+1,count);

}

---

[전체 코드] 

import java.util.Scanner;

public class toBin2 {

private static Scanner scanner;

private static int length;

private static int num;

private static int[] d;

public static void main(String[] args) {

// TODO Auto-generated method stub

scanner = new Scanner(System.in);

length = scanner.nextInt();

num = scanner.nextInt();

d = new int[length];

binaryFunc(0, 0);

}

static void printAll(int len) {

if (len != num)

return;

for (int i = 0; i < length; i++)

System.out.print(d[i]);

System.out.println("");

}

static void binaryFunc(int inx1, int len) {

if (len > num)

return;

if (inx1 == length) {

printAll(len);

return;

}

d[inx1] = 1;

binaryFunc(inx1 + 1, len + 1);

d[inx1] = 0;

binaryFunc(inx1 + 1, len);

}

}

---

감사합니다.