[알고리즘] Swift -프로그래머스 연습문제 #120876(겹치는 선분의 길이)

문제링크

https://school.programmers.co.kr/learn/courses/30/lessons/120876

프로그래머스

 

 

 

 

 

분석

선분 3개가 평행하게 있을 때, 2개 이상의 선분이 겹치는 부분의 길이를 리턴하는 문제

 

풀이 과정

선분의 개수는 3개

선분의 길이를 구하기 위해서는 음수일 경우와 양수일 경우가 있으니 절댓값을 취해준 후 큰 수에서 작은 수를 빼주면 된다.

겹치는 부분을 구하기 위해서는 점 하나가 선분의 시작지점과 끝지점 사이에 있을 경우 겹치게 된다.

범위가 -100부터 100까지의 배열을 만들고

var arr: [Int] = Array(repeating: 0, count: 200)

 

 

방문체크하는 것처럼 사이에 있는 값들에 +1을 해준다.

 

for line in lines {
    //라인의 시작점부터 끝지점까지 반복
    for j in line[0]..<line[1] {
        arr[j+100] += 1
    }
}

여기서 j+100을 해주는 이유는 시작이 -100부터이기 때문이다.

만약 [-5, 10]이었다면 배열의 시작 인덱스가 -5+100 = 95 이다.

 

arr.filter({$0 >= 2}).count

배열의 값이 2이상인 곳의 개수를 세주고 리턴해준다.

 

 

풀이

import Foundation

func solution(_ lines: [[Int]]) -> Int {
    // -100 부터 100 까지 이기 때문에 200 개의 원소를 갖는 빈 배열을 만들어준다.
    var arr: [Int] = Array(repeating: 0, count: 200)

    for line in lines {
        //라인의 시작점부터 끝지점까지 반복
        for j in line[0]..<line[1] {
            arr[j+100] += 1
        }
    }

    //배열에서 2번이상 겹치는 곳의 개수를 세어준다.
    return arr.filter({$0 >= 2}).count
}

 

결과

print(solution([[0, 5], [3, 9], [1, 10]]    ))

 

 

---

📂  정리

이번에는 다른 사람의 코드를 보고 참고 한 문제이다.

기존에는 첫번째시작점과 마지막점을 구해서 겹치는 부분을 빼주는 방식으로 진행했다.

func solution(_ lines: [[Int]]) -> Int {
    var overlaps: [(start: Int, end: Int)] = []
    for i in 0..<lines.count {
        for j in (i+1)..<lines.count {
            if lines[i][1] >= lines[j][0] && lines[i][0] <= lines[j][1] {
                var overlapStart = max(lines[i][0], lines[j][0])
                var overlapEnd = min(lines[i][1], lines[j][1])
                var overlapLength = overlapEnd - overlapStart

                for index in (0..<overlaps.count).reversed() {
                    let (start, end) = overlaps[index]
                    if overlapStart <= end && overlapEnd >= start {
                        overlapLength += max(end - overlapEnd, overlapStart - start)
                        overlapStart = min(overlapStart, start)
                        overlapEnd = max(overlapEnd, end)
                        overlaps.remove(at: index)
                    }
                }
                overlaps.append((overlapStart, overlapEnd))
            }
        }
    }

    return overlaps.reduce(0) { $0 + $1.end - $1.start }
}

왼쪽이 기존에 했던 방식으로 진행했던 결과이다.

코드는 길지만 시간을 보면 더 짧은 걸 볼 수 있다.

하지만 긴 거보다 짧은 게 이해하기 쉬우니까 ... 

나도 짧은 코드를 빨리 짤 수 있게 해야겠다...