한 동안 의상 선택 문제에 막혀서 요새는 풀지 않고 있었다. 어제 연락한 리크루터가 코딩테스트를 한다고 해서 다시 그 문제를 들여다보았다. 내가 그 문제에서 막힌 이유는 20개 중에 19개는 통과하는데 하나에서 시간 초과가 뜨기 때문이었다. 몇일을 들여도 해결 방법이 떠오르지 않았기 때문에.. 이번에는 inout으로 배열을 복제하지 않게 하는 등으로 특정 문제 기준 750ms였던 처리 속도를 120ms까지 줄였다. 그래도 여전히 몇시간째 막혀서 결국엔 GPT에게 요청했는데 무료인 3.5는 개선책을 내놓지 못했다.(개선 했다면서 내 코드를 그대로 줌) 그래서 Bing에게 주니 아주 짧은 코드를 내놨다. 그 코드를 그대로 넣고 제출해보니 시간 초과되던 문제에서 0.08ms가 나왔다. 처음에는 이해하지 못했는데 관점의 차이였다. 나는 재귀함수로 나머지 경우를 선택해 나가게 하고, 1개부터 n개까지 선택하는 경우를 모두 더했는데. 각 종류에 0개를 선택하는 경우를 포함하면 자연스럽게 1~n개 선택하는 경우가 모두 포함되는 것이었다. (a,b,c에서 1개씩 선택한다고 했을 때 a에서 0개를 선택한 경우 b,c가 되는 것이다) 문제의 주제는 Hash였는데 Hash를 사용하지 않아서 풀지 못한 것이 아니라 관점을 다르게 보지 못한 게 문제였다.
콘텐츠를 더 읽고 싶다면?
원티드에 가입해 주세요.
로그인 후 모든 글을 볼 수 있습니다.
로그인 후 모든 글을 볼 수 있습니다.
・댓글 1