프로그래머스 조이스틱

https://school.programmers.co.kr/learn/courses/30/lessons/42860

프로그래머스

📌 해결 순서

문제 다 읽자마자 한 단어마다 A로 다시 이동하는데 필요한 조이스틱 이동 횟수를 담아두는 배열을 만들어 두면 편할것 같다는 생각이 들어서 우선 만들고 시작했다.

이제 해결해야 되는건 좌, 우 이동을 어떻게 할것이냐 인데,, 좀 까다롭다

 

이미 A로 만들어져 있는 문자에 대해선 조이스틱을 움직일 필요가 없으므로, 좌 우 이동만 하면 되는데 문제는 어떻게 이동 횟수를 최소로 만들것이냐에 대한 것이였다.

 

ex) name = CAACAAAAB

가장 긴 A로된 문자열의 길이는 4 

start = 3

end = 8 

1. 가장 긴 A 의 왼쪽부터 시작하기

조이스틱을 오른쪽으로 start 만큼 이동해서 CAAC 까지 이동하고 모두 A로 변경하고 다시 돌아온다.

그리고 왼쪽으로 len(name) - end 만큼 이동해서 제일 끝의 B를 A로 변경한다.

cnt = 3 * 2 + 1 = 7

2. 가장 긴 A의 오른쪽 부터 시작하기

조이스틱을 왼쪽으로 len(name) - end  만큼 이동해서 B 까지 이동해서 모두 A로 변경하고 다시 돌아온다.

그리고 오른쪽으로 start번 이동하면서 CAAC 를 모두 A로 변경한다

cnt = 1 * 2 + 3 = 5

3. 순차적으로 이동하기

cnt = len(name) - 1 = 8

 

주어지는 각 문자열에 대해서 가장 긴 A로된 문자열을 찾고 3개의 경우중 가장 적은 이동 횟수를 찾으면 된다

 

📌 코드

def solution(name):
    answer = 0
    move_min = len(name) - 1
    cnt_lst = [min(abs(ord('A') - ord(i)), abs(ord('Z') + 1 - ord(i)))
               for i in name]
    answer += sum(cnt_lst)
    max_length = - 1

    for i in range(len(name)):
        next = i + 1
        while next < len(name) and name[next] == 'A':
            next += 1

        if max_length < next - i - 1:
            max_length = next - i - 1
            start = i
            end = next
    move_min = min(move_min, 2 * start + len(name) -
                   end, 2 * (len(name) - end) + start)
    return answer + move_min

그런데 이렇게 풀면 27개의 테케중 1개만 실패한다.. 그 이유를 도저히 모르겠다.

로직은 틀리지 않은것 같은데 그래서 일단 기록

 

나는 가장 긴 A의 길이를 구하고 그 시작과 끝 인덱스를 사용해서 문제를 풀었는데,

구글링을 해서 다른분들의 풀이를 보니까 반복문을 돌때마다 3개의 경우에 대한 최솟값을 계속 업데이트 해가는식으로 푸신것 같았다.

 

📌 코드

def solution(name):
    answer = 0
    move_min = len(name) - 1
    cnt_lst = [min(abs(ord('A') - ord(i)), abs(ord('Z') + 1 - ord(i)))
               for i in name]
    answer += sum(cnt_lst)

    for i in range(len(name)):
        next = i + 1
        while next < len(name) and name[next] == 'A':
            next += 1

        move_min = min(move_min, 2 * i + len(name) -
                       next, 2 * (len(name) - next) + i)
    return answer + move_min