[문제] 3가지 조건을 만족하는 문자열 변경

 

Leetcode 의 225회 주간 대회 (Weekly Contest 225, Q2) 2번 문제이다.

leetcode.com/problems/change-minimum-characters-to-satisfy-one-of-three-conditions/

개인적으로 아마추어의 수학 실력을 가지고 소프트웨어 엔지니어로 먹고산 지 20년이 되었다. 20년이 되고 나니.. 알고리듬과 수학의 유사한 부분과 차이.. 그리고 어떻게 하면 알고리듬 실력을 향상 시킬 수 있을 지 이해하는 것 같다.

특히 이러한 문제를 보고... 주어진 제한 시간 내에서 이런 아이디어를 만들어서 코드까지 돌려서 통과할 수 있는 사람은 몇 안된다고 생각한다. 왜냐하면.. 이러한 높은 난이도의 문제를 쉽게 해결하는 많은 고수들의 답안들을 자세히 분석해 보면.... 대부분의 고수들은 이러한 문제에 필요한 아이디어를 이전에 알고 있었다는 확신을 여러 번 받았기 때문이다.

물론 알고리듬에 나오는 수많은 이론들 (DFS, BFS, Binary Search, Segment Tree 등)을 알고 이러한 지식의 적용 훈련을 받아야 하지만, 결국 초보자와 상급자의 가장 큰 차이는.. 수많은 대회들을 통해서 "이러한 좋은 문제들의 유형을 (개인적으로 잘 정리해서) 가지고 있거나 없고의 문제"로 귀결되는 느낌이다.

(혹시라도 읽어볼 수 있는 분들을 위하여 이 문제에 대한 요구사항과 필요한 자세히 설명을 하지 않음을 먼저 밝힌다. 관심있는 분들은 Leetcode 의 해당 문제를 참조하기 바란다.)

두 개의 문자열... s 와 t 가 다음과 같을 때...

s = dabadd

t = cda

각각의 문자열에서 가지고 있는 알파벳 수는

(아래의 붉은 색 블럭으로 표시한) s는  a: 2, b: 1, d: 3 가 되고 

(녹색 블럭으로 표시된) t는 a: 1 c: 1, d:1 가 되면서... 아래와 같이 블럭으로 표시할 수 있다.

 

그리고  (검은 색 선을 중심으로...) 전체 블럭을 좌우로 옮기는 작업으로 문제는 바뀌게 된다.

결국 각 단계별로 붉은 색과 녹색의 블럭을 좌우로 완전히 구분하기 위하여

옮겨야 하는 전체 블럭의 합 = 아래 위의 둥근 사각형으로 표시한 블럭 갯수들의 합 이 된다.

(참고로) 왼쪽과 오른 쪽은 각각 condition 1 / 2 의 경우를 표현한 것이 된다.

 

아래는 각각 Javascript 와 Python 으로 구현한 코드들이다.

Javascript 

@copyright : yunha0221

Python

leetcode.com/problems/change-minimum-characters-to-satisfy-one-of-three-conditions/