LeetCode 394. Decode String
문제분석
인코딩이 되어있는 문자열에 대해서 디코딩을 해서 문자열을 반환하기.
인코딩 규칙: k[encoding_string] 이렇게 인코딩이 되어있으면 괄호 안에 들어있는 문자열에 대해서 k번 반복되어 있다는 것을 의미한다. k는 항상 양수이다.
인풋으로 들어오는 문자열이 항상 유효한 문자열이고, 공백은 없으며, 괄호가 잘 형성되어있다. (예외 처리를 할 필요 없다는 의미)
더하여, 데이터는 숫자와 괄호안에 들어있는 문자열이 정확히 구분된다. 예를들어서 괄호안에 들어있는 문자열은 숫자를 포함하지 않는다.
즉 3a, 2[4] 같은 문자열은 인풋으로 들어오지 않음.
Input: s = "3[a]2[bc]"
Output: "aaabcbc"
Input: s = "3[a2[c]]" => 3[acc] => accaccacc
Output: "accaccacc"
Input: s = "abc3[cd]xyz"
Output: "abccdcdcdxyz"
Input: s = "100[leetcode]"
Output: leetcode X 100돌파구
문자열을 인코딩하거나 디코딩하는 문제는 정규표현식을 이용하면 쉽게 해결 가능하다.
하지만, 이 문제를 해결하기 위해서 한 번 더 생각해야 할 점이 있었는데 중첩된 괄호를 어떻게 처리할 것인가? 에 대한 문제였다.
Input: s = "3[a2[c]]" => 3[acc] => accaccacc
Output: "accaccacc"이런 인풋이 들어온다면, 괄호 안에 있는 문자열을 먼저 디코딩 해야 괄호안에 담긴 순수한 a부터 z까지의 문자열을 다시 디코딩 할 수 있다. 이를 해결하기 위해서 중첩되지 않은 순수한 number[characters] 문자열을 정규표현식으로 매칭해서 replace를 해주고, 이 순수한 문자열이 모두 다 디코딩이 되면 최종적으로 문자열에 대해 디코딩이 끝난 것이다. 즉, 숫자를 매핑하는 정규표현식을 while 안의 조건으로 넣어주어서, 숫자가 매칭이 되면 계속해서 위의 순수한 number[characters] 문자열을 디코딩하는 로직을 실행한다.
이 때, str.replace(regular expression, str you want to put || callback function ) 메소드를 사용할 수 있다. JavaScript에서 String 자료형에 사용할 수 있도록 내장되어 있는 함수다. 이번에 이 문제해결을 위해 찾아 보았더니 엄청난 기능이 있다는 것을 알았다.
간단한 사용법은 아래와 같다. 첫번째 인자에는 찾고자 하는 문자열을 두번째 인자에는 그것을 대신하는 문자열을 집어 넣는다.
첫번째 인자에는 또한 정규표현식이 올 수 있다.
숫자를 매핑해서 두번째 인자로 들어온 a로 치환했다.
이 메소드의 강력한 사용법은 아래와 같다. 그리고 이 사용법이 이번 디코딩을 위한 핵심적인 역할을 했다.
본래에 replace 함수의 두번째 인자에 문자열을 바로 넣었지만, 이번 문제에서는 순수한 number[charactes] 문자열을 맵핑하고,decoding한 값으로 치환하는 것이 필요했다. 위와 같이 두번째 인자에는 callback function이 들어갈 수 있는데, 첫번째 인자로 매핑된 문자열이 들어온다. 즉 위의 케이스에서는 number[characters] 문자열을 지지고 볶아서 디코딩해서 return 하면 디코딩이 완료되는 것이다.
중간에 지지고 볶는 로직은 다음과 같다.
- 숫자 매핑
- 괄호안의 순수한 캐릭터 매핑
return 순수한캐릭터.repeat(숫자)
number[characters] 문자열 매핑을 위한 정규표현식 톺아보기
/\d+\[[a-z]+\]/gi
- \d: 숫자
- +: 앞의 토큰(숫자)에 대해서 1개 이상인 것을 매핑한다.
\[: \는 Escaped Character 다. 괄호와 같은 문자열은 순수한 문자열이 아니기 때문에 back space와 함께 정규표현식을 써야한다.[a-z]: a부터 z까지의 모든 문자를 매핑한다.- +: 앞의 토큰(
[a-z])에 대해서 1개 이상인 것을 매핑한다. \]: 위의\[와 같이 괄호이기 때문에 back space와 함께 표현
정규표현식의 시작과 끝은 /(슬래쉬) 로 표현한다. 그리고 뒤에 오는 것은 정규표현식을 어떻게 매핑할지에 대한 옵션인데
- g는 global을 의미하고
- i는 insensitive 즉, 캐릭터에 대해서 대소문자를 가리지 않고 매핑하게 하는 옵션이다.
구현
- 인풋으로 들어온 str 에 숫자가 매칭되면 아직 디코딩이 끝나지 않은 것이다. => while 문 안의 로직을 계속 돌림
- 처음에 repeatNumber를 구하기 위해서 숫자를 parsing하는 코드에서 정규표현식을
/\d/gi로 해줬을 때 두자리 이상의 숫자일 때에는 배열에 각각 하나씩 담기기 때문에/\d+/gi+를 붙여주어서 숫자를 하나로 매칭하도록 코드를 수정했다.
