[프로그래머스] 위클리 챌린지 5주차 후기

지난주에 이어 이번주에도 위클리 챌린지 문제를 풀어보았다.

문제는 아래와 같다.

https://programmers.co.kr/learn/courses/30/lessons/84512

코딩테스트 연습 - 5주차

---

word의 길이가 5 이하이고, 문자 또한 A, E, I, O, U만 포함될 수 있으므로

시간복잡도는 크게 신경쓰지 않아도 통과시켜주는 범위이다.

즉, 정확성만 체크하는 문제일 것이란 생각이 가능하다.

(물론 O(N!) 뿐만 아니라, O(N), O(2^N) 등 더 좋은 시간복잡도로 풀면 더더욱 좋긴 하다. 실제로 좋아요를 가장 많이 받은 코드는 O(N)일 뿐만 아니라, 가독성 또한 굉장히 좋은 코드였다.)

 

전형적인 백트래킹 문제이다.

백트래킹은 브루트포스(완전탐색) 알고리즘 중 하나이다.

어차피 길이가 5 이하이기 때문에 백트래킹으로 모든 경우를 O(N!) 또는 O(N*N!)에 따져도 크게 문제가 되지 않는다. 

 

또한, 이번에는 문제 입력이 [] 배열이 아닌, string을 그대로 입력받는 형태여서 로컬에서 테스트하기 편해서 되게 만족스러웠다.

프로그래머스는 왜 input을 받을 때 배열을 []형태로 받는건지 모르겠다. 로컬에서 테스트할 때 일일이 {}로 변환해서 돌려야되기 때문에 이런 형태는 꽤 짜증난다. 또, vector<vector<int>> 형태로 인자를 주고받는 방식 또한 나에겐 골칫덩어리였는데, 이번엔 그러한 형태의 인자가 없어서 굉장히 힐링됐다.

 

참고로 길이가 1~5인 문자열 모두 탐색 대상에 속하므로 모든 경우를 탐색하고 길이가 5를 초과하는 경우를 탐색할 때엔 바로 return시켜버리도록 하자.

---

해결완료

Level 2 문항으로 무난무난한 문제였다.

백트래킹 기초를 익히기에 적당한 문제인듯.

 

* 프로그래머스 정책에 따라 풀이 코드는 올리지 않습니다. *