문제 설명
•
문자열 S를 재배치해서 만들 수 있는 서로 다른 행운의 문자열의 개수를 구하는 문제
◦
행운의 문자열이란 인접해 있는 문자가 서로 같지 않아야 한다.
예제 입력/출력
•
입력1
aabbbaa
Python
복사
•
출력1
1
Python
복사
•
입력2
ab
Python
복사
•
출력2
2
Python
복사
•
입력3
aaab
Python
복사
•
출력3
0
Python
복사
•
입력4
abcdefghij
Python
복사
•
출력4
3628800
Python
복사
제약 조건
•
문제 풀이
풀이1
•
모든 순열에 대해 살펴본 후에, 중복된 결과를 수학적으로 처리해주는 방법 (브루트 포스)
◦
상한
◦
최악의 경우 N=10일 때, 30,628,800회의 연산 필요
•
모든 순열에 대해 살펴본 후에 중복된 결과를 제거하는 것이 중요하다.
◦
예를 들어, [a,a,b]의 순열에 대한 결과는 다음과 같다.
('a', 'a', 'b')
('a', 'b', 'a')
('a', 'a', 'b')
('a', 'b', 'a')
('b', 'a', 'a')
('b', 'a', 'a')
◦
위의 예에서 보듯이, 중복된 순열이 다수 존재한다.
•
중복된 순열을 제거해주기 위한 방법으로 크게 3가지를 생각했다.
1.
check 리스트를 사용하여, 순열 중복 방지
2.
set 함수 사용
3.
중복된 결과를 수학적으로 처리
•
각 방법의 결과는 다음과 같다.
check 리스트를 사용하여, 순열 중복 방지 (시간 초과)
set 함수 사용 (메모리 초과)
중복된 결과를 수학적으로 처리
풀이2
•
문자의 종류를 기준으로 각 자리를 완성하는 방법 (백트래킹)
◦
상한
◦
최악의 경우 N=10일 때, 30,628,800회의 연산 필요
•
문자열에서 각 문자의 개수를 센 다음, 재귀함수를 사용해 앞에서부터 문자를 채워 넣은 다음에 마지막에 행운의 문자열이라면 cnt 개수 증가
◦
이에 대한 모든 경우의 수를 체크
풀이 코드
풀이1 - 브루트 포스
풀이2 - 백트레킹
알아두면 좋은 내용들
set 와 list 의 메모리 사용 차이
ord() 함수와 chr() 함수