순위 검색

유승선 ·2022년 1월 12일
0

프로그래머스

목록 보기
6/48


매일매일 코딩테스트 폐관수련으로 근무 끝나거나 시작하기 전에 사지방에 앉아가지고 주구장창 문제만 푸는중이다. 비록 이 전에 LeetCode 문제들을 풀때처럼 하루에 두문제 세문제 푸는건 힘들지만 양보다는 질을 선택하는 마음가짐으로 카카오 문제들만 공략중이다. 최근들어는 훈련이 좀 더 힘들어져서 개인정비 시간이 줄어들었고 시간을 내기 힘들지만 꾸역꾸역 짜내고 있는중이다 (잠 3시간 자고 00시부터 06시 근무 끝난후에 코딩테스트 문제 풀려니 죽을거같긴 했다.)

문제가 설명하듯 info 벡터에는 코딩언어 - 직군 - 경력 - 소울푸드 - 점수 순으로 나열된 문자열이 있고 query 에도 비슷하지만 조금씩 다른 문자열이 제공됐고 우리는 query 에 있는 문자열을 통해서 해당 query 에서 원하는 정보의 사람들이 얼마나 있는지를 리턴하면 되는문제이다.

솔직히 이 문제를 처음 읽었을때는 감도 안왔고 어떻게 해야할지도 몰랐다. [java]라는 키워드를 기준으로 backend - junior - ... 순으로 그래프를 만들어야 하나? 라는 생각도 들었고 아예 모든 카테고리에 map을 만들어서 따라가야하나 이런생각도 들었지만 미친 생각이었다. 결국에 힌트를 찾기 위해 다른 블로그들을 참고했고 내가 생각한 방법들에 비웃음을 치듯 해결 힌트는 바로 키워드를 java/backend/... 이런식으로 따로따로하는게 아닌 [javabackendjuniorpizza] 이런식으로 한번에 만든다음에 score 만 따로 저장하면 되는것이었다.

사실 이 문제는 언제였지...일병 4호봉때 한번 도전해보고 정 안되서 다른 사람의 답을 또 참고하고 카피해서 꾸역 꾸역 맞춘 문제였기에 온전히 내가 푼게 절대 아니였다. 그렇지만 이번에는 온전히 내 힘으로 문제를 풀기 시작했고 정말 많은 뿌듯함을 느꼈다.

해결 방법은 위에서 말한대로 키워드를 저렇게 종합한 다음에 "-" 를 1에서 4까지 조합 을 시켜서 모두 맵에 저장한후에 query 를 읽으면서 특정 score 이상에 사람을 lower_bound() 함수를 통해 이진탐색후 인원의 숫자를 찾으면 되는문제였다.

(사지방 컴퓨터 너무 작다...집 컴퓨터가 너무 마렵다...)
정말로 색다로운 문자열 parsing 방법을 좀 배운거같다. 내가 직접 썼으면 뭐 for loop 을 이용해 ' ' 빈칸이 나오면 빈 문자열에 추가하고 빼고 과정을 통해서 내가 원하는 문자열을 고를수있는 함수를 만들수 있지만 코딩테스트에는 시간이 생명이기 때문에 굉장히 유용한 parsing 함수인 istringstream 을 처음 배웠다. 생각보다 정말 간단했고 앞으로도 요긴하게 많이 쓸수있을거같다. lower_bound() 이진탐색도 처음 써보는데 개인적으로 이진탐색 문제를 좋아하는 나로서는 아쉬웠지만 시간을 아끼기에는 좋은 함수같다.

매번 느끼지만 카카오는 조합? 류의 문제를 레벨2 문제유형으로 많이 내는거같다. 다행히 리트코드 등등의 수련을 통해 조합류에 자신이 생겨서 내가 나만의 함수를 적을수 있었단거에 뿌듯했다.

이 조합 방법을 쓰면 r 이 1에서부터 4까지 늘어날동안 전부 조합을 할수있으므로 4C1 + 4C2 .. 4C4 통해서 초과되지 않을만한 코드를 쓸수있었다.


내가 썼던 조합 방법 외에도 STL 로 제공되는 prev_permutation 이라는 함수가 있는데 이것도 처음에는 이해가 전혀 안됬는데 계속 하다보니 이해가 완전히 됐다. 나중에 시간을 아끼고 싶다면 이 방법을 쓰는것도 나쁘지 않을거같다.

끝으로 조합을 이해하는데 있어서 가장 많은 참고를 했던 블로그 링크 하나를 써보겠다.
https://ansohxxn.github.io/algorithm/combination/

배운점:
1. 가끔은 무식하게 푸는것도 나쁘지 않다
2. 나만의 코드를 만들어보자. 이해안되면 할때까지 보자.

profile
성장하는 사람

0개의 댓글