[Hackerrank] [Hard] Reverse Shuffle Merge

https://www.hackerrank.com/challenges/reverse-shuffle-merge/problem

Reverse Shuffle Merge | HackerRank

풀이

• 입력으로 문자열 s를 받을 때 아래 조건을 만족하는 알파벳 순으로 가장 앞선 문자열 A를 찾는 문제
  • s \in merge( reverse(A) , shuffle(A) )
  • merge 연산은 파라미터로 두 개의 string을 받는데, 각 string의 입력 순서만 맞으면 됨.
    • merge( 'abac', 'bcbc' ) -> (a)b(b)c(ac)bc 괄호안에 있는게 'abac', 없는게 'bcbc'
  • reverse 연산은 문자열을 뒤집는 것이고, shuffle 연산은 permutation을 뜻함.
• string 2개를 합쳐 입력 문자열 s가 되야하기 때문에, s의 각 문자 개수는 짝수개 -> (각 문자의 count // 2)개만큼 나눠가지게 됨.
  • s = 'abbcca' -> A는 {a:1, b:1, c:1}로 구성됨.
• s \in merge( reverse(A), shuffle(A) ) => reverse(s) \in merge( A , shuffle(A) )
• count_dict으로 각 문자열 개수 정보를 저장.
• used_dict으로 정답 후보에 사용된 문자열 개수 정보를 저장
• remain_dict으로 앞으로 남은 문자열 개수 정보를 저장.
  • 처음에 count_dict으로 초기화.
  • input string으로 iteration마다 해당 문자열 개수 1씩 감소
• reversed(input string)을 한 번 보면서 정답에 포함할지 안할지를 stack 자료구조를 사용.
  • input string의 i번째 문자가 c라고 했을 때,
  • c를 정답에 포함시킬지 말지 결정. 먼저 A에는 count_dict[c]//2개만큼의 문자가 있어야 함. 이를 used_dict[c]와 비교해 조건문 만듬.
    • (count_dict[c] // 2) > used_dict[c]
  • 중요한건 pop의 조건인데, stack 자료구조를 사용한 result에 정답 후보 문자열이 담겨있다면
    • 1. result의 마지막 문자열이 현재 iteration 문자열 c보다 크고(알파벳 순)
      2. result의 마지막 문자열이 앞으로 남은 문자열에 있어 나중에 다시 insert를 수행할 수 있을 때만 pop을 할 수 있음.(나중에 다시 넣음)
  • used_dict[c]에 1 추가, remain_dict[c]에 1 감소

def reverseShuffleMerge(s):
    from collections import defaultdict
    count_dict = defaultdict(int)
    used_dict = defaultdict(int)
    result = []

    for c in s:
        count_dict[c] += 1

    remain_dict = dict(count_dict)

    for c in reversed(s):
        if (count_dict[c] // 2) > used_dict[c]:
            while result and result[-1] > c and (used_dict[result[-1]] + remain_dict[result[-1]]) > (count_dict[result[-1]] // 2):  
                pop_char = result.pop()
                used_dict[pop_char] -= 1

            used_dict[c] += 1
            result.append(c)

        remain_dict[c] -= 1
    return "".join(result)