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

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

 

 

 

문제 해결 방법

 

1. 시간을 key로 모기수를 value로 한 딕셔너리를 만든다. 

2. key를 통해 딕셔너리를 정렬한 후, 순회하면서 현재 들어온 모기 수랑 그동안 순회하며 들어온 최대 모기 수를 갱신한다. 최대 모기 수를 갱신하는 중에는 flag변수를 통해 계속 인지하고있는다. 또한 최대 모기 수를 갱신하기 시작한 시간을 표시해준다. 

3. 최대 모기 수를 유지하다가 모기가 나가기 시작하면 최대 모기 수는 깨진다. 따라서 이때 flag변수를 통해 다시 이를 인지할 수 있도록 값을 바꿔주고, 그동안 최대 모기 수를 유지했던 시간을 표시해준다. 

4. 출력

 

코드 구현

시간 초과된 코드

import sys

n=int(sys.stdin.readline())
total=[]
minn=2100000000
maxx=0

for i in range(n):
    # 입장시간, 퇴장시간
    e, x = map(int, sys.stdin.readline().split()) 
    #print(e, x)
    if e<minn:
        minn=e
    
    if x>maxx:
        maxx=x

    total.append([e,x-1])

#print(minn, maxx)

total 

tmp=[]
for i in range(maxx):
    tmp.append(0)

for i in total:
    s, e = i
    for i in range(s, e+1):
        tmp[i]+=1

#print(tmp)

check = 0
start = -1
end = -1

result = []

cnt=0

for i, value in enumerate(tmp):
    if value == max(tmp):
        if start != -1:
            check=1
            continue
        else:
            #최초로 넣을때 
            check=1
            start = i
            result.append(i)
            cnt+=1
            start=-1
            

    else:
        if check==1:
            check=0
            end=i
            result.append(i)
            end = -1

#print(result)

print(max(tmp))


origin = result[0]
originEnd = 0
originStart=0
for i, value in enumerate(result):
    if i ==0:
        originStart=value
        continue

    if origin +1 == value:
        origin+=1
    else:
        originEnd=result[i-1]
        break

if originEnd==0:
    originEnd=result[-1]

    
print(originStart, originEnd)

정답 코드

 

(주석 있는 버전)

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

n = int(input())
d = defaultdict(int)
print('defaultdict', d)
for i in range(n):
    s, e = map(int, input().split())
    d[s] += 1
    d[e] -= 1




m, cnt = 0, 0 # cnt는 모기 마릿수 m은 최대갱신 모기 마릿수 
tem, txm = 0, 0# 최댓값 갱신시 시간과 갱신 해제시 시간
flag = False
for i in sorted(d.keys()):
    print(i)
    cnt += d[i]
    # 기존 최대 모기수 보다 현재 모기수가 더 클때
    # == 최고일때만 계산함 
    if cnt > m:
        m = cnt
        tem = i
        flag = True
    # 현재 모기수 cnt보다 최대 갱신 모기수가 더 크고
    # 만약, 현재 값이 모기가 나가는 타이밍일때
    # 현재 모기수에서 지금 시간의 모기를 빼면 음수값이라 더한 격이 되어
    # 지금 나간 모기를 더했을때의 값 = 최대값이 m인 경우이다. 
    # FLAG가 TRUE인 상태 
    # 마찬가지로 최고자리가 박탈 됐을때 계산함 
    elif cnt < m and cnt - d[i] == m and flag:
        txm = i
        flag = False
print(m)
print(tem, txm)

 

(주석 없는 버전) - 변수명 변경됨

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

n=int(input())
dict = defaultdict(int)

for i in range(n):
    # 입장시간, 퇴장시간
    e, x = map(int, input().split()) 

    dict[e] += 1
    dict[x] -= 1
    

maxx, nowMos = 0, 0
startTime, endTime = 0, 0
flag = False
for i in sorted(dict.keys()):
    nowMos += dict[i]

    if nowMos > maxx:
        maxx = nowMos
        startTime = i
        flag = True
    elif  nowMos < maxx and nowMos - dict[i] == maxx and flag:
        flag = False
        endTime = i

print(maxx)
print(startTime, endTime)

 

시간/공간 복잡도

 

입력값보다 입력값의 값의 범위가 워낙 커서 웬만하면 N으로 구현해야 했다. 

 

 

최적화 및 개선

 

• 기존에는 입력값의 범위를 전부 순회하면서 최대 모기수를 체크해서 시간초과가 발생했었다. 
  • 이런 방식의 관점을 바꿨다. 
  • => 현재 방에 있는 모기의 수가 갱신이 되는 모기의 수일 경우에만 체크 

 

어려웠던 점

시간복잡도에 대한 개념은 알고있지만, 여전히 문제 풀기전에 시간복잡도에 대한 계산을 하는것이 어렵다. 

파이썬의 경우 1초에 최대 연산횟수가 logN인 알고리즘으로 계산해도 최대 연산 횟수가 10억번인데, 이 문제의 경우 값의 범위가 10억을 훌쩍넘어 20억쯤 된다. 이런 경우는 시간복잡도 계산을 어떻게 해야하는지 모르겠다. 

 

 

알게된 것

• sys모듈의 sys.stdin.readLine() 함수를 input 변수로 저장 할 생각을 못하고 계속 수기로 작성해왔었는데 이제는 변수로 저장할 줄 알게됐다. 
• 딕셔너리 자료구조가 이런경우에 유용함을 다시 상기시킬수 있었다.