[코드트리 챌린지] 2차

2023/09/18 (월)

마지막 문제를 풀지 못했는데..

마지막 문제는 3가지 방법으로 풀었던 것 같다.

첫번째는 백트래킹(모든 경우의 수에 대한 조합을 계산해야 했어서)

두번째는 itertools의 combinations

세번째는 이중 반복문 사용..

이번에도 역시나 시간복잡도를 생각하지 않고 풀었던게 문제였는데 세가지 방법 모두 실패했었다.

 

제안해주신 문제와 해설을 봤는데,

이런 문제 유형도 시간을 줄이기 위한 방법을 HashMap으로 사용할 수 있는지 새로 배울 수 있었다.

N^2의 경우에 시간초과가 발생한다면, 한 번의 반복문 안에서 해결해야 한다.

 

반복문 한 번..

 

여기서 또 잠깐 멈칫했던 것은, 어떤 것을 기준으로 쌍의 갯수를 더해줄지 고민했다.

(1) 현재 인덱스를 기준으로 이미 지나온 값을 더해주는가?

아니면

(2) 현재 인덱스를 기준으로 앞으로 보게 될 값을 더해주는가?

 

였는데, 사실 앞으로 어떤 값이 올지 모른다. 하지만 둘 다 처리를 해주어야 한다.

즉, (1)과 (2)에서 관여하는 변수가 다르다.

(1)의 경우 dictionary에 담긴 값을 answer에 더해주고

(2)의 경우 dictionary[key] += 1을 해주기 때문.

 

다시 말하면,

정답에 해당하는 쌍의 갯수를 세는 변수(answer)에 더해야 할 것은 이제까지 등장했던 값의 횟수(dictionary[key])를 더해야 했다.

그리고 현재 값은 dictionary의 key로 넣고 그 key에 해당하는 value를 1 증가시킨다.

 

HashMap의 경우 시간 단축을 위해 종종 사용했는데, 이렇게 경우의 수 처럼 보이는 문제도 활용할 수 있다니 놀랍다.