2023. 8. 13. 23:03ㆍ알고리즘
안녕하세요! 콩하나입니다 ㅎㅎ
오랜만에 블로그 글을 작성해보네요.
요즘 블로깅할만한 거리가 보이지 않아서... 못했다고 하죠 ㅎㅎ
예전에 백준 666일 연속 풀이를 하다가 끊기고 나서 한동안 안풀다가
최근 알고리즘 문제를 다시 풀고 있는데요.
이제는 오히려 스트릭에 구애받지 않고 풀고싶은 문제들을 풀어서 더 편안한 마음으로 스트레스 안받고 푸는 것 같아요 ㅎㅎ
아무튼 지난주에 블랙캣이 18년도 카카오 공채 문제들을 한번 풀어봐라~ 추천해서
지난주에는 18년도 카카오 공채 문제들을 풀어봤습니다.
확실히 최근 문제들이 어렵긴하더라고요...
금요일에는 당시 제일 어려운 난이도로 출제된 '추석 트래픽' 문제를 한번 풀어봤습니다.
그냥 풀어보고 넘기려고 했는데, 요즘 우테코 크루들 중에서도 알고리즘을 푸는 분들도 많으시고,
저한테 알고리즘을 어떻게 푸는지 물어보는 분들도 많으셔서 제가 알고리즘을 푼 방식에 대해 공유해드리려고 합니다.
문제 개요
우선 문제 개요입니다.
저는 문제를 읽을 때에는 문제에서 요구하는 사항이 무엇인지 정확하게 파악하려고합니다!
18년도 카카오 공채 문제들은 친절하게도 문제에서 요구하는 사항들이 분명하더라고요!
추석 트래픽 문제의 핵심적인 요구사항은 초당 최대 처리량을 계산하는 것이네요.
이때 주의사항은 초당 최대 처리량은 요청의 응답 완료 여부와 관계 없이 임의 시간부터 1초간 처리하는 요청의 최대 개수를 의미한다는 점이에요. 처음 문제를 보고 바로 이해가 안돼도 괜찮습니다. 보통 문제들에는 예제가 있으니 예제를 보고 이해하면 돼요.
입력 형식
입력 형식이 길게 느껴지지만 요약해보자면 다음과 같아요.
- 입력은 lines로 전달된다.
- lines는 최대 2000개의 로그 문자열로 구성되어있다.
- lines는 응답완료시간과 처리시간이 전달된다.(공백으로 구분)
- 응답완료시간은 2016-09-15 hh:mm:ss.sss의 형식이다. 날짜는 고정이다.
- 처리시간은 최대 소수점 셋째 자리까지 기록하며 뒤에는 s로 끝난다. 최대 3.000초까지 소요된다.
- lines는 응답완료시간을 기준으로 정렬되어있다.
하나씩 살펴보도록 하죠.
응답완료시간
- 응답완료시간은 2016-09-15 hh:mm:ss.sss의 형식이다. 날짜는 고정이다.
여기에서 날짜는 고정이기 때문에 사실상 문제에서 해당 부분을 고려할 필요는 없습니다. 문제 개요를 보더라도 마찬가지로 2016년 9월 15일의 트래픽을 아는 것이 요구사항임을 알 수 있기 때문에 날짜는 신경쓰지 않아도 됩니다. 만약 9월 14일, 16일 등 다른 날짜가 입력되었다면 데이터 전처리 과정에서 필요했겠지만요.
따라서 hh:mm:ss.sss의 시간을 가지고 문제를 해결한다고 생각하시면 돼요.
시간, 분, 초가 :을 기준으로 나눠져 있으니, :가 구분자겠구나~ 생각하시고 일단 넘어가셔도 좋습니다.
처리시간
- 처리시간은 최대 소수점 셋째 자리까지 기록하며 뒤에는 s로 끝난다. 최대 3.000초까지 소요된다.
처리시간의 경우, 예시를 보니 0.1s, 0.312s, 2s와 같이 전달받는 형식이 모두 다르다는 것을 주의하셔야합니다. 이를 인지하고 있어야지 입력받는 값을 저희가 원하는 방식으로 빠르게 전처리할 수 있습니다.
요청시작시간
재미있게도 입력에는 요청시작 시간이 없습니다. 다만 문제 개요에서는 요청 시간에 대해서는 언급이 되어있죠. 따라서 저희는 응답완료시간에 처리시간을 빼서 요청시작시간을 따로 구해야합니다.
입력에서는 이 정도 정보를 추출해볼 수 있겠군요.
출력 형식
출력은 문제 개요에서 본대로 초당 최대 처리량을 전달하면 되겠네요.
입출력 예제
그 밖의 입출력 예제들이 있습니다.
친절하게도 엣지케이스에 대한 예제여서 주의할 점을 금방 파악할 수 있었어요.
어렵다 싶은 예제에 대해서는 아주 친절하게 설명도 하고 있고요!
그림도 그려서 설명해주네요 ㅎㅎ
여기까지가 문제에서 주어진 상황입니다.
어떻게 풀어볼 것인가?
일단 여기에서 간단하게 어떻게 문제를 효율적으로 풀어볼 수 있을지 생각해보시면 됩니다!
초당 최대 처리량은 요청의 응답 완료 여부와 관계 없이 임의 시간부터 1초간 처리하는 요청의 최대 개수를 의미한다.
아까 문제에서 나왔던 초당 최대 처리량의 정의였죠. 여기에서 저희는 힌트를 얻을 수 있습니다. 초당 최대 처리량을 계산할 때 어떤 요청이 처리 중이라면 이는 처리량에 포함된다. 다시말해서 어떤 한 요청이 들어왔고, 이게 응답되지 않았다면 이는 처리량에 포함시켜도 된다는 점입니다.
이게 굉장히 중요한 의미를 가지는데요.
어떤 로그를 바라볼 때 요청시간과 응답시간만 보고도 처리량을 계산할 수 있다는 의미를 가지게 됩니다.
이해가 안되신다면 한번 위의 예제를 보고 요청 시간, 응답 시간만 가지고도 정답을 구할 수 있는지 시도해보세요. 아마 금방 이해가 되실거예요.
이렇게 문제를 한번 싸악 읽어본 뒤 문제를 어떤 방식으로 접근할 지 생각해보시면 됩니다!
연산 횟수 비교
이제는 문제를 어떻게 풀어볼 수 있을지 한번 연산 횟수를 가지고 비교해보도록 하겠습니다!
1. 00:00:00.000초부터 23:59:59:59.999까지 1초씩 대입해봐서 문제를 풀어본다.
는 당연히 안되겠죠?
밀리 세컨초를 기준으로 시간 계산을 하고 있기 때문에 1초에 대해 계산하는데 1000번의 연산이 필요합니다.
이걸 분, 시간 단위로 계산을 한다고 하면 1~2 내에 풀기에는 빠듯해보입니다.(1000*60*60*60 = 약 8천만) 추가적으로 이는 전체 시간을 탐색하는데 드는 연산 횟수이고, 이것뿐만이 아니라 모든 로그에 대해서도 탐색해야하고, 1초에 대한 밀리초들도 모두 계산해야하기 때문에 시간 내에 절대로 못푼다고 생각하시면 됩니다.
연산 횟수: 1000 * 60 * 60 * 60 * n(최대 2000) * 1000 수준으로 예상
2. 로그를 이중 반복문으로 돌려가며 하나씩 비교한다.
그냥 이중 반복문으로 돌려가며 비교를 한다면 n(최대 2000) ** 2 * t(최대 3000)의 연산 횟수가 발생하기에 사실상 풀 수 없습니다. 하지만 저희는 위에서 로그를 전체 비교하지 않더라도 시작과 끝을 비교하면 된다고 정리를 해보았죠.
따라서 로그의 앞뒤만 비교를 한다면 (n ** 2) * 2 = 약 800만 수준으로 문제를 충분히 문제를 해결할 수 있을 것으로 보입니다.
연산 횟수: (n ** 2) * 2 수준으로 예상
3. 시작시간을 기준으로 정렬된 로그를 반복문으로 돌려가며 해결해본다.
이 방법은 다소 복잡합니다. 힙 자료구조를 사용한 방법이기도 하고, 머릿속으로 생각해봐야할 것들이 많기 때문이죠.
1. 우선 min heap을 하나 새로 둡니다. 이 min heap에는 로그들의 끝나는 시간들이 담길거예요. 그래서 min heap의 0번째 요소는 가장 빨리 끝나는 로그가 되겠습니다.
2. 그리고 로그를 시작 시간을 기준으로 정렬합니다.
3. 정렬된 로그를 하나씩 반복문으로 꺼내옵니다.
3-1. 꺼내온 로그의 시작 시간 - 1초를 기준 시간으로 잡고, 해당 시간보다 heap에 담긴 로그의 시간이 더 이른 것을 모두 빼냅니다. (이 부분이 핵심입니다.)
3-2. heap에 꺼내온 로그의 끝 시간을 담고, heap의 개수를 셉니다.
4. heap의 개수 중 가장 많은 개수가 초당 최대 처리량이 됩니다.
이 방법은 다소 복잡하지만 2번보다 연산 횟수를 더 줄일 수 있습니다.
현재 프로그래머스에서는 해당 문제가 level 3 수준의 문제로 기억하는데, n의 크기가 100000 정도로 많아져서 level 4 수준의 문제로 난이도가 올라간다면 이러한 방식으로 풀어야합니다.
저는 해당 방법으로 문제를 풀어보았습니다.
괜히 18년도 1차 공채 문제 중 제일 어려운 문제라니 호승심이 일어 조금 더 어려운 방식으로 풀어보았습니다.
연산 횟수: n log n 수준으로 예상
코드 작성
자, 이렇게 내용을 정리하고 난 뒤에 문제를 푸시면 됩니다.
저는 여태까지는 이정도까지만 파악하면 그냥 바로 코드를 작성해서 문제를 풀었는데요.
요즘은 각 시점에서 어떤 동작들이 필요한지를 나열하고 문제를 풉니다.
이렇게 문제를 풀어보니 더욱 빠르고 정확하게 문제를 풀 수 있겠더라고요.
각 시점에서의 주의 사항도 잘 파악하고 말이죠. ㅎㅎ
대강 이런 느낌으로 문제를 풉니다.
먼저 글을 적고, 그에 해당하는 코드를 작성해요.
아무튼 저는 알고리즘 문제를 풀 때에는 단순히 코드보다는 접근 방법이 더 중요하다고 생각해서 이 쯤해서 글을 마무리하도록 하겠습니다.
그래도 혹시 궁금하신 분들이 있으실 수 있으니 아래에 코드도 남겨놓도록 할게요~
# 초당 최대 처리량 계산
# 1초간 처리하는 요청의 최대 개수
# 응답완료시간 s는 2016-09-15 hh:mm:ss.sss 형식
# 처리시간 T: 소수점 셋째 자리까지 기록
# 시작 시간 -> s - (t - 0.001)
# lines는 응답 완료시간을 기준으로 정렬
import heapq
def make_time(log_time):
h, m, s = log_time.split(":")
return (int(h) * 3600 * 1000) + (int(m) * 60 * 1000) + int(float(s) * 1000)
def make_elapsed_time(log_time):
s = log_time.split("s")[0]
return int(float(s) * 1000)
def solution(lines):
# lines의 시작 시간을 체크
time_tables = [] # 시작, 끝
for line in lines:
log = line.split(" ")
end_time = make_time(log[1])
elapsed_time = make_elapsed_time(log[2])
start_time = end_time - (elapsed_time - 1) if end_time - (elapsed_time - 1) >= 0 else 0
time_tables.append([start_time, end_time])
# lines의 시작 시간을 기준으로 정렬
time_tables.sort(key = lambda x: x[0])
answer = 0
h = []
# lines를 하나씩 탐색한다.
for start, end in time_tables:
# 현재 탐색 시간 ~ 1초 뒤: 처리량을 계산하는 구간
time_range = start - 1000
# 현재 min heap의 첫번째 요소의 값 + 0.999초가 현재 탐색 시작 시간보다 이전이면 이를 뺀다.
while h and h[0] <= time_range:
heapq.heappop(h)
# min heap에 끝 시간을 넣는다.
heapq.heappush(h, end)
# min heap의 개수를 매번 센 뒤 가장 큰 값을 저장한다.
answer = max(answer, len(h))
return answer
'알고리즘' 카테고리의 다른 글
| 백준 온라인 저지 365일 연속 문제 풀이 후기 (2) | 2022.07.26 |
|---|