부트캠프 32일차 후기

오늘 CodeKata는 3문제를 풀었다. 가장 기억에 남는 문제는 두 번째로 풀었던 "두 큐 합 같게 만들기"이다.

 

https://school.programmers.co.kr/learn/courses/30/lessons/118667

프로그래머스

이 문제는 얼핏 보면 Queue를 사용해서 Bruteforce하게 푸는 문제처럼 보여진다. 하지만, 두 큐의 길이가 십만 단위라서 Bruteforce하게 풀 순 없다. 그렇다면 어떻게 풀어야할까?

 

여기서 한 가지를 깨달았는데, 당연하지만, queue1에서 뺀 원소를 queue2로 원소를 옮기면 queue2에 원소의 합이 커진다는 거다. 그러니까, queue1과 queue2의 합을 같게 하려면 큰 곳에 있는 Queue를 작은 곳에 있는 Queue로 옮기는 Greedy한 방식이 통할 수도 있다는 거다. 그러면 그 구현은 어떻게 할까? Queue 두 개를 만들어서 그냥 구현을 할까? 그러면 어떤 방법으로도 각 큐의 원소 합을 같게 할 수 없는 경우는 어떻게 계산해야하지? 그런 것을 생각했을 때, 하나의 아이디어가 떠올랐다. 바로 투 포인터다.

 

일단 queue1과 queue2를 이어붙인 배열을 만든다. 그리고 왼쪽을 가리키는 변수(이하 l)는 0으로, 오른쪽(이하 r)은 queue1의 사이즈 만큼을 가르킨다. l가 r이 가르키는 것은 queue1고, 배열의 나머지는 queue2를 의미한다. queue1의 원소를 빼고, queue2의 원소를 빼는 것은 l = l + 1이고, queue2의 원소를 queue1으로 넣는 작업은 r = r + 1이다. 이것을 queue1의 원소들이 queue2와 같아질 때까지 반복한다. 어떤 작업을 할 지는 위에서 언급한 알고리즘을 따른다. 만약 배열의 끝까지 r이 도달했는데도 같아지지 않았다면, 원소 합을 같게 할 수 없는 경우이다. 나는 이렇게 이 문제를 해결하였다.

 

사실 오늘 내가 한 일은 별로 없었다. 팀원분들의 코드를 보고 조언을 하는 정도였고, 같이 코드를 짜며 시간을 보냈다. 가장 기억에 남는 오류는 내가 처음 데이터베이스를 만들 때, 외래키를 안 만들어서, 다른 팀원 분의 코드가 오류가 발생했다는 것이다. 결국 내가 외래키 컬럼을 만들어서, 문제가 해결되었다.

 

한편, 거의 완성되어가는 팀 프로젝트의 문제가 발생했다. 한 팀원 분의 노트북이 고장나서, 작업하신 분량이 다 날라가버렸단 사실이다. 들은 바에 의하면 Git에도 Push을 안 하셔서, 결국 내가 해당 파트를 맡게 되었다. 좀 당황하기 했지만, 어느정도 각오한 바였기도 하고, 어차피 시간도 있어서, 그렇게까지 큰 감정의 동요는 없다. 내일 안에 코드를 짜자. 다행히 해당 파트는 내가 이전 프로젝트에서 했던 파트와 겹쳐서, 거기서 코드를 가져와서 변형시키면 생각보다 빨리 끝날 수 있을 것 같다. 빠르게 완성하고, 코드를 전체적으로 이어붙이는 작업을 해서 테스트를 빠르게 마치자.