시프트 연산자를 통한 부분 집합 풀이

public class SubSet { 
	public ArrayList<String> subSet(String str) {
		Set<Character> split = new HashSet<>();
		ArrayList<String> result = new ArrayList<>();


		for(int i = 0; i < str.length(); i++) {
			split.add(str.charAt(i));
		}

		Object[] material = split
					.stream()
					.sorted()
					.toArray(Object[]::new);
		
		int n = material.length;
		// 1 << n은 1을 n번 왼쪽으로 시프트(shift)한 결과값을 나타낸다.
		// 1 << n은 2^n과 같은 값을 가지게 된다.
		for(int i = 0; i < (1 << n); i++) {
			ArrayList<String> subset = new ArrayList<>();
			for (int j = 0; j < n; j++) {
				// "비트 AND(&)"와 "비트 왼쪽 시프트(<<)" 연산자를 이용한 부분집합 생성을 위한 코드
				// (1 << j)는 j번째 비트를 1로 만든 값 i와 비트 AND 연산을 하면 i의 j번째 비트가 1인지 아닌지를 판단할 수 있다.
				if ((i & (1 << j)) > 0) {
					subset.add(material[j].toString());
				}
			}
			result.add(String.join("", subset));
		}

		Collections.sort(result);

		return result;
	}
}

AND연산자 '&'와 시프트 연산자 '<<', '>>' 를 사용했다.

AND연산자는 비교적 익숙하나 쉬프트 연산자는 해당 문제를 풀이하면서 처음 접하게 되었다.

 

 '1 << n'은 'n'번째 비트가 1인 이진수를 나타내며, 2의 'n'제곱과 같은 값을 가진다. 이진수에서 각 비트는 해당하는 자릿수에 대응되는 값을 2의 거듭 제곱으로 표현하므로, '1 << n'은 'n'번째 자리가 1이고 나머지 자리가 0인 이진수를 의미한다.

 

예를 들어, 'n'이 3일 경우 '1 << n'은 8을 나타내며, 이진수로는 '1000(2)' 로 나타낼 수 있다. (문과라 정확한 표기법은 잘 모르겠다;;.ㅋㅋ)

 

'i & (1 << j)' 는 'i'의 'j'번째 비트가 1인지 아닌지를 판단한다. 이진수에서 '&' 연산은 두 비트가 모두 1일 때 1을 반환하며, 그 외의 경우에는 0을 반환한다. 따라서 'i & (1 << j)'는 'i'의 'j' 번째 비트가 1이면 0이 아닌 값을 반환하며, 그 외에는 0을 반환한다.

 

'i'는 0부터 '2^n - 1'까지 반복하며, 각 'i'에 대해 'j'는 '0'부터 'n - 1'까지 반복한다. 따라서 'i & (1 << j)'는 'i'의 이진수표현에서 'j'번째 비트를 검사하는 것과 같다.

 

'i & (1 << j)'로 판단하여 'subset' 리스트에 'maerial' 배열의 'j'번째 요소를 추가하면, 'subset' 리스트는 'material' 배열의 모든 부분집합을 포함하게 된다.

 

그밖의 코드는 문제에서 String 문자열이 주어져 중복요소를 없애고 정렬하는 의미를 가지고 있으니 별로 신경쓰지 않아도 될 것 같다. 

 

근데 char에서 바로 String으로 바꾼 것이 아니라 Object를 거친 이유가

error: incompatible types: cannot infer type-variable(s) R

때문이다 ㅋㅋ;