1409. Queries on a Permutation With Key

오랜만에, 문제를 가지고 왔습니다 !

 

사실 계속해서 문제를 풀었는데, 포스팅만 안했네요. 이번 문제는 포스팅할 맛이 있는 문제라 가져왔습니다.

 

https://leetcode.com/problems/queries-on-a-permutation-with-key/

Queries on a Permutation With Key - LeetCode

가봅시다 !

---

이 문제는 1 ~ m이라는 순열 (순열이란 표현이 맞는가 잘 모르겠는데...?) query가 주어집니다.

 

query 안에는 숫자가 있고 1 ~ m까지 순열에서 그 수를 찾아서 그 수를 제일 앞 쪽으로 이동시켜주고,

 

그 수의 index를 result에 추가를 해나가면서, 마지막까지 query를 돌았을 때이 result 값을 뱉어주면 되는 문제입니다.

---

간단해보일수도 있는 문제입니다만... (Python을 쓰면 너무 간단합니다)

 

직접 코드를 짜서 하려고 하면 좀 막막합니다. 왜냐 시간 복잡도가 O(N^2)이 될 수 있기 때문인데요. Query가 항상 순열의 제일 마지막 숫자만을 가져오라고 했을 시, 그 수를 제일 앞에 옮기고 나서 모든 숫자를 뒤로 밀어내야하기 때문이죠.

다른 숫자 다 꺼져

그렇다면 저희는 생각을 해야합니다만...  앞서 Python을 쓰면 간단하다고 했습니다.

 

그렇다면 우선 Python으로 해보도록하죠

 

class Solution:
    def processQueries(self, queries: List[int], m: int) -> List[int]:
        result = []
        p = [i for i in range(1, m + 1)]
        
        for i in queries:
            idx = p.index(i)
            result.append(idx)
            num = p.pop(idx)
            p = [num] + p
            
        return result

초초초초초초 간단하죠?

 

query에서 숫자를 꺼내고 그 수를 built-in 함수로 index를 찾아서, result에 추가하고, 걔를 뽑아내서 제일 앞으로 보내주기만 하면 !?

 

끝

 

초간단

하지만 저희는 보다 지적인 개발자가 되기 위해 다른 방법들도 찾아봐야 할 것입니다.

 

뭐 자료구조 deque을 쓴다면 이동에서 O(1)이 걸릴테니 query 숫자 갯수 * 숫자 찾기 (O(N)) 만큼의 시간이 걸릴 수 있겠죠?

 

다른 방법은 뭐 있을까요?

 

저는 세그먼트 트리의 구간합을 이용해서 한 번 문제를 해결해보았습니다.

---

https://ggodong.tistory.com/221

307. Range Sum Query - Mutable

이 문제에서 Segment Tree에 대해 잘 설명했으니, 모르시겠으면 보시고 오는 것을 추천합니다.

 

그렇다면 도대체 어떻게 !? Segment Tree를 이용하느냐 !?

 

?

m이 5라고 합시다. 그렇다면 저희는 1, 2, 3, 4, 5라는 순열을 가졌을 겁니다.

 

그러고 Query에 3이라는 수가 나왔다면 3의 앞자리 1, 2의 갯수 만큼만 result에 추가를 해주면 됩니다. 그렇다면 저희는 Tree를 만들 수가 있는데, [0, 1(1), 1(2), 1(3), 1(4), 1(5)]로 구성된 Tree를 만들 수 있겠죠. (0번 index는 편의상 사용하지 않습니다)

 

이렇게되면 1 ~ 3 - 1만큼의 구간합을 구해 result에 넣으면 되니까요.

 

근데 문제가 있습니다. 저희는 솎아낸 숫자를 제일 앞으로 넣어야합니다. 그런데 Tree의 길이가.... 충분치 않죠. 넣을려고 해도 자리가 없어요.

 

그렇기 때문에 query의 갯수(4개라고 가정) 만큼 앞에 자리를 확보를 해놓아야합니다.

 

만약 자리가 확보되었다고 생각해봅시다. [0, 0, 0, 0, 0, 1(1), 1(2), 1(3), 1(4), 1(5)]

 

1로 채워진 숫자는 순열이라고 생각하시면 됩니다.

 

그럼 다시 Query에서 3이라는 숫자가 나왔다고 했을 때, 어떻게 하면 될까요? query의 갯수 (4개) + 3 - 1만큼의 합을 구하면 되겠죠?

 

그리고 원래 3이 있던 위치를 0으로 바꾸고(update 0으로 한 번), 앞 쪽으로 이동시켜주면 됩니다.(update 1로 한 번)

 

[0, 0, 0, 0, 1(3), 1(1), 1(2), 0, 1(4), 1(5)] 이렇게하면 다음 Query에서 숫자 1이 나온다하더라도, query의 갯수 (4개) + 1 - 1만큼의 합을 구하면 문제 해결이 될 수 있습니다.

 

그렇다면 저희는 각 숫자가 Tree의 어떤 index에 있는지 따로 저장을 해야할 것이며, 숫자가 솎아져서 제일 앞쪽으로 들어갈 수 있게, Tree의 제일 앞 쪽 위치를 계속해서 갱신을 해주어야 할 것입니다.

 

이 것만 된다면, 나머지는 일반 Segment Tree의 구간합으로 해결이 가능합니다.

 

코드를 보시죠

class Solution:
    def __init__(self):
        self.po = [0 for i in range(1000 + 10)]
        self.tree = [0 for i in range(2000 * 3)]
        self.Max = 0
        self.M = 0
        self.result = []
        
    def update(self, n, s, e, idx, data):
        if s == e:
            self.tree[n] = data
            return
        
        mid = (s + e) // 2
        
        if idx <= mid:
            self.update(n * 2, s, mid, idx, data)
        else:
            self.update(n * 2 + 1, mid + 1, e, idx, data)
        
        self.tree[n] = self.tree[n * 2] + self.tree[n * 2 + 1]
        
    
    def query(self, n, s, e, qs, qe):
        if qe < s or e < qs:
            return 0
        elif qs <= s and e <= qe:
            return self.tree[n]
        else:
            mid = (s + e) // 2
            return self.query(n * 2, s, mid, qs, qe) + self.query(n * 2 + 1, mid + 1, e, qs, qe)
        
        
    
    def processQueries(self, queries: List[int], m: int) -> List[int]:
        self.Max = len(queries)
        self.M = self.Max
        
        # init tree
        for num in range(1, m + 1):
            self.po[num] = self.Max + num
            self.update(1, 1, self.Max + m, self.Max + num, 1)
        
        # query
        for q in queries:
            idx = self.po[q]
            self.result.append(self.query(1, 1, self.Max + m, 1, idx - 1))
            # update 0
            self.update(1, 1, self.Max + m, idx, 0)
            
            # update 1
            self.update(1, 1, self.Max + m, self.M, 1)
            self.po[q] = self.M
            self.M -= 1
        
        return self.result

괜찮쥬?

---

이상 1409. Queries on a Permutation With Key였습니다. ^_^