[Kickstart][2020][Round B] 3. Robot Path Decoding

문제 : https://codingcompetitions.withgoogle.com/kickstart/round/000000000019ffc8/00000000002d83dc

---

(1, 1) 좌표에서 시작해서 109개의 행, 열이 있는 좌표가 있다.

(w, h)는 w번째 열, h 번째 행을 의미한다.

이동하는 방법이 문자열로 주어진다.

WEST는 방향을 의미한다. (W: West, E: East, S : South, N: North)

X(Y) 형식으로도 표현하는데 X는 2~9인 숫자이고, Y는 이동하는 방법이 주어진다. X(Y)는 Y를 X번 반복하는 것을 의미한다.

예를 들어, 2(S2(E))는 SEESEESEE와 같다.

이동이 끝난후 w, h를 구해라.

---

 

가능한 숫자가 2~9 이기 때문에 숫자가 나오는 경우 나오는 변수의 횟수를 저장하는 변수를 하나두고(let, mul) 거기에 곱해준다.

이 때, 모듈러 법칙으로 어차피 1e9를 나머지한 결과를 반환하기 때문에 곱할때도 곱한 값에 1e9 나머지연산을 해서 저장해준다.

보통 올바른 괄호열하면 스택을 많이 쓰는데 이경우도 비슷하다.

열린 괄호가 나올때 이전에 나온 수를 스택에 저장하면서 mul 변수에 해당 수를 곱해주고, 닫힌 괄호가 나오는 경우 스택의 top에 있는 수를 mul에 나눠준다.

이 때, 곱한 mul의 값이 엄청 커질수도 있어서 곱할 때 모듈러 연산을 해주었다. 그래서 스택에서 값을 뺄 때, 그냥 나눠주기만 하면 계산 결과가 이상할수도 있다. 그래서 이 경우 스택에 있는 모든 요소를 다시 곱해줘서 mul을 다시 구해줬다.

숫자, 괄호가 아닌 EWNS 문자가 나오는 경우 이동하는 방향 좌표에 mul을 곱해서 이동 시킨 후, 1e9를 나머지 연산해준다.

이때, 좌표가 마이너스인 경우 나머지 연산을하면 결과가 이상해지기 때문에 나머지 연산하기 이전에 1e9를 더해줘서 양수로 만든 후 나머지 연산을한다.

---

소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/codejam/kickstart/2020/roundB/3.%20Robot%20Path%20Decoding.cpp