[Implementation] Sales by Match

문제 설명: 

  There is a large pile of socks that must be paired by color. Given an array of integers representing the color of each sock, determine how many pairs of socks with matching colors there are.

 

Example

  n = 7, ar = [1, 2, 1, 2, 1, 3, 2]

There is one pair of color 1 and one of color 2. There are three odd socks left, one of each color. The number of pairs is 2.

Function Description

Complete the sockMerchant function in the editor below.

sockMerchant has the following parameter(s):

• int n: the number of socks in the pile
• int ar[n]: the colors of each sock

Returns

• int: the number of pairs

Input Format

The first line contains an integer n, the number of socks represented in ar.
The second line contains n space-separated integers, ar[i], the colors of the socks in the pile.

 

 

내 풀이:

func bubbleSort(_ array: inout [Int]) {
    let n = array.count
    
    for i in 0..<n {
        var swapped = false
        
        for j in 0..<n-i-1 {
            if array[j] > array[j+1] {
                array.swapAt(j, j+1)
                swapped = true
            }
        }
        
        if !swapped {
            break
        }
    }
}

// 양말의 컬러(숫자)가 바뀌는 시점의 index를 담은 배열 구하기
func getColorIndexArray(sortedSocks: [Int]) -> [Int] {
    var result = [0]
    var compare = sortedSocks[0]
    
    for (index, sock) in sortedSocks.enumerated() {
        if sock != compare {
            result.append(index)
            compare = sock
        } 
    }
    return result
}

// targetSock과 동일한 색(숫자)의 양말 갯수 구하기
func countSocks(sortedSocks: [Int], targetSock: Int) -> Int {
    var targetCount = 0
    for sock in sortedSocks {
        if sock == targetSock {
            targetCount += 1
        }
    }
    return targetCount
}

func sockMerchant(n: Int, ar: [Int]) -> Int {
    var result = 0
    // 1. sort socks
    var sortedSocks = ar
    bubbleSort(&sortedSocks) 
    // 2. get array of index when sock color changes
    var sockColorIndexes = getColorIndexArray(sortedSocks: sortedSocks)
    print(sockColorIndexes)
    // 3. count the number of socks of each color
    for sockIndex in sockColorIndexes {
        let sockCount = countSocks(sortedSocks: sortedSocks, 
        targetSock: sortedSocks[sockIndex])
        // 4. each color / 2 
         result += sockCount / 2
    }
    
    return result
}

 

 

회고 :

  무작정 풀기보다 어떻게 풀지 단계별로 차근차근 나누고 해결해 가는 방식으로 푸는 것이 중요하다 생각이 들었다.

'정렬 - 새로운 숫자가 나타나는 index의 배열 구하기 - 각 배열에 해당되는 숫자 갯수 구하기 - 숫자 갯수를 2로 나눈 몫들의 합 구하기'

와 같은 방식으로 나눠서 풀어보니 각 파트별로 구해야하는 것에 초점을 맞출 수 있었던 것 같다.