Written by Lee Jongseo
on May 22, 2021

Leetcode[1]⭐ - 1025. Divisor Game, 1221. Split a String in Balanced Strings, 104. Maximum Depth of Binary Tree

1025. Divisor Game

Keyword: Dynamic Programming

Base Factor: n이 2일 때, True. n이 3일 때, False.

==> 2를 넘겨 받은 사람이 Win. 3을 넘겨 받은 사람은 Loose

그렇다면 n이 4인 경우는 ?

Alice와 Bob 둘다 optimally play한다고 가정한 상황.

Alice는 자기가 이기기 위해서 1을 선택. 그러면 Bob은 3을 넘겨받고 Loose.

==> 4를 넘겨 받은 사람이 Win.

n이 5인 경우는 ?

선택가능한 x는 1. Bob은 4를 넘겨받기 때문에 Alice는 Loose.

==> 5를 넘겨 받은 사람은 Loose.

마지막으로 n이 6인 경우는 ?

Alice는 5를 넘겨 받은 사람이 진다는 것을 아니까, 1을 선택.

==> Alice는 짝수를 넘겨 받게 되면 x로 1을 선택하면 항상 이긴다.

Alice 시점에서, n이 짝수인 경우, 그 전의 결과로 인해 1을 빼면 항상 승리한다.
Alice 시점에서, n이 홀수인 경우, 홀수 - 홀수 = 짝수이기 때문에 항상 패배한다.

Code

class Solution:
    def divisorGame(self, n: int) -> bool:
        return n % 2 == 0

1221. Split a String in Balanced Strings

Balanced String

문자열이 문제처럼 오직 두 가지 요소로 이루어져 있을 때, 두 요소의 수가 동일한 경우, 그 문자열을 Balanced String이라 한다.

# 문자열 S가 balanced인지 아닌지 체크
def is_balance(S):
    # balance 상태를 나타내는 변수. 0이면 balanced
    # 특정한 상태를 숫자로 나타낼 수 있음!
    balance = 0
    # 문자열을 이루고 있는 두 가지 요소를 나타내기 위한 변수
    s1, s2 = S[0], ""
    for c in S:
        if c != s1:
            s2 = c
            break
    # 하나는 1, 다른 하나는 -1을 나타내여 balance인 경우 최종적으로
    # 0이 되도록 순회.        
    for c in S:
        if c == s1:
            balance += 1
        if c == s2:
            balance -= 1
    return balance == 0
    

Balanced substring

Balaned string을 Balanced substring으로 split하는 경우 최대 몇개의 substring으로 split할 수 있는지 알아 내는 문제.

Balanced string을 이루고 있는 두 가지 요소를 각각 숫자 1과 -1에 대응시키킬 수 있다.
Balanced 상태는 숫자의 합이 0인 상태다.
R을 1, L을 -1에 대응시킨다.
RL 또는 LR은 0인 상태다.
string을 순회하여 0이 등장하는 횟수가 substring의 maximum amount이다.

Python Implementation

class Solution:
    def balancedStringSplit(self, s: str) -> int:
        balance = count = 0
        for c in s:
           if c == "R": balance += 1
           else: balance -= 1
           if balance == 0: count += 1
        return count

Stack을 이용한 풀이법

스택에 스트링의 첫번째 요소를 먼저 넣는다.
이후 순회에서 R을 만나면 스택에 push하고 L을 만나면 pop한다.
pop한 순간에 stack이 비어있으면 count를 1 증가시킨다.

class Solution:
    def balancedStringSplit(self, s: str) -> int:
        # stack에 첫번째 요소를 넣고 시작한다.
        stack = [s[0]]
        count = 0
        for c in s[1:]:
            if stack and (stack[-1] != c):
                stack.pop()
            else:
                stack.append(c)
            if not stack:
                count += 1
        return count

104. Maximum Depth of Binary Tree

👈 👉 Top