[파이썬] 1759 암호 만들기 feat. 백트래킹

[파이썬] 15649 N과 M (1) feat 띠용하다!

 

저번 글을 읽고 자신감이 붙어서 이번에는 골드5가 적힌 백트래킹 문제로 가보았다

 

 

결론은 n, k 그리고 k 만큼의 알파벳이 주어지고, 그 알파벳들을 

 

n개 만큼의 길이를 가진 리스트로 쭉 정렬해서 출력하는 것이다

 

근데 막상 보니 15649 문제와 매우 비슷하다

 

이전 15649 문제를 이해했다면, 금방 풀 수있다.. 라고 생각했다

 

각 문자를 그냥 숫자처럼 다루면 풀 수있다 ! 

 

라는 생각으로 배열에 알파벳들을 넣고 

 

풀트래킹을 돌렸다

 

똑같이 len 이 k만큼 도달하면 출력, return주고 하나 까고 다음으로

 

다만 중복을 없애기위해 백트래킹값에 +1을 주며 다음 값으로 넘어가며 문제를 풀었다

 

처음에는..

 

def back(tmp):     if len(ans)==4:         if "a" in ans or "i" in ans or "u" in ans or "e" in ans or "o" in ans:             print (*ans)         return     for i in range(tmp, len(ary)):         if ary[i] not in ans:             ans.append(ary[i])         back(i+1)         ans.pop() n,k = map(int,input().split()) ary = sorted(list(map(str,input().split()))) ans = [] back(0)

 

냅다 출력 초과가 떴다

 

뭐지뭐지 .. 하면서 보다가 

 

*ans로 하면 띄어쓰기로 들어간다는 걸 까먹고있었다 ..

 

풀고 join으로 다시했다 

 

def back(tmp):     if len(ans)==4:         if "a" in ans or "i" in ans or "u" in ans or "e" in ans or "o" in ans:             print (''.join(ans))         return     for i in range(tmp, len(ary)):         if ary[i] not in ans:             ans.append(ary[i])         back(i+1)         ans.pop() n,k = map(int,input().split()) ary = sorted(list(map(str,input().split()))) ans = [] back(0)

 

보기좋게 출력 초과가 2개 나왔다 ㅋㅋ..

 

 

그래서 뭐가 잘못된건지 계속 찾는데 답이안보였다 ..

 

그래서 문제를 게시판에 찾아보니 ..

 

자음도 같이 세줘야 하는 거 아니냐 ! 라는 말이나왔다 ..

 

뒤통수를 한 대 맞은 느낌이었다

 

왜 알파벳이 모음만 있을 수도 있다는 생각을 안 했을까

 

바로 for문으로 모음과 자음을 나눠서 카운트하고 일정 수 이상이 있는 경우에만 출력하게 끔 만들었다

 

def back(tmp):     if len(ans)==n:         mo = 0         za = 0         for i in range(n):             if ans[i] in 'aeiou':                 mo+=1             else:                 za+=1         if mo>=1 and za>=2:             print (''.join(ans))         return     for i in range(tmp, k):         if ary[i] not in ans:             ans.append(ary[i])         back(i+1)         ans.pop() n,k = map(int,input().split()) ary = sorted(list(map(str,input().split()))) ans = [] back(0)

 

 

mo먼저 검사하고 (모음 개수가 더 작으니)

 

그다음 아니면 자음인 식으로 +=1 해주면서 

 

변수값을 만든 뒤 비교해서 출력했다

 

그러니 간단히 풀렸다 

 

오늘은 문제가 쉬운반면 실수가 많아서 화가 많이 났다

 

뭔가 아직 부족하구나라고 느끼는 날이다