초보자 친화적인 가이드: LeetCode 3443 "Maximum Manhattan Distance After K Changes" 문제 풀이 (C++ | Python | JavaScript)

카테고리

프로그래밍/소프트웨어 개발

서브카테고리

웹 개발, 알고리즘, 데이터 구조

대상자

알고리즘 문제 풀이에 관심 있는 초보자 및 중급 개발자
LeetCode 문제 풀이와 관련된 테크닉을 학습하고자 하는 사람들
C++, Python, JavaScript 중 하나 이상을 사용하는 개발자

핵심 요약

k번의 방향 변경을 활용하여 최대의 맨하탄 거리를 계산
4가지 주요 방향 조합(N/E, N/W, S/E, S/W)을 사용하여 최적의 결과를 도출
선형 시간 복잡도 O(n)으로 문제 해결

섹션별 세부 요약

1. 문제 개요 및 입력 설명

s는 'N', 'S', 'E', 'W'로 구성된 문자열로, 이동 방향을 나타냄
k는 최대 허용되는 방향 변경 횟수
이동은 (0, 0)에서 시작하며, 각 방향에 따라 x, y 좌표가 변경됨
k번 이내에서 방향을 바꿔 최대의 맨하탄 거리를 계산해야 함

2. 핵심 아이디어 및 전략

각 문자열 위치에서 k번의 변경을 사용하여 최대 거리 계산
4가지 주요 방향 조합을 사용하여 각각의 경우를 탐색
방향이 목표 방향과 일치하지 않을 경우 k를 사용하여 변경
Greedy 알고리즘을 사용하여 최대 거리를 빠르게 계산

3. 구현 방법 및 예시

C++, Python, JavaScript 모두 동일한 논리로 구현
directions 배열을 활용하여 각 방향 조합을 탐색
rem 변수로 남은 k 변경 횟수를 추적
curr 변수로 현재의 맨하탄 거리를 계산
ans 변수로 최대 거리를 저장

4. 시간 및 공간 복잡도

시간 복잡도: O(n)
공간 복잡도: O(1)
n은 문자열 s의 길이

5. 예시 코드 (Python)

class Solution:
    def maxDistance(self, s: str, k: int) -> int:
        directions = [('N', 'E'), ('N', 'W'), ('S', 'E'), ('S', 'W')]
        ans = 0
        for d1, d2 in directions:
            curr = 0
            rem = k
            for ch in s:
                if ch == d1 or ch == d2:
                    if rem > 0:
                        rem -= 1
                        curr += 1
                    else:
                        curr -= 1
                else:
                    curr += 1
                ans = max(ans, curr)
        return ans

결론

4가지 방향 조합을 탐색하면서 k번의 변경을 적절히 사용
Greedy 전략으로 최대 거리를 계산하는 것이 핵심
시간 복잡도 O(n)으로 빠르게 처리 가능
C++, Python, JavaScript 모두 동일한 논리로 구현 가능