[B]BOJ1342 행운의 문자열 - 메모리 초과 코드, 시간 초과 코드 , 정답 코드

Brute force 코드 1 : 메모리 초과

BOJ_1342_permu.py

1. from itertools import permutations 라이브러리로

입력받은 문자열에 대해서 모든 가능한 순열 조합들을 뽑아내었다.

그리고 이 조합들에 set을 취해 중복 조합을 걸러내었다.

1.1 문자열의 길이가 최대 10일 경우,

후보 case는 약 360만 개 (=10!)

1.2 후보 case의 인접 문자 2개씩 비교하는 비교 연산을 9 (10-1)라고 하면

총 약 3200만번의 연산이 필요.

2. 순열 조합의 문자들을 순회하며

인접한 문자열끼리 비교를 통해 행운의 문자열인지 아닌지 판별했다.

# 메모리 초과

# Test case 4 경우 2.9s 소요

# 다른 방법 필요

비효율성

permutation으로 순열을 뽑으면

aabaa라는 문자열에서 각각의 a가 모두 다른 문자로 간주되기 때문에

많은 양의 중복 case가 발생한다.

단계1에서 permutation결과에 다시 set을 취하는 과정에서

많은 계산으로 인한 시간이 소요된 것으로 보인다.

대안

- 확률과 통계에서 배웠던 방법으로 중복 순열 Case를 처리하거나( N! / (a! b!) )

- 아래와 같이 set() 자료형에 tuple객체를 추가함으로서 중복을 처리할 수 있다.

s = set()

s.add(tuple(candidate)) # candidate는 permutation에서 나온 case

개수만 필요한 경우 전자, 중복 처리된 데이터까지 필요하다면 후자를 사용.

전자의 경우 dict를 통해

문자열에 어떤 문자가 몇 개 존재하는지 기록해도 좋지만,

원 문자열의 각 문자가 'a'~'z'라는 조건이 있으므로

set()으로 문자열 조합 하나하나를 비교하기 보다

수학 공식을 이용하여 산술적으로 처리하는 것이 더 빠르다.

Brute force 코드 2 : 통과

BOJ_1342_permu2.py

1. 인접 문자들 조건을 만족하는 문자열 개수를 모두 센 후

2. 개수에서 산술적으로 중복된 문자열을 제거함

위 대안의 전자에 해당하는 방법이다.

( N! / (a! b!) )

Backtracking : 시간 초과

BOJ_1342_recur.py

접근 및 로직은 정답이지만 로직에 비효율성이 있음.

Backtracking :  정답 코드

BOJ_1342_recur-correct.py

시간 초과 코드에서 수정한 것

1. 재귀 함수를 돌기 전, 기반 데이터를 만들 때
set() 작업과 count대신

set 자료형 변수에 리스트를 순회하며 추가했으며

그 순회 for문 내에서 문자 개수를 세서 dict에 추가하는 로직을 사용.

2. if choose문을 for문 안에서 검사하도록 함.

Brute force vs Backtracking

- Brute force는 모든 경우의 수를 순회하며 조건에 맞는지 검사.

- Backtracking은 답이 될 수 있는 경우만 만들어감.