정말 오랜만에 프로그래머스 문제 리스트가 업데이트가 되서 바로 찾아가서 문제를 풀었다. 해당 문제들은 2022 카카오 인턴십 문제 리스트인데 어느때와 같이 레벨1은 쉽기때문에 금방 풀었다.
레벨2 문제는 내가 생각했던것보다 간단해보였고 정말 심플한 그리디 문제라고 생각했지만 이상한 포인트에서 시간 초과가 나왔고 두 문제를 통과 못했어서 조금 어지러웠다.
일단 문제를 접근하는 방법은 여러가지가 있는데 투포인터로 접근 하는 방향도 있고 아에 큐를 따로 만들어서 보관하는 방법도 있었다. 처음 시작하는 두 큐의 값을 구하고 더 높은 수를 가진 큐를 하나씩 빼면서 서로 값이 같아질때까지 돌리면 됐었다.
다만, 두 합이 같아지지 않는 경우로는 만약 모든 값들을 빼면서 한 큐가 비게 되는 순간 불가능을 뜻하는 -1을 리턴하면 됐었다.
난 아예 큐를 따로 만들어서 관리르 해줬고 pop과 insert 과정에서 answer++를 해줬다. 내 첫번째 접근은 시간초과가 났고 시간초과를 줄일 수 있는 방법을 생각했는데.
정말 최악의 경우로 큐 안에 있는 모든 원소를 빼고 넣었음에도 값이 같아지지 않는 경우를 생각못했었다.
즉, 큐 한쪽이 비게되면은 -1을 리턴하는 조건까지는 맞았지만 큐가 비어지지 않고 계속해서 안에 있는 원소를 서로 주고 받는 상황에서 시간 초과가 나던것이었다.
[3,2,7,2], [4,6,5,1] 을 예시로, 가장 이상적인 방법은 2번의 작업안에 서로 수를 맞추는것이지만. 정말 최악의 방법으로 가면은 4,6,5를 빼줘서 넣고 3,2,7,2 를 다시 넣어주고 하는 방법으로 7번의 작업까지 늘어날 수 있다. 여기에서 추가로 의문에 테스트케이스를 더한다는 과정에서 이 작업은 마지막 요소를 탐색할때까지 계속 늘어날 수 있는거고 가장 최악으로는 초반에 시작했던 queue1 의 사이즈에 3배까지 탐색이 가능하다는 뜻이다.
즉, -1을 리턴하는 조건으로는 queue 한쪽이 비게 되는 경우도 있지만 탐색 범위가 기존 사이즈의 3배 이상으로 가게되면은 끝내야 한다는것이다.
똑같은 코드지만 if 문을 더해주는것으로 모든 테스트케이스를 통과했다. 솔직히 이렇게 직접적으로 queue 를 사용하는것보다 투포인터를 이용하는게 공간적으로 더 효율적이고 추가적인 조건 문으로 만약에 두 값을 더한 결과에 2를 나눈게 홀수면은 아예 -1을 리턴하는것도 좋은 확인법이라고 생각한다.
배운점:
1. 조건에 대한 생각
2. 시간 초과에 대한 고찰
