인프런 커뮤니티 질문&답변

1. 아 각 숫자가 두개씩 들어있는데 딱 한 숫자만 하나 들어있는 배열에서 하나만 든 숫자를 찾는거구나

2~3. 

{10, 10, 20, 30, 30, 40, 40, 50, 50, 60, 60} 에선 20이 혼자

{7, 10, 6, 4, 22, 10, 4, 5, 6, 5, 22} 에선 7이 혼자

4. 음 같은 숫자가 두개씩 있는 배열에서 딱 한 숫자만 한개가 들어있으니까 중복을 허용하지 않는 set 자료구조를 사용해보자

5-1. 배열의 각 요소들을 순회하면서 차례대로 set에 넣어보자

5-2. set에 값을 넣을 때 이미 존재하는 값이면 리턴값은 false이다.

5-3. add의 리턴값이 false이면 set에서 해당 요소를 삭제하자

5-4. 모든 요소들에 대한 순회가 끝나면, set에는 딱 1개의 값만 남아있을 것이므로 stream으로 1개의 값을 획득한다.

5-5. 획득한 값을 리턴한다.

6. 즉 제가 제시한 방법의 시간복잡도는 배열의 길이만큼 순회하고, 거기서 다시 논리비교를 매번 하니 O(n²), 공간 복잡도는 O(n)입니다

 

복잡도가 익숙지 않아서 참 어렵군요 

공간복잡도가 헷갈리는데, set에 n개만큼 더했다가 n개만큼 삭제하므로, n²이라고 생각했는데 잘 이해가 안갑니다.공간복잡도는 늘어난 것만 생각하고 줄어드는 것은 고려하지 않나요? 일단 계속 돌려보면서 이해하고 있겠습니당