알고리즘 연습[2]

 해시 > 위장

스파이가 여러 종류의 옷을 가지고 총 몇가지의 위장을 할 수 있냐는 문제다. 이건 수학문제중에 경우의 수에서 자주 볼 수 있는 문제인데 중간까지 그걸 파악못하고 혼란을 겪었다. 

map 에 중복되는 요소들을 넣기 위해 이전 테스트에서 배운 getOrDefault 메소드를 사용했고, entrySet으로 모든 요소들을 가져와서 경우의 수 공식에 대입했다. 

스택/큐 > 다리를 지나는 트럭

이 문제는 시간이 정말 오래걸렸다.. 실제 테스트에 나왔으면 이거 하나 풀고 다른거는 건들지도 못하거나 이문제를 건들지도 못하거나 ... 생각 할 요소가 많은게 처음에는 가장 효율 적인 시간을 구해야 하는 지 알았다. 예를 들어 8, 3, 1, 7 무게 10 이렇게 있으면 8다음 3은 들어갈 수 없으니 뒤에 들어갈 수 있는 1을 찾아서 들어가서 시간을 단축내는 ? 이렇게 풀다보니 너무 어려워져서 다시금 그냥 주어진 순서만 지키면 된다는걸 알게 되었다. 해서 나온게 아래의 경우

while 조건에서 요구하는 sum과 다리위에 들어가기 위한 sum이 달라서 afterSum/beforeSum으로 나눴는데, 이걸 구하는 과정이 너무 반복이라 효율성에서 실패 하였다. 마지막 추가 되는 상황에서만 sum에 해당 요소를 더해주니 간신히 통과...!