코드챌린지 두개뽑아서더하기 완전탐색 swift 문제풀이

 

 

 

프로그래머스에서 최근 코드챌린지 이벤트(?)를 열었습니다. 
프로그래머스 코드챌린지에 나온 기초문제 중 하나를 swift로 풀어보겠습니다. 바로, "두 개 뽑아서 더하기" 문제입니다.

바로 문제 풀러 가보겠습니다~

 

 

---

두 개 뽑아서 더하기 문제설명

두 개 뽑아서 더하기, 해당 문제는 제목만으로 해당 문제의 요지를 알 수 있습니다. 

정수 배열, numbers가 주어질때, 해당 배열의 서로 다른 인덱스에 있는 두 개의 수를 뽑아 더해 구할 수 있는 모든 수의 경우를 오름차순으로 담아 답으로 return하는 문제입니다. 예를들면, [1, 2, 3] 이 numbers로 주어진다면, 1+2, 1+3, 2+3 의 값이 있겠죠. 그 결과는 [3, 4, 5]가 됩니다. [3, 4, 5]은 그 자체가 오름차순이므로 이대로 답을 제출하면 되는 것입니다. 

서로 다른 인덱스의 두 개의 수를 뽑는 경우를 완전탐색으로 구해내면 되겠네요. 그 시간복잡도(Time Complexity)는 O(N^2)가 되는데요. 다행이도, 해당 문제의 입력값 범위는 2 ~ 100에 불과하므로, O(N^2)의 시간 복잡도로도 충분히 통과할 수 있지 않을까 싶습니다.

 

 

두 개 뽑아서 더하기 문제의 입출력 예시입니다. 

문제 제목 그대로 서로다른 인덱스의 두 수의 합의 경우를 모두 구해서 오름차순으로 정렬해주면 되는데요. 주의할 점은 중복되는 결과값에 대해서는 하나의 값으로 쳐야한다는 것입니다. 고유한 결과값들의 오름차순이 되는 것입니다. 

swift에는 이러한 고유한 값에 대한 카운팅에 사용될 수 있는 대표적인 2가지 자료구조가 있습니다. 바로 Hashable한 set과 dictionary입니다. 

바로 문제풀이를 가보겠습니다. 🤗

 

 

 

---

두 개 뽑아서 더하기 완전탐색 swift 문제풀이

먼저, 딕셔너리 문제풀이입니다. 

이중 포문을 통해서, 서로 인덱스가 다른 두 수의 합의 경우를 완전탐색 하는 코드입니다. 내부의 for문은 idx+1부터 시작함으로써 중복되지 않은 인덱스의 값들을 더함을 보장하고 있습니다. 

딕셔너리는 [Int: Bool](), : [Int: Bool] = [:] 와 같은 초기화 방식으로 선언한 후, 위와 같이 key, value 형태로 사용될 수 있습니다. 
서로다른 인덱스의 합 결과 기록을 7행에서 진행하고 있습니다. 

이후 정답으로 기록된 딕셔너리의 key값만 map으로 맵핑 후, sorted()로 오름차순 정렬을 해주고 있습니다. 딕셔너리에서 sorted()를 사용하면 기본적으로 배열로 반환하게 되므로 이 자체를 그대로 반환하면 정답을 제출할 수 있습니다.  

sorted()는 기본적으로 오름차순 정렬을 해줍니다. sorted(by: <), sorted(by: >) 등으로 오름차순 / 내림차순을 설정할 수도 있습니다. 

 

 

 

딕셔너리를 사용해서 정답을 맞추었네요. 그 결과는 위와 같습니다. 

완전탐색 + 딕셔너리를 통해서 해당문제를 풀어보았습니다. 여기서 끝나면 심심하죠? Set을 사용해서도 풀어보겠습니다. 

 

 

이번에는 Set을 통해서 문제를 풀어봅니다.

Set<Int>()로 Set을 초기화 한 후, 앞서 했던 딕셔너리의 7행 동작을 위와 같이 Set 메서드인 insert로 수행하고 있습니다. set이 같고 있는 값 또한 Hashable하며, 고유의 값을 갖게 됩니다. 

또다른 차이점이라면, return 하고 있는 11행에 있습니다. 딕셔너리는 key, value 의 페어와 같은 형태로 단일값 배열 변환을 위해 map으로 맵핑을 했던 반면, set은 그저 sorted() 메서드로 오름차순 정렬만 해주면 되었습니다. 

이 과정에서 딕셔너리는 map(), sorted()를 사용했지만, 셋(set)은 sorted()만 사용하면 되었네요. 그렇다면 이어서 제출 결과를 보겠습니다. 

 

 

네 앞서 보았던 완전탐색 + 딕셔너리 방식보다, 완전탐색 + 셋 방식이 좀더 빠른 결과값을 보이고 있네요.

제 생각에는 아무래도 map()연산자로 한번 더 맵핑 한 딕셔너리 방식보다 Set방식이 빠를 수밖에 없었다고 생각되네요. ㅎㅎ

 

 

 

---

오늘은 이렇게, 프로그래머스의 코드챌린지 문제 중 하나인 두 개 뽑아서 더하기 완전탐색 swift 문제풀이를 해보았습니다.

매우 간단한 문제이지만, Set, Dictionary를 번갈아가면서 풀어보면서, 재밌는 실험도 해볼 수 있었습니다. ㅎㅎ 

Dictionary, Set 자료구조는 Array와 더불어 알고리즘 문제, 코딩테스트 문제등에서 매우 유용하게 사용되는 만큼, 자주 사용해보면 좋을 것 같습니다. 그럼 이만 ㅂㅇ입니다. 👩🏻‍💻

 

두 개 뽑아서 더하기 문제 코드 swift 참고링크 ▼

applebuddy/ProgrammersAlgorithmStudy