[백준 - Python] 20440 - 🎵니가 싫어 싫어 너무 싫어 싫어 오지 마 내게 찝쩍대지마🎵 - 1

0.  문제 링크

 

 

https://www.acmicpc.net/problem/20440

20440번: 🎵니가 싫어 싫어 너무 싫어 싫어 오지 마 내게 찝쩍대지마🎵 - 1

---

1.  풀이 방법

 

 

일단 처음에 이 문제를 Two Pointer로 풀려고 했다.

근데 그건 좀 힘들 것 같아서 어떻게 풀지 고민을 했다.

 

 두 번째로 생각한 방법은 출입 시간과 퇴장 시간을 리스트로 만들어서 +1을 시키는 것이다.

그리고 index를 차례대로 참조하면서 찾는 것!

근데 이거는 문제가 시간이 너무 오래 걸린다.

아니 오래 걸리는 건 둘째치고 메모리를 미친 듯이 먹는다.

21억 개의 리스트를 두 개나 만들다 보니까 실제로 메모리를 31GB나 먹는 것,,,,,,, ㅁㅊ;;

 

그래서 이건 아니다 생각을 해서 동적으로 만들어야 된다는 것을 생각했다.

저번 스터디에 스터디원이 defaultdict을 사용했는데, 이게 동적으로 작동하는 것이 떠올랐다.

그래서 이를 이용하고, 출입과 퇴장을 하나로 만들어서 저장했다.

최종적으로 가장 높은 값이 있을 때, 시작을 저장하고, 가장 높은 값이었다가 떨어질 때 퇴장을 저장했다.

---

2.  코드

 

 

import sys
from collections import defaultdict
input = sys.stdin.readline

if __name__ == "__main__":
    n = int(input())
    maps = defaultdict(int)
    for _ in range(n):
        e, x = map(int, input().split())
        maps[e] += 1
        maps[x] -= 1

    max_value = 0
    cur_value = 0
    bef_value = 0
    start, end = -1, -1
    flag = False

    for i in sorted(maps.keys()):
        bef_value = cur_value       # 이전 값을 저장
        cur_value += maps[i]        # 현재 값을 갱신
        if cur_value > max_value:       # 만약 현재의 값이 최댓값보다 크다면 갱신
            max_value = cur_value
            start = i
            flag = True     # 중복으로 end를 갱신하는 것을 방지하기 위함
        if flag and bef_value == max_value and cur_value < max_value:
            # 위에서 갱신했을 때만 end를 갱신함
            # 이때 현재 값은 작으면서, 이전 값은 커야함
            end = i
            flag = False

    print(max_value)
    print(start, end)

---

3.  마무리