문제의 카테고리는 깊이/너비우선탐색이다. 학교다닐때 알고리즘 수업을 아예 안듣다시피해서 아무것도 모른다고 봐도 과언이아니다. 그래서 알고리즘 문제가 나오면 항상 막막하고 인터넷에서 해당 알고리즘에 대하여 공부부터하고 코딩을 했었다.
알고리즘을 떠나 이 문제를 보고 떠오른 방식은 트리였다. 맨 처음 수 부터 다음 수를 더한것과뺀것을 쭉 저장하면 층층으로 이루어진 트리구조로 나올 것 같았다. 이렇게 계산을 한다면 numbers의 사이즈가 커질수록 계산이 너무 커지겠지만 일단은 이 방식으로 해보자.
- 모든 결과가 담길 빈 배열
temp를 선언한다. itorator로numbers의 원소에 접근한다.- 그 안에 빈 배열
node를 하나 더 선언한다. (numbers의 원소 하나마다 초기화되어야 하므로) itorator로temp의 원소에 접근한다.
5-1.node에numbers의 원소first와temp의 원소second를 더해서 저장한다.
5-2.node에numbers의 원소first와temp의 원소second를 빼서 저장한다.- 하나의
first에 대한 연산이 끝나면temp를node로 바꿔준다. - 모든 값이 담긴
temp가 완성되면filter를 사용하여target과 같은 값들의 수를answer에 저장한다.
레고레고
시간초과는 변순데....?
바꿔줄 만한 건 temp와 node의 타입이나 node에 연산결과를 더해주는 부분 정도인듯하다.
일단 Array로 선언했던 변수들을 Arraylist로 바꿔보자.
...?
연산결과가 너무 방대해져서 시간이 오래 걸릴 줄은 알았지만 아예 시간초과가 나올 줄은 몰랐다.
Array = Array.plus(Int)이 부분이 좀 신경 쓰이기는 한다. 값을 배열에 저장해주는 느낌이 아니라 배열을 교체하는(?) 것 같아서 자원이 많이드는 듯 하다. 아마도 Array는 변경이 불가능한 형태이기 때문에 데이터를 추가하는 것이 아닌 새롭게 배열을 선언을 해주는 방법으로 업데이트가 가능한 것 같다.
다른 방법을 좀 찾아보자.
Array안에서 답이 안나와서 Arraylist로 변경 후 add함수를 사용했더니 통과를 하긴했다. 테스트 5같은 경우는 바꾸기전에 1398ms라는 어마어마한 시간이 걸렸지만 지금은 현저하게 줄어든 것을 볼 수 있다. Arraylist가 널리 쓰이는 이유를 한번 더 인지할 수 있었다.
