본문으로 건너뛰기

3443 - Maximum Manhattan Distance After K Changes

정보

풀이 키워드​

스포주의

수학


풀이 코드​

정보
  • 메모리: 45670 KB
  • 시간: 47 ms
class Solution {
    public int maxDistance(String s, int k) {
        char[] sArr = s.toCharArray();
        int N, S, E, W;
        N = S = E = W = 0;

        int ans = 0;
        for (int i = 0; i < sArr.length; ++i) {
            char ch = sArr[i];

            if (ch == 'N') ++N;
            else if (ch == 'S') ++S;
            else if (ch == 'E') ++E;
            else ++W;

            int d1 = Math.abs(N - S);
            int d2 = Math.abs(E - W);
            int md = d1 + d2;
            int cand = md + Math.min(2*k, i+1-md);
            ans = ans < cand ? cand : ans;
        }

        return ans;
    }
}

풀이 해설​

문자열의 각 방향 문자에 대해 순차적으로 좌표를 이동시킬때, 최대 순간 Manhattan Distance를 구하는 문제이다.

풀이할 때 여러 시도를 해보았는데 그리디하게 '우리팀', '상대팀' 나눠서 처리하는 것은 WA이다.

대부분 어느 한 세력 (ex. N < S 또는 E > W) 크기가 확실하게 더 크면 해당 팀을 k로 지원하는게 먹히기는 한데

세력의 크기가 같을 때가 애매해서 문제이다.

처음엔 예제 TC를 고려해서 먼저 등장하는 녀석을 우리팀으로 지정해보았는데 그것도 WA였다.

반례
WEEW
1
답: 3

왜냐하면 상단의 반례에서 E와 W는 세력의 크기가 같지만 먼저 등장하는 W의 편을 들어주면 3이 나올 수 없기 때문이다.

그래서 아예 발상을 다르게 해야 하는데...


마법의 한 줄
for (int i = 0; i < sArr.length; ++i) {
    ...

    int d1 = Math.abs(N - S);
    int d2 = Math.abs(E - W);
    int md = d1 + d2;
    int cand = md + Math.min(2*k, i+1-md);
    ans = ans < cand ? cand : ans;
}

우선 k를 고려하지 않은 Manhattan Distance(이하 md)를 구한 뒤, 후처리로 k를 적용해주는 방식으로 접근해야 한다.

그래서 회심의 한 줄에 거의 모든 난이도가 집중되어 있는데 이는 다음과 같은 발상으로 도출될 수 있다.

i번째 이동을 했을때, 지금까지 얼마의 거리를 손해봤는가?


예를 들어 이런 입력이 주어진다고 하자.

예제
NESW

마지막 W를 순회할 때 k를 적용하지 않은 순수 md는 N-S / E-W 끼리 서로 상쇄되어 0이다.

그리고 여태까지 이동한 절대 거리(스칼라 거리)는 i를 이용해서 i+1이라고 할 수 있는데,

그렇다면 여태까지 손해를 본 거리는 (i+1)-md 라고 할 수 있다.


🤔 ok... 그럼 k는 어떻게 쓰는데?​

k는 얘를 한 번 사용했을때 거리 상 얼마의 이득을 보는지 따져보면 된다.

상단의 예제에서, S -> N으로 반칙(?)을 1번 사용하면 거리는 2가 되어 2의 이득을 보게 되고

W -> E까지 2번 사용하면 거리는 4가 되어 4의 이득을 보게 된다.

즉, k번의 반칙 사용으로 얻을 수 있는 거리적 이득은 2*k인 것이다.

따라서 주어진 최대 이득 2*k과 손실난 거리 i+1-md 중 더 작은 값만큼 손실을 메꿔주면 되고

수식은 md + {메꾼 거리} 형태가 된다.


메모​

  • 마법의 한 줄 떠올리기가 이 문제의 전부임