Computer >> 컴퓨터 >  >> 프로그래밍 >> Python

파이썬(Python)으로 방향 문자열 균형 맞추기: 네 방향이 각각 n/4회씩 등장하도록 최소 교체 구간 구하기

문제 소개

문자열 s가 주어지며, 이 문자열은 북(N), 남(S), 서(W), 동(E)을 나타내는 네 가지 방향 문자 "N", "S", "W", "E"로만 구성되어 있다고 가정해 봅시다. 우리의 목표는 네 방향이 각각 정확히 n/4번씩(단, n은 문자열 s의 길이) 등장하도록 문자열의 일부를 교체할 때, 교체 대상이 되는 가장 짧은 부분 문자열의 길이를 구하는 것입니다.

예를 들어 입력이 s = "NNSWWESN"라고 해보겠습니다. 이때 n은 8이므로 각 방향은 8 ÷ 4 = 2번씩 나타나야 합니다. 마지막 문자 'N'을 'E'로 단 한 글자만 바꾸면 모든 방향이 정확히 두 번씩 등장하게 되므로, 정답은 1입니다.

해결 접근 방법

이 문제는 슬라이딩 윈도우(Sliding Window) 기법과 빈도수 분석을 결합하면 효율적으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.

  • 먼저 각 방향 문자의 개수를 세어, 목표치(quarter = n/4)보다 많이 포함된 문자를 찾아냅니다.
  • 초과된 문자들을 제거하기 위해 교체 구간 안에 반드시 포함되어야 할 개수를 음수 형태의 목표값(target)으로 저장합니다.
  • 두 포인터(left, right)로 윈도우를 확장·축소하며, 초과 문자들이 충분히 포함되는 최소 구간을 탐색합니다.

구체적인 알고리즘 단계는 다음과 같습니다 −

  • n := 문자열 s의 길이
  • n이 0이면 0을 반환합니다.
  • quarter := (n / 4)의 내림 값
  • count := s에 포함된 각 문자의 빈도수 목록
  • target := 새로운 딕셔너리(맵)
  • count의 각 쌍 (dir, cnt)에 대해 다음을 수행합니다.
    • cnt > quarter라면 target[dir] := quarter − cnt
  • target이 비어 있다면 이미 균형이 잡혀 있는 상태이므로 0을 반환합니다.
  • left := 0, min_len := 무한대(∞)
  • s의 각 인덱스 right와 방향 문자 dir에 대해 다음을 수행합니다.
    • dir이 target에 있다면 target[dir] := target[dir] + 1
    • target의 모든 값 중 최솟값이 0 이상인 동안 다음을 반복합니다.
      • min_len := min_len과 (right − left + 1) 중 더 작은 값
      • s[left]가 target에 있다면 target[s[left]] := target[s[left]] − 1
      • left := left + 1
  • min_len을 반환합니다.

구현 예시

다음 파이썬 코드를 통해 더 잘 이해해 보겠습니다 −

from collections import Counter

def solve(s):
    n = len(s)

    if not n:
        return 0

    quarter = n // 4

    count = Counter(s)
    target = dict()
    for (dir, cnt) in count.items():
        if cnt > quarter:
            target[dir] = quarter - cnt

    if not target:
        return 0

    left, min_len = 0, float("inf")
    for right, dir in enumerate(s):
        if dir in target:
            target[dir] += 1

        while min(target.values()) >= 0:
            min_len = min(min_len, right - left + 1)
            if s[left] in target:
                target[s[left]] -= 1
            left += 1

    return min_len

s = "NNSWWESN"
print(solve(s))

입력

"NNSWWESN"

출력

1