[python3] 1396. Design Underground System

풀이 일자: 23.05.31

난이도: [Medium]

분류: [Hash]

문제 내용

문제의 내용은 사용자들이 지하철을 타고 내릴 때 걸리는 시간의 평균을 리턴하는 문제였다.

 

문제 해결 흐름

1. 이 문제를 해결하기 위해서 떠오를 만한 방법은 해시정도?

→ 그 이유는 지하철을 환승한다던가 여러 곳을 거쳐야 한다던가하는 일이 없고 정직하게 시작점과 끝점의 시간정보와 사용자 수에 대한 정보만 가지고 있다면 되기 때문이다.

→ 또한 해시를 사용할 수밖에 없는 것이 배열에서 startStation과 endStation의 인덱스를 찾아서 그 인덱스로 2D array에서 평균 시간을 리턴하고 체크인 체크아웃을 하기에는 시간이 너무 많이 걸리기 때문이다.

→ 따라서 이중 해시를 이용해서 문제를 해결해보았다.

 

class UndergroundSystem:

    def __init__(self):
        self.avgTime = dict();  # {startStation: {endStation: [total Time, clients]}}
        self.inout = dict();    # {id: [startTime,startStation]}

    def checkIn(self, id: int, startStation: str, t: int) -> None:
        self.inout[id] = [t, startStation];
        if startStation not in self.avgTime:
            self.avgTime[startStation] = dict();

    def checkOut(self, id: int, endStation: str, t: int) -> None:
        startTime, startStation = self.inout[id];
        del self.inout[id];
        if endStation not in self.avgTime[startStation]:
            self.avgTime[startStation][endStation] = [0,0];
        self.avgTime[startStation][endStation][0] += (t - startTime);
        self.avgTime[startStation][endStation][1] += 1;
        

    def getAverageTime(self, startStation: str, endStation: str) -> float:
        s, n = self.avgTime[startStation][endStation];
        return s/n;

 

 

Time Complexity:  O(N)

시간 복잡도는 오래 걸려봐야 station의 갯수인 N정도가 될 것이다.

 

 

Space Complexity: O(NM)

공간 복잡도는 이중 hash를 구성하고 있기 때문에 startStation의 수인 N개와 endStation의 수인 M개정도의 곱정도될 것이다.

 

 

다른 해결 방식

1. 나의 방식과는 좀더 좋은 방식으로 2중 해시로 구성하지 않고 아예 (startStation, endStation)을 key로 보았다.

→  이를 제외하고 Counter를 사용한다거나 defaultDict을 사용하는 등의 편의를 위한 약간의 차이가 있을 뿐 큰 차이는 없었다.

 

 

 

문제 링크

https://leetcode.com/problems/design-underground-system/description/

Design Underground System - LeetCode