(JAVA) 백준 1342번 : 행운의 문자열

https://www.acmicpc.net/problem/1342

1342번: 행운의 문자열

 

백트래킹 문제.

 

 

 

내 풀이법은 다른 사람들과는 조금 달랐다.

 

 

 

매커니즘

---

 

1. 문자열을 toCharArray() 해서 Char 배열에 저장.

 

2. 행복한 문자열을 만들기 위한 백트래킹 실행

** 이 때, 첫 시작 문자를 정하기 위해 문자열의 처음부터 끝까지 한 번씩 백트래킹 함수 초기 호출함

 

3. 백트래킹 시 StringBuilder를 인자로 사용해서 char 추가/삭제에 용이하도록 함. 

 

4. boolean 배열을 통해

 1) 이전에 이 문자를 넣은 경우 - 다음 인덱스 문자로 진행

 2) 이전에 이 문자를 넣지 않은 경우 - 해당 문자를 선택하는 경우/선택하지 않은 경우

 

5. 문자 선택 시 StringBuilder의 끝 문자와 선택하는 문자와 비교

 1) 같은 경우 다음 인덱스 문자로 진행

 2) 다른 경우에만 해당 문자를 선택하는 경우/선택하지 않은 경우로 나뉨

 

6. HashSet 사용해서 중복된 문자열 실시간 제거 가능(HashSet은 데이터의 중복 X)

 

7. HashSet의 Size 리턴

 

 

이렇게 진행하니

 

맙소사!

서버가 이상한 줄 알았다.

 

 

실제로 각기 다른 문자 10개가 있으면

 

3628800 개의 문자열을 저장해야 한다고 한다.

 

 

그러니 서버가 어케버티누!!

 

 

 

 

조금의 해결 방법을 찾던 중

Factorial(팩토리얼) 방식으로 해결하는 사람들이 많았다.

 

그래서 순열의 공식과 성질을 이용해

중복의 개수만 제거하려고

 

Factorial을 사용한다.

 

그래서 이를 사용하기 위해

각 알파벳이 몇 번 이용되었는지 판단한 다음

 

2번 이상인 횟수들의 Factorial을 저 원소에 제거한다.

 

 

 

 

그러니 20배 이상 줄지 않겠는가?!

 

말문이 불여일건.

 

 

소스코드

---