42860. 조이스틱
Level 2 조이스틱
Approach
A에서 해당 문자까지의 거리를 구하고 값을 더한다.
Attempt
1#include <bits/stdc++.h> 2using namespace std; 3 4int distance(char c) { 5 if(c == 'N') return 13; 6 if(c >='A' && c <= 'M') return c-'A'; 7 else return ('Z' - c) + 1; 8} 9 10int solution(string name) { 11 int answer = 0; 12 const int SIZE = name.size(); 13 for(int i=0; i<SIZE; ++i) { 14 answer += distance(name[i]); 15 } 16 return answer; 17}
Issues
문자를 변경할 때의 조작 횟수만 계산하고, 좌우로 움직일때의 횟수를 빼먹었다.
BAAABBBB와 같이 연속된 A의 경우는 쉽게 해결했지만, BABBBBABA와 같이 A가 떨어져 있는 경우에서
애를 먹었고, 결국 다른 코드를 참조해서 해결했다 (아래 'reference' 참고).
Solution
1#include <bits/stdc++.h> 2using namespace std; 3 4int distance(char c) { 5 if(c >='A' && c <= 'N') return c - 'A'; 6 else return 'Z' - c + 1; 7} 8 9int solution(string name) { 10 int answer = 0; 11 const int SIZE = name.size(); 12 int moves = SIZE-1; 13 14 // O(N + α) 15 for(int i=0; i<SIZE; ++i) { // O(N) 16 answer += distance(name[i]); 17 18 int j = i+1; 19 while(j < SIZE && name[j] == 'A') ++j; // +α 20 21 int a = i; 22 int b = SIZE - j; 23 moves = min(moves, min(2*a + b, a + 2*b)); 24 } 25 26 answer += moves; 27 28 return answer; 29}
Time Complexity
O(N + α)
Space Complexity
O(1)