[알고리즘/Swift] 정렬 문제풀이 - K번째수, 가장 큰 수, H-Index

Swift 스터디 10주차 6/24

스터디 4주차 챕터였던 "정렬 알고리즘" 에서 삽입 정렬, 병합 정렬, 퀵 정렬에 대해 학습했었습니다. 이와 관련되서 프로그래머스의 정렬 챕터를 통해 알고리즘 문제 풀이를 진행했습니다.

 

✔︎ K번째수

배열 array의 i번째 숫자부터 j번째 숫자까지 자르고 정렬했을 때, k번째에 있는 수를 구하는 문제이다.

 

👀 입출력

 

• array : Int 배열, 1 <= 배열의길이 <= 100
• commands : [i, j, k] 를 원소로 갖는 2차원 배열, 1 <= 배열의길이 <= 50
• return : commands 에 맞는 결과값을 배열로 담아 리턴한다.

 

💡 풀이방법

 

• 각 command 마다 array 배열의 i ~ j 까지의 부분 배열을 서브스크립트를 통해 구한다. 
• 부분 배열을 오름차순으로 정렬하고, k번째 수를 정답 배열에 추가하고, 정답 배열을 반환한다.
• array 배열은 인덱스가 0부터 시작, i, j, k 는 인덱스가 1 부터 시작한다는 차이만 잘 확인하면 된다.

 

풀이1 - for 문 이용

func solution(_ array:[Int], _ commands:[[Int]]) -> [Int] {
    var answer = [Int]()
    for command in commands {
        let i = command[0], j = command[1], k = command[2]
        answer.append(array[i-1...j-1].sorted()[k-1])
    }
    return answer
}

 

풀이2 - map 함수 이용

 

풀이1에서의 command = $0 이라고 생각하면 된다. $0 은 원소가 3개인 일차원배열인 것이다.

func solution(_ array:[Int], _ commands:[[Int]]) -> [Int] {
    return commands.map { array[$0[0]-1...$0[1]-1].sorted()[$0[2]-1] }
}

---

✔︎ 가장 큰 수

0 또는 양의 정수가 주어졌을 때, 정수를 이어 붙여 만들 수 있는 가장 큰 수를 알아내는 문제이다.

 

👀 입출력

 

• numbers : 정수로 이루어진 1차원 배열, 0 <= 배열의 길이 <= 1,000
• return : numbers 배열의 정수를 이어 붙여 만들 수 있는 가장 큰 수를 반환한다.

 

💡 풀이 방법

 

• 정수를 문자열로 변환해서, 이어 붙였을 때 더 큰 수가 되도록 정렬한다.
• sort(by:) 함수를 이용해서 문자열의 합으로 이전값+다음값 / 다음값+이전값 을 비교해 정렬한다.
• 예를 들면, [33, 30] -> '33'+'30' = '3330' > '30+'33' = '3033' 이므로 '33', '30' 순서로 정렬된다.
• 예외 처리 :: [0, 0, 0] -> '000' 으로 정답은 0이 되어야하므로 별도로 예외처리를 해주어야한다.

 

풀이1 - sort, reduce, if-else 활용

func solution(_ numbers:[Int]) -> String {

    var stringNumbers: [String] = numbers.map { String($0) }

    stringNumbers.sort { prev, next in
        let first = prev + next
        let second = next + prev
        return first > second
    }

    let answer = stringNumbers.reduce("", +)
    if answer.first! == "0" {
        return "0"
    } else {
        return answer
    }
}

 

풀이2 - sorted 축약, joined, 삼항연산자 활용

func solution(_ numbers:[Int]) -> String {

    let stringNumbers: [String] = numbers.map { String($0) }
    let answer = stringNumbers.sorted { return $0+$1 > $1+$0 }.joined()
    return answer.first! == "0" ? "0" : answer
}

---

✔︎ H-Index

어떤 과학자가 발표한 논문 n편 중, h번 이상 인용된 논문이 h편 이상이고 나머지 논문이 h번 이하 인용되었다면 h의 최댓값이 이 과학자의 H-Index입니다.

 

👀 입출력

 

• citations : 어떤 과학자가 발표한 논문의 인용 횟수를 담은 배열
• return : 이 과학자의 H-Index

 

💡 첫번째 풀이

 

• 문제에 써져있는 대로 풀은 방법. (풀이2보다 시간효율이 안좋다)!
• h 를 0부터 논문의 개수까지 증가하면서 h번 이상 인용된 논문이 h편 이상인지 확인하며 최댓값을 구한다.

func solution(_ citations:[Int]) -> Int {

    var hIndex = 0
    while hIndex <= citations.count {
        let count = citations.filter { $0 >= hIndex }.count
        if count < hIndex { break }
        hIndex += 1
    }
    return hIndex - 1
}

 

💡 두번째 풀이

 

• 논문의 인용 횟수 배열을 내림차순 정렬한다. * citations 는 함수인자라 상수이므로 sorted 함수를 통해 return 값을 이용한다.
• h 를 0부터 논문의 개수까지 증가하면서 h 번째 논문의 인용 횟수와 비교한다.
• 처음으로 나타난 h 번째 논문의 인용 횟수가 h 이상일 때가 h의 최대값으로, H-Index 가 되어 반환한다.
• h 를 전부 반복한 경우, H-Index 는 논문의 개수와 같아지게 된다.

func solution(_ citations:[Int]) -> Int {
    
    let citations = citations.sorted(by: >)
    for hIndex in 0..<citations.count {
        if hIndex >= citations[hIndex] {
            return hIndex
        }
    }
    return citations.count
}

풀이1과 풀이2 상세한 과정  (더보기)

citations = [3, 0, 6, 1, 5]
정렬x
h = 0 -> h 이상 5 >= 0
h = 1 -> h 이상 4 >= 1
h = 2 -> h 이상 3 >= 2
h = 3 -> h 이상 3 >= 3
h = 4 -> h 이상 2 >= 4 x --> H-Index = 4-1 = 3

정렬 = [6, 5, 3, 1, 0]
h = 0 -> 0 >= 6 x
h = 1 -> 1 >= 5 x
h = 2 -> 2 >= 3 x
h = 3 -> 3 >= 3 o --> H-Index  = 3

 

🤔 풀이1과 풀이2의 시간복잡도 비교 * 정렬의 필요성 !!

시간복잡도 비교 

 

📖 오늘 스터디의 리뷰

• 다른 스터디원 분들의 코드를 보고, 같은 언어로 좀 더 간결한 코드를 고민해볼 수 있었다.
• map, sort, sorted 함수의 closure 를 잘 활용하자!
• [string].joined() 를 통해 하나의 문자열로 만들 수 있다.
• 깨알문법 :: array.sort() 는 리턴값 없이 array 요소를 업데이트, array.sorted() 는 정렬된 배열을 반환한다.

---

👀 참고 링크

• 가장 큰 수 참고 풀이
• git hub 코드

songda515/SwiftAlgorithm