[LeetCode - Online Assessment 기출] Circular Printer

 

• 단어가 주어졌을때, 처음 알파벳 부터 각 알파벳에 맞게 포인터를 움직여야한다.
• 포인터의 첫번째 위치는 'A'이며, 포인터가 왼쪽, 오른쪽으로 움직일 때마다 1초씩 증가한다. 

입력 & 출력 예제

• case1
  • 입력: "BZA"
  • 출력: 4
• case2
  • 입력: "AZGB"
  • 출력: 13
• case3
  • 입력: "ZNMD"
  • 출력: 23

제한사항

• 1 <= s 문장의 길이 <= 10^5

---

문제 풀이

• 제한사항을 보면 문장의 최대길이는 10^5이기 때문에, 백트레킹을 사용하기 힘들어보인다. 
• 수학식을 사용하여 O(N) 시간이 걸리도록 구현하자.
• 이전 알파벳과 현재위치 알파벳의 아스키코드 값 차이를 구할 건데, 시작점이 A이기 때문에 문장 앞에 A를 붙인다.
• A ~ Z까지 알파벳의 총 갯수는 26개이다. 
• 즉 이전 알파벳과 현재 알파벳의 차이를 절대값으로 구하고, 포인터가 시계방향으로 갈때와 반시계방향으로 갈때의 최소 값을 구해야한다.
• 시계방향은 알파벳들의 차이 값을 사용하고, 반시계방향은 알파벳의 총 크기 26에서 차이 값을 빼주면 된다. 

소스 코드

inp = 'BZA'
ans = 0
inp = 'A' + inp
for i in range(1, len(inp)):
    pre, curr = inp[i - 1], inp[i]
    d = abs(ord(pre) - ord(curr))
    ans += min(d, 26 - d)
print(ans)