[LC] 767. Reorganize String

[seungriyou]

https://leetcode.com/problems/reorganize-string/ (similar to #70)

Approach

Idea 1: Max Heap

max heap을 이용하여 most frequent char를 추출한다. 이를 두 가지 방법으로 구현할 수 있다.

1. 70 에서처럼 cycle을 지정(2)하여, cycle 내에서 pop 된 원소들의 cnt 값을 업데이트 하기 위해 임시 저장하는 tmp를 사용할 수 있다. 이렇게 하면 cycle 내에서는 같은 문자가 반복되지 않는다. 하지만 각 cycle의 첫 번째 문자가 res에 추가된 가장 최근 문자와 동일한지 여부를 체크해야 한다.

2. 혹은, cycle을 이용하지 않고, max heap의 원소 개수가 1개 이하로 남을 때까지 두 값을 연달아 pop 하고 cnt 값을 업데이트하는 동작을 반복할 수도 있다. 해당 동작이 완료된 후에도 max heap에 원소가 남아있는 경우, 해당 원소의 남은 cnt 값이 1보다 크다면 같은 원소가 연달아 나올 수 밖에 없으므로 ""을 리턴해야 한다. 이렇게 하면 가장 최근 문자와 동일한지 여부를 체크할 필요가 없다. (한 번의 loop 내에서는 동일한 문자가 나올 수 없으므로)

Idea 2: Sorting

ref: https://leetcode.com/problems/reorganize-string/solutions/3947780/100-2-approaches-priority-queue-sort

1. counter를 생성하고 문자를 most frequent 한 순서로 정렬한다.

2. 만약, most frequent 문자가 전체 길이의 절반보다 더 많이 등장한다면, 해당 원소가 연달아 나올 수 밖에 없으므로 빠르게 ""을 리턴한다.

   if cnts[sorted_chars[0]] > (len(s) + 1) // 2:
       return ""

3. 1번에서 만든 list를 순회하면서, 현재 문자의 cnt 수만큼 결과 list(length == len(s))에 2칸씩 띄워가며 채워나간다.

   이때, first pass(i < len(s)) 에서는 index 0 부터, second pass(i >= len(s)) 에서는 index 1부터 채워나간다. (pass가 2개인 이유는 2칸씩 띄워가며 순회하기 때문)

📌 Tips

heapq.heapify() instead of heapq.heappush()

ref: https://www.geeksforgeeks.org/time-complexity-of-building-a-heap/, https://stackoverflow.com/questions/51735692/python-heapify-time-complexity, https://stackoverflow.com/questions/9755721/how-can-building-a-heap-be-on-time-complexity

• list를 순회하면서 그 값을 heap으로 만들고 싶을 때, 주로 heapq.heappush()를 사용해왔다.

  # create a counter
  cnts = Counter(s)
  
  # create a max heap
  pq = []
  for char, cnt in cnts.items():
    heapq.heappush(pq, (-cnt, char))    # -- O(nlogn) == sorting

  하지만 이렇게 하면 time complexity가 O(nlogn)(O(n) = 원소 순회 / O(logn) = heapq.heappush())이 된다.

  즉, sorting과 동일하다!

• 반면, heap으로 구성하고 싶은 값을 list로 만들고, heapq.heapify(lst)를 사용하면 전체 time complexity가 O(n) 이 된다!

  # create a counter
  cnts = Counter(s)
  
  # create a max heap
  pq = [(-cnt, char) for char, cnt in cnts.items()]
  heapq.heapify(pq)   # -- heapify = O(n)

String Concatenation w/ "".join(lst)

ref: Python: How simple string concatenation can kill your code performance

• python에서 string은 immutable object이다. 따라서 +를 통해 string concat이 발생할 때마다 기존 string이 복제(-> O(n)) 된 새로운 string object가 메모리에 생성되게 된다.

  즉, 길이가 n인 기존 string에 길이가 s인 새로운 string을 concat 하는 complexity는 O(n + s)이며, s가 1이고 만들어야 하는 문자열의 전체 길이를 m이라고 할 때 이를 loop를 돌면서 수행하면 O(m^2) 이 되게 된다.

  

• 따라서 이렇게 loop를 돌면서 concat 해야하는 경우에는 list를 이용하여 lst.append(char)(-> O(1))로 문자를 담고, "".join(lst)(-> O(n))로 문자열로 변환하는 방법을 사용하는 편이 time 측면에서 낫다. (그런데 이상하게 이번 문제에서는 string concat이 더 빨랐음..)

Complexity

• Time: (max heap) O(nlogk) (k = number of unique char) / (sorting) O(n + klogk)
• Space: O(n)