스위프트 기초정렬문제, 2693 N번째 큰 수 문제풀이

 

 

---

백준 2693번, N번째 큰 수 문제설명

N번째 큰 수는 T번의 테스트케이스에 대해서 각각 10개의 숫자가 주어졌을때 3번째로 큰 숫자를 출력하는 기초정렬 문제입니다.

 

 

 

 

배열 A가 주어졌을때 3번째로 큰 값을 출력하면 되는 문제입니다. 배열 A의 크기는 10입니다. 또한 주어지는 숫자는 모두 자연수입니다. 자연수의 범위는 1,000 이하이므로, 계수정렬을 활용해서 O(N)의 시간복잡도로 풀 수 있습니다. 

 

저는 계수정렬을 활용해서 빠르게 문제 풀어보겠습니다.

 

 

 

 

예제 입/출력은 위와 같습니다. 참고하시고, 바로 문제 풀어보겠습니다. 

 

 

 

---

백준 2693번, N번째 큰 수 문제풀이
계수정렬을 활용해서 문제풀기

먼저 테스트케이스 갯수, T를 입력받고, 정답을 모아둘 answer 배열 또한 정의했습니다.

 

각 케이스마다 print() 함수를 사용해서 정답을 출력할 수 있지만, 저는 배열에 정답을 모아두었다가 joined()로 합친 후, print() 함수를 단 한번만 사용해서 답을 출력할 예정입니다. 

 

 

 

 

4행) T번의 테스트케이스를 수행하는 forEach 반복문입니다. 

 

5 ~ 6행) 계수정렬 카운팅용 배열, dic과 주어진 숫자 중 최댓값을 저장할 mx변수를 정의했습니다. 

7 ~ 11행) 10개의 값이 있는 배열을 입력 받아 곧바로 forEach로 숫자를 탐색, dic 배열에 기록합니다. 최댓값 또한 mx에 저장합니다. 이후 최댓값 부터 1까지 순차적으로 숫자를 줄여가며 3번째 큰 수를 구합니다. 

 

13행) cnt는 3번쨰 큰 수를 알아채기 위해 사용하는 카운팅 변수입니다.

14 ~ 20행) mx -> 1로 타겟숫자를 줄여가면서 3번째로 큰 수를 찾아갑니다. 그렇게 세번째로 큰 숫자를 찾게 됨면 answer에 저장하고, 반복문을 빠져나갑니다. 

22행) 최종적으로 answer에 저장된 문자열을 개행단위로 합친 후, 출력하여 문제를 해결합니다. 

 

이렇게 swift언어와 계수정렬을 활용해서 문제를 풀 수 있었습니다. 아래에 제출결과 및 소스코드 첨부드리겠습니다. 참고하시기 바랍니다.

 

 

 

---

let T = Int(readLine()!)!
var answer: [String] = []
(0..<T).forEach { _ in
  var dic = [Bool](repeating: false, count: 1001)
  var mx = 0
  readLine()!.split(separator: " ").map { Int(String($0))! }
    .forEach { num in
      dic[num] = true
      mx = mx < num ? num : mx
    }
  
  var cnt = 0
  for target in (1...mx).reversed() {
    if dic[target] {
      cnt += 1
      if cnt == 3 { answer.append("\(target)"); break }
    }
  }
}

print(answer.joined(separator: "\n"))