코드만 궁금한 분은 링크
GitHub - Rhyankwon/algorithms
Contribute to Rhyankwon/algorithms development by creating an account on GitHub.
github.com
문제 설명은 스킵하고..
문제를 풀 수 있는 두가지 방법이 있다.
첫번째는 dfs이다. 모든 문자열의 조합을 다 확인해봐야하기때문에 dfs로 그걸 구현하면서.. k개만큼의 조합을 만들었을때마다 - 입력받은 문자열 중 k개 조합만으로 구성이 되는지 확인해서 가장 많은 조합일 때의 갯수를 저장한다. 그리고 이 때 숫자조합에 맞춰 알파벳을 확인해야하기 때문에 ord함수를 써서 문자를 아스키코드로 변환한다. 어차피 순서가 중요한거라 -ord(‘a’)를 활용해서 a부터 z까지를 0...25 이런식의 인덱스에 매치시키면 된다. 아슬아슬하게 풀린다. python3로는 안 풀리고 pypy써야댐
두번째는 비트연산이다. 사실 dfs로도 비트연산 해서 풀면 더 빨리 풀릴듯. 아무튼, 비트연산을 하면 저.. k개의 조합을 만들 때마다 for문을 사용하지 않고 그냥 덧셈계산을 통해 문자 조합을 비교할 수 있게 할 수 있기 때문에 시간을 덜 소요하게 된다. python3로 계산되고, 그러면 첫번째 방법과 거의 비슷한 속도로 풀려서 그냥 원래 푸는데 오래걸리는 문제라는걸 알 수 있다. 근데 pypy3로 하면 확실히 속도가 짧아져서 첫번째 방식보다 수 배 속도를 줄일 수 있다.
사실 나는 처음에 그냥 for문으로 계산해서 풀었는데 당연히 안 풀릴거라고 예상하긴했다. 문제난이도에 비해 정답률이 낮아서 시간초과이슈가 있겠거니 했는데 정말 ..그랬다. 조금 고민해보다가 역시 난 효율성 문제는 아직이구나 싶어서 바로 그냥 검색해봤다. 이 문제를 비트연산을 사용해서 푸는게 대부분 사람이 좋은 방식이라고 채택한 풀이방법인것같았는데 나는 일단 dfs로 풀어보고싶어서 dfs로 푼 풀이를 대충 훑어보고 구현해봤다.근데 정말 신기한게, 나랑 그 사람의 기본적 논리는 같은데 사이에 미묘한 구현의 차이로 속도가 꽤 차이가 난다. 50%..? 이유는 글쎼 if문때문인가 싶기도 하고. 그리고 나서 비트연산으로 풀어봤는데 확실히 비트연산으로 풀라는 문제라는걸 느꼈다. for문을 생략할 수 있을 뿐만 아니라 덧셈연산이 탐색보다는 빠르니까.
ord를 모르면 풀 수 있는 문제일까?싶다. 순번을 매겨서 풀지 않고는 굉장히.. 푸는게 귀찮아질 것 같다. 여러모로 많은 공부가 된 문제였다. 1월..초 쯤에는 지금보다는 잘 할 수 있으면 좋겠다.
'코딩테스트 > 백준' 카테고리의 다른 글
| 백준 1700번 멀티탭 스케줄링 문제 해설/코드 (파이썬) (0) | 2021.09.30 |
|---|---|
| 백준 2504번 괄호의 값 해설/풀이/코드 (파이썬) 테스트케이스 추가 요청하기 (0) | 2021.09.29 |
| 백준 14888번 연산자 끼워넣기 풀이/해설/코드 (파이썬) /Eval의 속도, dfs 안에 for문 쓰기 (0) | 2021.09.27 |
| 백준 5904번 Moo 게임 풀이/코드 (파이썬) (0) | 2021.09.24 |
| 백준 1699번 제곱수의 합 풀이/코드 (파이썬) ('**2' 와 '*'의 차이..!) (0) | 2021.09.21 |