문제
바로 어제 최백준 조교가 방 열쇠를 주머니에 넣은 채 깜빡하고 서울로 가 버리는 황당한 상황에 직면한 조교들은, 702호에 새로운 보안 시스템을 설치하기로 하였다. 이 보안 시스템은 열쇠가 아닌 암호로 동작하게 되어 있는 시스템이다.
암호는 서로 다른 L개의 알파벳 소문자들로 구성되며 최소 한 개의 모음(a, e, i, o, u)과 최소 두 개의 자음으로 구성되어 있다고 알려져 있다. 또한 정렬된 문자열을 선호하는 조교들의 성향으로 미루어 보아 암호를 이루는 알파벳이 암호에서 증가하는 순서로 배열되었을 것이라고 추측된다. 즉, abc는 가능성이 있는 암호이지만 bac는 그렇지 않다.
새 보안 시스템에서 조교들이 암호로 사용했을 법한 문자의 종류는 C가지가 있다고 한다. 이 알파벳을 입수한 민식, 영식 형제는 조교들의 방에 침투하기 위해 암호를 추측해 보려고 한다. C개의 문자들이 모두 주어졌을 때, 가능성 있는 암호들을 모두 구하는 프로그램을 작성하시오.
입력
첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다.
출력
각 줄에 하나씩, 사전식으로 가능성 있는 암호를 모두 출력한다.
알고리즘 스터디를 진행하면서 Python을 통해 문제를 풀고 있다.
C++과 Python을 섞어가며 문제풀이를 진행할 예정....(두개다 하기 힘들어요!!! 😭 )
실력증진을 위해...화이팅... 시간아 멈춰! ✋
어떻게 풀 것인가?
Python 장점 : Combination과 Permutation을 만들기 쉽다. 왜?
itertools에서 Combination과 Permutation을 제공하기 때문❗
주어진 알파뱃을 사전순으로 정렬하고, Combination을 통해서 문자를 조립해주면 될 듯??
근데 여러가지 조건이 있었다.
모음을 하나이상 포함해야 된다구?
그럼 만들어진 Combinations에서 모음 하나 이상인 것만 출력하지 뭐.
자음을 두개이상 포함해야 된다구?
그럼 만들어진 Combinations에서 자음 두개 이상인 것만 출력하지 뭐.
라고 생각했다가.
전체 갯수 - 모음 갯수 > 2이기만 하면 된다는 생각! (모음이 아니면 무조건 자음이기 때문에!)
증가하는 순서대로?
그럼 입력받은 문자열 정렬하고 Combinations 하면 사전순으로 될듯 🙂
그럼 끝!
자~~드가자~ 🖖
기본 입출력 정의
파이썬으로 처음 문제풀이기 때문에 입력을 어떻게 받아야될지 고민하다가
래영이형 코드를 훔쳐왔다.
import sys
l, n = map(int, sys.stdin.readline().split())
alphabets = list(map(str, sys.stdin.readline().split()))
print(alphabets)sys.stdin.readline()을 통해서 입력을 받으면 input()보다 더 빨리 입력받을 수 있다는 사실!
역시 이런거 하나 있을 줄 알았어.
C++에서 ios::sync_with_stdio(false); cin.tie(nullptr) 같은 것...
Combinations만들기
Python의 itertools에서 Combination 가져오기~
import sys
from itertools import combinations
l, n = map(int, sys.stdin.readline().split())
alphabets = list(map(str, sys.stdin.readline().split()))
print(alphabets)
alphabets.sort()
res = []
for comb in combinations(alphabets,l):
res.append(comb);
print(res)조건에 맞는 Combinations
조건에 맞는 것만 res에 넣기 위해서 chk()라는 함수를 만들었다.
def chk(comb):
vowel = 0
for c in comb:
if c in 'aeiou':
vowel += 1
if vowel == 0:
return False
if len(comb) - vowel < 2:
return False
return True모음 갯수와 자음 갯수 전부 만족!
그리고 조합 만들때 조건 검사해서 res에 넣기!
import sys
from itertools import combinations
l, n = map(int, sys.stdin.readline().split())
alphabets = list(map(str, sys.stdin.readline().split()))
print(alphabets)
alphabets.sort()
res = []
def chk(comb):
vowel = 0
for c in comb:
if c in 'aeiou':
vowel += 1
if vowel == 0:
return False
if len(comb) - vowel < 2:
return False
return True
for comb in combinations(alphabets,l):
print(comb)
if not chk(comb):
continue
res.append(comb)
for r in res:
print(''.join(r))잘 되는 것 같다.
🏎️ 제출하러 가즈아~ 🚗
맞았다 :)
예전에 풀었던 방식도 있었는데...
그 방식은 설명이 너무 복잡하고 코드도 길고 하튼...많이 별로다.
코드길이 확 줄고....시간도 확 줄고...
그래서 그냥 간단한 방식으로 한번 더 풀었다!
💥FeedBack💥
사실 피드백을 쓰기 위해 이 글을 쓴다고 해도 과언이 아님.
1. 작은 기능을 하는 것은 chk()와 같은 함수로 만들기 → 함수화
이건 뭐 더 이야기 할 것도 없지
2. 변수 이름을 이쁘게 만들고 코드 줄이기.
ans, res, ret → 정답 or 리턴값
p, k, x → 대충 쓰는 변수
pos, idx → 인덱스 가리킬 때
char은 c, string은 s
항상 이쁘고 멋있는 코드에 대한 생각이 많았는데 래영이형하고 이야기하고, 래영이형 코드를 보면서 점점 이쁘고 멋있고 보기 쉬운 코드에 대한 생각이 점점 잡혀가는 것 같다.
실제로 개발을 할때는 몰라도, 알고리즘 문제를 풀 때는 사람들끼리 통용되는 변수가 있는 것 같다. EX) ans..등
그리고 결국에는 코드양이 적을수록 보기 편하다는 생각이 들었다. 완전 숏코팅은 좀 그렇지만
읽어야 할 코드가 적을수록 알기 쉽겠지... 처음 푼 코드는 정말 길어서....나도 다시 보기 싫을 정도였다.
다시 봤는데 절대 이해 못함.
반성해 반성‼️ 🙇♂️
3. 남들이 작성한 코드를 5개정도 보고 남들 코드 이해한 것 다시 간결하게 작성해보기
이게 제일 중요한 듯.
혼자 풀고 맞았다고 나 좀 쩌는듯? 하기 보다는
다른 사람들이 푼 방식을 확인하고 더 나은 풀이 방법을 찾는게 실력 발전에 이바지한다고 한다.
항상....느끼지만 문제 풀어서 맞았습니다!! 뜨면 더이상 아무것도 하기 싫음...
앞으로 1. 래영이형 코드 2. 꾸준함 블로그 3. 유성장 블로그
이렇게 세번 코드만 찾아봐도 괜찮을 것 같다.
4. 실천하기....
아무래도 실천이 젤 중요하지요. 😩
항상 피드백 도와주는 래영이형 세상에서 제일 고맙다 🙂 🙏
