swift Sorting 값 정렬하는 방법, 백준 수 정렬하기 문제풀이

 

 

---

백준 2751, 수 정렬하기 2 문제설명

백준 2751번 수 정렬하기 2 문제는 O(NlogN) 이상의 효율로 정렬하기를 요구하는 문제입니다. O(N^2)의 시간복잡도로 해당 문제를 풀면 통과하기 어렵습니다.

 

 

 

 

제한시간은 2초, 1 ~ 1,000,000 범위의 N을 입력받습니다. 백만개의 숫자를 정렬해야할 경우 O(N^2)의 복잡도로는 2억번(약 2초)를 훨씬 뛰어넘는 시간이 필요하므로 통과하기 힘듭니다.

 

 

 

 

첫줄에 N을 입력받고, 2 ~ 2+N번째 줄에 숫자를 하나하나 입력받습니다. 여기서 주의할 점은 절대값 백만 이하의 정수이므로 음수가 나올 수도 있다는 점입니다. 

 

바로 swift언어로 백준 수 정렬하기 2 문제를 풀어보도록 하겠습니다. 

 

 

 

---

백준 2751, 수 정렬하기 2 swift 문제풀이
swift 내장함수, sorted(), sort() 활용, 문제풀이

ㅋ

1행) 먼저 정수 하나를 입력받아 String을 반환한는 ip() 클로져(함수)를 정의했습니다. readLine()함수가 여러번 사용될 경우 이렇게 클로져를 미리 정의하고 사용하면 코드가 좀더 간결해보이는 장점이 있습니다.

 

2 ~ 6행) 이후 N을 입력받고, G라는 배열을 정의했습니다. G배열에 이후 N번 입력받는 숫자를 하나하나 넣어줍니다. 이제 이 G배열을 정렬해서 값을 출력할 예정입니다. 이어서 가보도록 합니다. 

 

 

 

 

swift의 배열은 기본적으로 sort(), sorted()라는 정렬함수를 제공합니다.

 

위와 같이 sorted()를 사용하면 원본배열은 변경되는것이 없고, 대신 정렬된 배열을 반환합니다. 거기에 이어 정렬된 배열을 순회(forEach)하면서 값을 출력하는 모습입니다. 이렇게 O(NlogN)의 시간복잡도로 해당 문제를 간단하게 풀 수 있습니다. 

 

원본배열 G 자체를 정렬해서 G.forEach { ... } 의 방식으로 동일하게 문제를 풀 수 있습니다. 

 

요약하자면, sorted()는 원본배열이 변환하지 않고, 정렬된 새로운 배열을 반환한다. sort()는 원본배열 자체를 정렬시킨다. 입니다. sort()와 같이 구조체의 내부를 변환시킬 수 있는 함수를 mutating 함수라고도 합니다.

 

 

아래 제출결과는 차례대로 sort(), sorted()를 사용한 문제풀이 결과입니다. 

 

 

 

 

---

그렇다면 이게 최선의 방식일까요? 사실 해당문제는 O(N)의 시간복잡도로 해결할 수도 있습니다. 정수의 범위가 한정적이기 때문입니다. 바로 계수정렬로 푸는 방법이 있습니다. 

 

 

 

 

---

수 정렬하기 2 계수정렬 활용, swift 문제풀이

계수정렬을 사용한 문제풀이 해설은 자세하게는 하지 않겠습니다. 해당문제는 중복된 숫자가 들어가지 않으므로, [Bool] 배열, dic을 활용해서 존재하는 숫자를 기록하고, 정렬된 값을 출력할 수 있습니다.

 

12 ~ 14행) 음수의 값까지 포함해서 계수정렬을 해야하는데, 음수는 인덱스로 사용할 수 없으므로, 입력받은 숫자의 + 1,000,000을 해주어 인덱스를 dic 배열에 기록해줍니다.

 

19 ~ 23행) 이후에 dic배열의 값을 순회하면서 true 값을 갖고 있는 인덱스를 문자열로 모아서 합친 후 출력하는 답안입니다. 이때 숫자를 합칠때에는 다시 1,000,000을 빼서 모아주어야 하는 점이 있습니다. 

문제풀이 간 활용한 enumerated, reduce(), joined() 등은 forEach, sort, sorted등과 더불어 유용하게 사용할 수 있는 고차함수들입니다. 관심있으시면 찾아보고, 사용하는 연습을 해보시길 추천드립니다.

 

계수정렬은 한정적인 숫자일 경우 O(N)의 시간복잡도를 가지는 장점이 있지만, 그 수의 범위가 커질 수록 많은 메모리를 필요로한다는 단점이 있죠. 아래 계수정렬 문제풀이의 제출결과를 보시면 계수정렬의 장/단점을 볼 수 있습니디.

 

 

 

 

백준 2751 수 정렬하기2 문제 제출결과