[Codejam][2020][QR] 2. Nesting Depth

문제 : https://codingcompetitions.withgoogle.com/codejam/round/000000000019fd27/0000000000209a9f

---

숫자 문자열이 주어질 때, 이를 엄격하게 괄호로 묶어서 반환하라.

이 때, 괄호의 개수는 최소로 하고 숫자는 일의 자리로 판단하라 (ex. 10 은 1과 0으로 인식되지 10으로 인식되진 않는다.)

엄격하게 괄호로 묶는 방법은 숫자만큼 해당 문자를 괄호로 감싸면 된다.

 

example)

0000 -> 0000

101 -> (1)0(1)

111000 -> (111)000

1 -> (1)

1324 -> (1((3)2((4))))

---

문자열을 탐색하면서 이전 숫자와 현재 탐색중인 숫자의 차이를 구한다.

 

1. 이전 숫자가 현재 숫자보자 작다면, (열린 괄호 추가)

정답 문자열에 있는 열린 괄호의 개수가 현재 숫자를 포함하기에는 부족하다.

따라서 현재 숫자 - 이전 숫자만큼 열린괄호를 추가한다.

ex) 12 -> 2를 탐색할 때 현재까지의 정답 문자열은 1을 위해서 열린괄호가 하나 추가된 "(1"일 것이다.

2를 추가하려고 할 때, 1을 위한 열린괄호의 개수 1은 부족하다 따라서 2추가 전에 부족한 열린괄호를 추가한뒤 2를 추가한다. "(1(2"

 

2. 이전 숫자가 현재 숫자보다 크다면, (닫는 괄호 추가)

정답 문자열에 있는 열린 괄호의 개수가 현재 숫자보다 크다.

따라서 이전 숫자 - 현재 숫자만큼 닫는 괄호를 추가한다.

ex) 21 -> 이때까지 정답문자열은 "((2"이 것이고, 1 추가를 위해서는 열린 괄호가 하나 많다. 따라서 닫는 괄호를 한 개 추가한 뒤 1을 추가한다. "((2)1"

 

3. 이전 숫자와 현재 숫자가 같다면, 추가 괄호 없이 현재 수를 문자열에 추가한다.

ex) 11 -> 이때까지 정답문자열은 "(1" 일 것이고 1 추가를 위해서 어떤 괄호의 추가가 필요없다. 따라서 "(11".

 

모든 문자열을 탐색했을 때 마지막 문자 수 만큼 닫는 괄호를 추가하면 정답이 된다.

 

시간복잡도는 O(N). N = 문자열 길이.

---

소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/codejam/2020/QR/2.%20Nesting%20Depth.cpp