Stack 으로 조합 구현하기.

 

- 목차

 

아이디어.

스택으로 조합을 구현하는 방법에 대해서 설명하고자합니다.

1 부터 5 까지의 숫자를 3개의 조합들로 나타내려고 합니다.

저희가 원하는 결과는 아래와 같습니다.

 

< 1 ~ 5 의 조합 케이스 >

1,2,3
1,2,4
1,2,5
1,3,4
1,3,5
1,4,5
2,3,4
2,3,5
2,4,5
3,4,5

 

각 조합의 자릿수는 첫번째, 두번째, 세번째 로 표현할 때,

조합 1,2,3 은 첫번째 값이 1, 두번째 값이 2, 세번째 값이 3 입니다.

조합 3,4,5 은 첫번째 값이 3, 두번째 값이 4, 세번째 값이 5 입니다.

 

조합이 구성되는 패턴을 보면 세번째 값이 1씩 증가하게 되고

세번째 값이 최대값에 도달하게 되면 두번째 값이 1씩 증가하는 방식입니다.

 

이는 N 번째 값을 1 씩 increment 하고, N 번째 값이 최대치에 도달하게되면 N - 1번째 값을 1씩 increment 합니다.

이를 스택으로 표현해보면, 아래와 같습니다.

 

1) Stack 의 Top 을 1 씩 Increment 한다.

2) Stack 의 Top 이 최대치에 도달하면, Pop 한다.

3) Stack 의 Size 가 R 보다 작으면 Top 보다 1이  큰 값을 Push 한다.

 

numbers = [0,1,2,3,4,5]
maxNumber = 5;
Stack stack = new Stack()
List combinations = new List();
R = 3

// 초기값 세팅
stack.push(0);
stack.push(1);
stack.push(2);

while (stack.isNotEmpty) {
	if stack.isFull {
    	combinations.add(stack);
    } 

    top = stack.pop();
    if top < maxNumber {
    	for (i = top + 1; i <= maxNumber; i++) {
        	stack.push(i);
        }
    } 
   
}

 

 

 

 

 

구현.

N 개의 수들 중에서 R 개의 조합을 구성하는 방식은 아래와 같습니다.

 

< 코드 예시 >

public static void main (String[] args) {
    int[] a = new int[]{1,2,3,4,5};
    int n = a.length;
    int r = 3;

    Stack<Integer> stack = new Stack<>();
    List<int[]> combs = new ArrayList<>();
    for ( int i = 0; i < r; i++) {
      stack.push(i);
    }

    while (!stack.isEmpty()) {
      if (stack.size() == r) {
        int[] combination = new int[r];
        for ( int i = 0; i < r; i++) {
          combination[i] = stack.get(i);
        }
        combs.add(combination);
      }

      int top = stack.pop();

      if (top < n) {
        for (int i = top + 1; i < n && stack.size() < r; i++) {
          stack.push(i);
        }
      }
    }

    for (int[] combination: combs) {
      System.out.printf("%s %s %s \n", combination[0], combination[1], combination[2]);
    }
  }

 

 

< 출력 >

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