부분집합 경우의 수 알고리즘.
문자들 중 일부 문자를 생략하고
나타낼 수 있는 모든 경우의 수를 출력하는 알고리즘이다.
A, B, C, D 와 같이 4개의 문자가 있다고 하자. (쉽게 설명하기 위해 4개로 설정)
이 문자들 중 일부 또는 전부를 생략하고자 할 때, (또는 생략을 안 할 수도)
모든 경우의 수를 표현하고자 한다.
생략할 수 있는 문자를 다음과 같이 표현할 수 있다.
B와 C를 생략하고자 한다면 -> A {B} {C} D
그렇다면 다음과 같은 경우의 수가 발생한다.
A B C D
A B D
A C D
A D
총 4가지의 경우의 수가 발생.
간단해 보일 수 있지만, 전체 문자와 생략 문자의 수가 많아지면 복잡하다는 것을 알 수 있다.
예:: {A} B {C} {D} E F {G} H I {J} {K} L {M} {N}...
이것을 알고리즘으로 구현하고자 한다.
기본 원리는 다음과 같다.
...
1. 문자열 입력 받기 -> A {B} {C} D
2. 파싱하여 배열에 저장 -> String[]
3. 일반 문자와 생략 문자 구분 -> 일반 문자는 0, 생략 문자는 1로 표현
4. 컴패어 바이너리 테이블을 만든다(핵심)
- 2의 n승 만큼의 크기로 바이너리 테이블 생성
(n은 문자 수, 위의 예에선 4개:A,B,C,D) => 2의 4승은 16.. 0000, 0001, ... ~ 1111까지
5. 위 3번에서 생성된 문자(0110)를 컴패어 바이너리 테이블과 비교(핵심)
- 5번의 생성 문자와 컴패어 바이너리 테이블과 비교하였을 때,
0의 위치는 반드시 같아야 하며, 1은 검사하지 않는다.
※ 다음과 같은 결과가 나온다
일반문자 :: 0110
비교문자 :: 0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111
- 0000, 0010, 0100, 0110 문자만 패스되었다.
6. 패스된 문자에서 0에 해당하는 문자만 출력한다.
7. 0000 : ABCD, 0010 : ABD, 0100 : ACD, 0110 : AD
8. 출력된 문자는 리스트, 배열 등에 담아서 각자 알아서 처리하기~!
코딩에 앞서 본인은 문자 파싱(split)을 위해 다음과 같은 조건을 적용해 보았다.
1. 각 문자는 스페이스(공간)로 구분한다. -> A B C D
2. 생략가능 문자는 중괄호로 묶어 준다. -> {A} {B} ...
3. 일반 문자(비생략)는 0으로, 생략 문자는 1로 표현한다. -> A {B} = 0 1