2019 카카오 개발자 겨울 인턴십 레벨3문제를 풀어보았다. 요즘 내가 있는곳에서 평가 기간도 겹치고 반복되는 새벽 근무와 잠을 잘 못잔거 때문에 스트레스를 많이 받은 느낌이었는데 조금 더 분발해서 많은 문제를 풀어보고싶다.
백트래킹 문제를 부쩍 자주 푸는 느낌인데 정말로 도장깨기 하는 느낌으로 문제들을 접근하고 있다. 예전에는 전혀 이해가 안됐던 문제들도 계속 접근하다보니깐 이해가 되고 그냥 답만 옮겨적었었던 어려운 유형의 문제도 아 이랬었구나 하고 느끼면서 내가 내 코드로 재해석해서 과거에 힘든 문제들을 하나씩 푸는 재미로 살고있다. 비록 추가적인 포인트나 랭킹은 못올리고 있지만 이거 자체로도 의미가 있는거같다.
문제는 불량사용자의 리스트가 주어졌을때 응모자 아이디의 벡터 (user_id) 에서 해당되는 불량 사용자의 리스트를 찾고 숫자를 리턴해주면 되는문제이다. 다만 제한사항중 하나는 내용이 동일하다면 순서에 상관없이 같은 것으로 처리하고 하나로 세면된다는것이다.
그렇다. 이 문제는 백트래킹 문제이다. 난 분명 이 문제를 더 빨리 풀수있을줄 알았는데 생각보다 느리게 풀었던 이유중에 하나는 불량 사용자의 목록과 응모자 아이디의 목록의 길이가 다르기 때문에 어떻게 동시에 유지할수있을지를 고민하는 과정에 있었다. 정답은 그냥 임의에 또다른 index를 만든느것이었고 한 유저당 하나의 불량 아이디가 배정되기때문에 visited 라는 bool 벡터를 사용해야한다는 점 이었다.
또 한가지의 실수를 했던거는 답의 예시를 보니깐 이건 순열 문제가 아닌 조합 문제라는걸 깨닫게 되고 뒤늦게 visited2 라는 벡터를 또 하나 만들다 보니 코드가 꽤 길어졌다. 이제 순열과 조합의 차이에 꽤 익숙해져있기때문에 내가 틀린 문제를 계속 보면서 어떤 과정이 이루어지고 있었을까 생각하다보니 머리속에서 그려지는걸 보고 뿌듯했다.
다음은 내가 쓴 코드이다:
visited 하나는 banned_id를 위한것 그리고 visited2는 조합을 위해 user_id를 위해 만든것이다. set 는 중복된 순서에 상관없이 하나로 처리하기 위해 사용한 자료구조이다.
잘리긴 했지만 뒤에 부분은 알아들을거라 믿는다. 컨테이너가 banned_id에 사이즈에 닿았을경우 컨테이너안에 있는 요소들을 sort 해준다음에 set에 넣었다. sort 해준 이유는 다른 순서여도 동일하게 만들기 위해서이다. copy 벡터를 만든 이유도 문제를 디버깅 하다보니 느낀건데 container 는 오리지날 카피이기 때문에 sort해주면 답이 이상하게 나와서 바꿔줬다.
에전에 2021 카카오 블라인드 순위 검색을 보고 배웠던 prev_permuation 방식이다. frodo 가 있으면 * 가 들어갈수있는 모든 조합을 만들고 banned_id 와 비교하고 같다면 true 를 리턴했다.
정답은 결국 다 맞았지만 다른 사람들의 풀이를 보니 훨씬 간결하고 깔끔한것들이 많았다. 가령 frodo 의 * 가 들어가는 모든 조합을 만들 필요도 없었다던지 ㅠㅠ 좀 복잡하게 생각해서 시간이 길어졌는데 다음에는 더 생각을 많이 해야겠다.
배운점:
1. 조합과 순열의 활용, 그리고 bool 벡터의 중요성
2. 문제를 너무 복잡하게 생각하려하지 말자.
