99클럽 코테 스터디 16일차 TIL + 탐욕법(Greedy) : 조이스틱

문제

링크텍스트

풀이

def solution(name):
    n = len(name)
    nameI = [ord(i) for i in name]
    nameI0 = [i for i in range(n) if nameI[i] != 65]
    n0 = len(nameI0)
    
    if n0 == 0:
        return 0
    elif n0 == 1:
        return min(nameI[nameI0[0]]-65,91-nameI[nameI0[0]])+min(nameI0[0],n-nameI0[0])
    
    dx = [nameI0[0],0]
    for i in range(1,n0):
        dxi = nameI0[i] - nameI0[i-1]
        if dxi > dx[0]:
            dx = [dxi,i]
    i = dx[1]
    cnt = min(nameI0[i-1], n-nameI0[i]) + nameI0[i-1] + n - nameI0[i]
    cnt = min(cnt, nameI0[-1])
    cnt = min(cnt, n - nameI0[0])
   
    for i in nameI0:
        cnt += min(nameI[i]-65,91-nameI[i])
        
    return cnt    
    
for i in range(6):
# for i in [2]:
    print(f'test case: {i}')
    if i == 0:
        name, r = "JEROEN",	56
    elif i == 1:
        name, r = "JAN", 23
    elif i == 2:
        name, r = "ABBAAABAAAABB", 15
    elif i == 3:
        name, r = "BAABBAAA", 7
    elif i == 4:
        name, r = "AABAAABAA", 8
    elif i == 5:
        name, r = "AAAAAAAA", 0
    a = solution(name)
    print(a)
    print(r)

• 입력 name을 정수 list로 변환하여 nameI 를 만들고, 특히 65 (=A)가 아닌 것을 모아 nameI0 를 만듭니다.

• A가 아닌 글자를 만들기 위한 커서의 조작 횟수를 간단히 구할 수 있습니다.

• 문제는 A가 아닌 글자의 위치로 이동하는 커서의 조작 횟수입니다.

  • 이동 횟수를 최적화 하기위해, 굳이 가지 않아도 되는 글자의 위치를 파악합니다.
  • 굳이 가지 않아도 되는 글자들의 연결된 뭉텅이가 중에 가장 큰 것을 구하여,
    • 그 뭉텅이의 시작점 직전이, 위의 코드에서는 nameI0[i-1]입니다.
    • 그리고 마지막 점 바로 다음이, 위의 코드에서는 nameI0[i]입니다.

• 뭉텅이를 제외하고는 어쩔 수 없이 한번은 훑어야 합니다.

• 이번 문제는 처음에는 각각의 scenario 별로 다 저장하면 풀려고 했으나 오답에 시간 초과도 걸려서, 결국 위의 방법으로 변경하였지만, test case를 모두 통과하기 위한 조건을 추가하는 것도 긴 시간이 걸렸습니다.

• 무조건 코드를 작성해 가면서 푸는 습관을 고치기가 너무 어렵습니다.

• 문제정의에는 greedy 탐색법이라 되어있는데 아직 잘 모르겠습니다. [조이스틱](https://school.programmers.co.kr/learn/courses/30/lessons/42860) 를 보고 공부해야겠습니다.

결과