[백준] 1342 - 행운의 문자열

[문제링크]

1342번: 행운의 문자열

 

0. 주어진 문자로 만들수 있는 모든 순열 중, 조건을 만족하는 갯수를 구하는 문제

  - 조건 1. 인접한 문자는 달라야 한다

  - 조건 2. 최종 결과가 달라야 한다 (a 2개로 aa', a'a을 만들수 있지만, 둘은 같은것으로 취급한다)

 

1. 순열의 i번째 자리를 정할 때 이전 문자정보를 참고해 다른 문자만 사용한다면, 조건 1번은 해결할 수 있다

  - 0번째 자리에서 참조할 값으로는 입력값(알파벳)이 아닌 아무 문자나 주면 된다

 

2. 조건 2번의 경우, 여러번 등장하는 같은 문자를 다른 문자로서 사용하기 때문에 발생한다.

  - 즉, i번째 자리에 한번 a 문자를 사용했다면 a가 또 등장해도 사용하지 않으면 해결할 수 있다

 

3. 이를 위해, 한번 사용한 문자의 정보를 저장해두어 중복 사용하는것을 막았다 (bitmask)

 

4. 2/3번에서 걸러지지 않고 끝까지 완료된 순열만 count해주면 된다

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main{
	public static void main(String[] args)throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		s = br.readLine().toCharArray();
		isC=new boolean[s.length];
		cntLuck=0;
		lucky(0, ' ');
		System.out.println(cntLuck);
	}
	
	static char[] s;
	static boolean[] isC;
	static int cntLuck;
	
	static void lucky(int cnt, char prev) {
		if(cnt==s.length) {
			cntLuck++;
			return;
		}
		int bitMask=0;
		for (int i = 0; i < s.length; i++) {
			if(!isC[i] && s[i]!=prev && ( (bitMask&1<<(s[i]-'a')) == 0)) {
				//not used + not same with prev
				isC[i]=true;
				bitMask|=1<<(s[i]-'a');
				lucky(cnt+1, s[i]);
				isC[i]=false;
			}
		}
	}
	
	static int pint(String s) {
		return Integer.parseInt(s);
	}
}

결과 화면