[1스4코2파] # 196 LeetCode 981. Time Based Key-Value Store

[1스4코2파] 1명의 스위프트 개발자와 4명의 코틀린 개발자, 2명의 파이썬 개발자코딩 테스트 서막 : 1스4코1파

Rule :

하루에 1문제씩 풀기.
한 문제당 30분씩은 고민하기.
왜 그렇게 풀었는지 공유하기.
하루라도 놓친다면 벌금은 1,000원
백준 플래티넘, 프로그래머스 4단계, 개발자 탈퇴 시 모임 탈퇴 가능

START :

[3코1파] 2023.01.04~ (196차)
[4코1파] 2023.01.13~ (188일차)
[1스4코1파] 2023.04.12~ (99일차)
[1스4코2파] 2023.05.03 ~ (77일차)

Today :

2023.07.18 [196일차]
Binary search
981. Time Based Key-Value Store

981. Time Based Key-Value Store

https://leetcode.com/problems/time-based-key-value-store/description/

문제 설명

set(String key, String value, int timestamp)
메소드는 주어진 시간 타임스탬프의 값 값과 함께 키 키를 저장함
get(String key, int timestamp) 메소드는 이전에 호출된 set과 같은 값을 timestamp_prev <= timestamp로 반환합니다. 이러한 값이 여러 개인 경우 가장 큰 timestamp_prev와 연결된 값을 반환하고 값이 없으면 ""를 반환하는
TimeMap 클래스를 구현하는 것 !

문제 풀이 방법

get 메소드에서 binary search를 통해서
timestamp를 비교해서 가지고 오는 기능을 구현한다.

init으로는 그냥 dictionary 인 hashmap을 생성하고
set으로는 key, value, timestamp를 받아서
key가 store 안에 없으면 받은 key, value를 추가해주는 것으로 구현한다.

get 메소드에서는 해당하는 key에 대한 timestamps들을 가져와서, binary search로 가장 큰 timestmp_prev와 연결된 값을 반환한다!

내 코드

# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reorderList(self, head: Optional[ListNode]) -> None:
        """
        Do not return anything, modify head in-place instead.
        """
        slow, fast = head, head.next
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
        
        second = slow.next
        prev = slow.next = None
         
        while second:
            tmp = second.next
            second.next = prev
            prev = second
            second = tmp

        first, second = head, prev
        while second:
            tmp1, tmp2 = first.next, second.next
            first.next = second
            second.next = tmp1
            first,second = tmp1, tmp2

증빙

여담

ㄱㄴㄷㅎㅅ