최근에 비슷한 문제를 풀어보고 시리즈 2번이 나왔길래 한번 풀어보았다. 문제는 첫번째 시리즈와 굉장히 유사했지만 이번에는 뒤로도 글자를 shift 할 수 있는 direction 이라는 요소가 추가되었다.
이 문제는 TLE 를 되게 조심해야 하는 문제인데. shifts 벡터를 하나씩 읽고 range 를 다른 for 룹으로 탐색하면서 글자를 올리고 내리고 했으면은 시간 초과로 통과 못했을 문제이다.
저번에 나왔던 문제보다 조금 더 심화된 내용으로 prefix sum 을 활용했어야했고 오랜만에 쓰는 알고리즘이지만 저번에 풀었던 문제에서 많이 고민했어서 그런지 잠깐 생각하니깐 금방 풀 수 있었다.
이 문제에서는 prefix sum 에 대한 공부보다는 ASCII 테이블에 대한 공부를 조금 더 했던거같다.
prefix sum 에 대한 추가적인 설명은 생략하겠다. 조금 애 먹은거는 backward direction 으로 돌아갔을때 캐릭터를 관리 해주는 방법이었는데 이게 음수 값이 되면은 ASCII 테이블에서 완전히 다른 캐릭터가 나와서 좀 어거지로 끼어 맞추었다.
배운점:
1 (s[i] - 'a') 를 할경우에는 그 캐릭터에 위치가 나온다. 예) 'b' - 'a' = 1
2 'a' 캐릭터에 위에 값을 더한다면 원하는 캐릭터가 나오고 %26 으로 overflow 를 막아주자
성장하는 사람