[Swift 알고리즘] LeetCode 2078. Two Furthest Houses With Different Colors

○

Greedy | Easy

2078. Two Furthest Houses With Different Colors

Constraints
- n == colors.length
- 2 <= n <= 100
- 0 <= colors[i] <= 100
- Test data are generated such that at least two houses have different colors.

 

간단한 문제이지만, 다양한 풀이가 나올 수 있어 재미있었다. 

 

1. 

맨 처음에는 이런 식으로 풀었는데, 이론상 최대 O((n/2)^2) 정도 되는건가,,

앞의 절반과 뒤의 절반을 반복문으로 함께 탐색하는 방법이다. 

func maxDistance(_ colors: [Int]) -> Int {
    var result = [Int]()
    let count = colors.count / 2 + colors.count % 2
    for i in 0...count {
        for j in stride(from: colors.count-1, through: count, by: -1) {
            if colors[i] == colors[j] { continue }
            result.append(j-i)
        }
    }
    return Set(result).max()!
}

2. 

결과값을 배열에 굳이 더해 줄 필요는 없기 때문에, result 값 하나로 다음과 같이 바꿔봄.

func maxDistance(_ colors: [Int]) -> Int {
    var result = Int()
    let count = colors.count / 2 + colors.count % 2
    for i in 0..<count {
        for j in stride(from: colors.count - 1, through: count, by: -1) {
            if colors[i] != colors[j] {
                result = max(result, j-i)
                break
            }
        }
    }
    return result
}

3.

다른 분의 풀이 중에서 가장 효율적이어보였던 것. 

나는 캐치하지 못했지만, 이 문제의 정답은 항상 맨 첫번째 혹은 맨 마지막 값과의 거리를 비교하게 된다. 

따라서 다음과 같이 앞에서 한 번, 뒤에서 한 번 최대 거리를 구한 후 max 로 비교해줄 수도 있다. 

func maxDistance(_ colors: [Int]) -> Int {
    var start = 0
    var end = colors.count - 1
    let count = colors.count - 1
    // find max distance from index 0
    while colors[0] == colors[end] {
        end -= 1
    }
    // find max distance from last index
    while colors[start] == colors[count] {
        start += 1
    }

    return max(end, count - start)
}

동일한 방법으로 아래와 같이 구현해줄 수도 있음. 

func maxDistance(_ colors: [Int]) -> Int {
    var result = Int()
    let count = colors.count - 1

    for i in 0...count {
        // find max distance from last index || find max distance from index 0
        if colors[i] != colors[count] || colors[0] != colors[count - i] {
            result = count - i
            break
        }
    }

    return result
}