[PROGRAMMERS]-조이스틱 (Greedy)
📃 조이스틱
풀이
-
상, 하 조작 횟수와 좌, 우 조작 횟수를 따로 구해서 더해주면 된다.
좌, 우 조작 횟수의 경우1) 왼쪽에서 시작해서 오른쪽으로 한방향으로만 이동하는 경우 2) 왼쪽에서 시작해서 오른쪽으로 이동하다가 방향을 바꾸어 왼쪽으로 이동하는 경우
가 있다. -
첫번째는 문자열 길이와 조작 횟수가 같다.
-
두번째는 특정 문자까지 이동한 후(해당 문자의 인덱스) 다시 처음 글자로 되돌아가(+ 해당 문자의 인덱스) 연속된 A문자의 다음 문자까지 마지막 위치에서부터 거꾸로 이동(+ 문자열 길이 - 연속된 A문자가 끝나는 위치 + 1)하면 된다.
-
distance = min(idx, n - next_idx)
idx > n-next_inx
일 때
ex) BHCAAN 인 경우
B -> N -> B -> H -> Cidx < n-next_inx
일 때
ex) CPAANTQ 인 경우
C -> P -> C -> Q -> T -> N
코드
def solution(name):
answer = 0
n = len(name)
def alphabet_to_num(char):
num_char = [i for i in range(14)] + [j for j in range(12, 0, -1)]
return num_char[ord(char) - ord('A')]
# 위 아래 조작
for ch in name:
answer += alphabet_to_num(ch)
move = n - 1
# 커서 좌우 이동
for idx in range(n):
next_idx = idx + 1
while (next_idx < n) and (name[next_idx] == 'A'):
next_idx += 1
# idx 에서 되돌아 가는 경우 / 뒤에 있는 문자열부터 갔다오는 경우
distance = min(idx, n - next_idx)
# 한 방향으로만 이동하는 경우와, 오른쪽으로 이동했다가 왼쪽으로 이동하는 경우를 비교
move = min(move, idx + distance+ n - next_idx)
answer += move
return answer
Author And Source
이 문제에 관하여([PROGRAMMERS]-조이스틱 (Greedy)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@zioo/PROGRAMMERS-조이스틱-Greedy저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)