라이브코테 준비 - 연습문제1

어떤 기업의 라이브코테를 봐야했다.

메일로 연습문제를 보내줬으므로 풀어보도록 하였다.

출처링크

문제

Problem 77 [Easy]

스냅챗에서 출제된 문제입니다.

중첩될 수 있는 인터벌들을 갖는 리스트가 있습니다. 중첩되는 인터벌들을 하나로 합친 새로운 리스트를 반환하세요.

입력 리스트는 정렬되어 있지 않습니다.

예를 들어, [(1, 3), (5, 8), (4, 10), (20, 25)] 가 주어지면, [(1, 3), (4, 10), (20, 25)] 를 반환해야 합니다.

먼저 풀고 답을 보니까 고려해야할 사항들 중 하나가 빈 리스트 들어올 수 있다는 것이다.

---

풀이

def solution(input):
    result = []
    input.sort()
    for i in range(len(input)):
        if result and result[-1][1] >= input[i][0]:
            result[-1] = (result[-1][0], max(input[i][1], result[-1][1]))
        else:
            result.append(input[i])
    return result


input = [(1, 3), (5, 8), (4, 10), (20, 25)]
intervals = [(1, 3), (5, 8), (4, 10), (20, 25), (22, 27)]

assert solution(input) == [(1, 3), (4, 10), (20, 25)]
assert solution(intervals) == [(1, 3), (4, 10), (20, 27)]

결과를 리턴할 새로운 배열을 생성하고 그 배열의 끝만 비교하면 된다.

1. 처음에는 result[i-1]로 비교하였지만 연속으로 겹치는 배열이 들어올 경우 result에는 2번 연속 적재되지 않아서 out of range 뜬다. 때문에 Python에서 제공하는 배열[-1]를 통해 끝값을 확인한다.
2. 겹친다는 의미는 다음과 같은 경우가 있을 것이다. 현재 요소가 (4,10)이라고 치면
   다음 요소가
   • (3,5)인 경우 즉 x값이 작은 경우
   • (4,9)인 경우 안쪽에 완벽히 겹친 경우
   • (9,11)인 경우 다음요소 x가 기존 요소의 y값에 걸쳐진 경우

첫 번째 경우는 정렬을 통해 막을 수 있다. 무조건 x가 작은 요소가 먼저 들어오기 때문이다. 그래서 정렬을 해줬다.

두 번째 경우는 요소에 추가하지 않으면 된다.

세 번째 경우는 어차피 x는 작은 요소가 들어오게 보장되어있기에 끝 부분만 업데이트 해주면 된다. 다음 요소의 y와 현재 요소의 y를 비교해서 큰 경우는 업데이트를 해주고, 아닌 경우는 현재 값을 수정하지 않는다(두 번째 경우 해소)

---

결론

처음에는 빈 리스트가 들어올경우를 생각하지 않고 풀었다. 뿐만 아니라 문제의 첫 예제만 보고 완벽히 포개어진 경우만 생각하였는데, 다음에는 다양한 인풋 예제를 먼저 생각하는 것이 필요할 것 같다.