[PGS] 조이스틱 - Level 2

혜혜·2024년 6월 24일

Problem Solving programmers

PS

목록 보기

8/8

이번주 문제

📚 문제 내용

조이스틱으로 알파벳 이름을 완성하는 문제. 맨 처음엔 A로만 이루어져 있음.
ex) 완성해야 하는 이름이 세 글자면 AAA, 네 글자면 AAAA

조이스틱 방향에 따른 의미

▲ - 다음 알파벳
▼ - 이전 알파벳 (A에서 아래쪽으로 이동하면 Z로)
◀ - 커서를 왼쪽으로 이동 (첫 번째 위치에서 왼쪽으로 이동하면 마지막 문자에 커서)
▶ - 커서를 오른쪽으로 이동 (마지막 위치에서 오른쪽으로 이동하면 첫 번째 문자에 커서)

ex) "JAZ"를 만드는 방법

- 첫 번째 위치에서 조이스틱을 위로 9번 조작하여 J를 완성합니다.
- 조이스틱을 왼쪽으로 1번 조작하여 커서를 마지막 문자 위치로 이동시킵니다.
- 마지막 위치에서 조이스틱을 아래로 1번 조작하여 Z를 완성합니다.
따라서 11번 이동시켜 "JAZ"를 만들 수 있고, 이때가 최소 이동입니다.

만들고자 하는 이름 name이 매개변수로 주어질 때, 이름에 대해 조이스틱 조작 횟수의 최솟값을 return 하도록 solution 함수 만들기.

제한 사항

name은 알파벳 대문자로만 이루어져 있음
name의 길이는 1 이상 20 이하

입출력 예

name	return
"JEROEN"	56
"JAN"	23

✍️ 문제 분석

처음에 생각한 풀이

name 한 글자씩 돌아가면서 A가 아닌 위치를 찾음 → 배열
다음 위치에 대해 ◀, ▶ 중 어느 커서를 통해 이동하는 게 더 빨리 도달할 수 있는지 구하기 (현재 위치 가지고 있어야 함)
이동해서 해당 글자가 ▲, ▼ 중 어느 커서를 통해 알파벳을 바꾸는 게 타겟 알파벳에 더 빨리 도달할 수 있는지 구하기
A가 아닌 위치 배열 끝까지 도달할 때까지 반복

최종 풀이

처음에 생각한 풀이와 거의 동일
2번은 "현재 위치"를 고려해야 하고, 3번은 고려하지 않아도 됨(항상 'A'에서 시작하니까)

💻 내 코드

def solution(name):
    answer = 0
    locaiton = 0
    wrongPos = []
    
    for i in range(len(name)):
        if name[i] == 'A':
            pass
        else: 
            wrongPos.append(i)
    
    if len(wrongPos) > 0:
        for j in range(len(wrongPos)):
            location = wrongPos[j]
            answer += calculateLessAdd(ord('A'), ord(name[wrongPos[j]]), ord('Z'))
            
            if(j < len(wrongPos) - 1):
                answer += calculateLessMove(j, wrongPos[j+1], len(name) - 1)
            
    
    return answer

def calculateLessAdd(curVal, nextVal, lastVal):
    front = nextVal - curVal
    back = lastVal - nextVal + 1
    
    return front if front < back else back


def calculateLessMove(curLoc, nextLoc, lastLoc):
    front = nextLoc - curLoc
    back = curLoc + (lastLoc - nextLoc) + 1
    
    return front if front < back else back

44.4점...(;;)

'A'가 아닌 문자 위치를 찾는 wrongPos 배열 생성
바뀌어야 하는 문자가 있으면, if문 진입
해당 문자 위치에서 더 적은 움직임을 구해 더함
다음 위치까지의 더 적은 움직임을 구해 더하고 이동
함수는 일부러 모듈화를 위해 분리했는데 알파벳인지 위치인지에 따라 back에서 curLoc을 더해줄지 말지로 분리해도 상관없을 것 같다

📌 다른 풀이

chatgpt의 풀이

def solution(name):
    # 각 문자를 변경하는 데 필요한 조작 횟수를 계산
    def char_to_move_count(c):
        return min(ord(c) - ord('A'), ord('Z') - ord(c) + 1)
    
    total_moves = 0
    n = len(name)
    
    # 각 문자의 조작 횟수를 더해줌
    for char in name:
        total_moves += char_to_move_count(char)
    
    # 좌우 이동 최적 경로 계산
    min_move = n - 1  # 초기값: 오른쪽으로 쭉 가는 경우
    for i in range(n):
        next_index = i + 1
        while next_index < n and name[next_index] == 'A':
            next_index += 1
        # (왼쪽으로 갔다가 돌아오는 경우 vs 오른쪽으로 쭉 가는 경우) + 중간의 A 갯수 고려
        min_move = min(min_move, i + i + n - next_index, i + (n - next_index) * 2)
    
    total_moves += min_move
    return total_moves

각 문자를 변경하는 데 필요한 조작 횟수를 먼저 계산
확실히 이걸 먼저 구하고 경로를 구하는 게 더 편리할 것 같다... ㅠㅠ
왔다갔다 없이 순방향으로만 쭉 진행했을 경우(최소 이동) → min_move
다음 글자가 'A'면 그냥 쭉쭉 쩐진
'A'가 아닌 글자를 만나면(이게 next_index)
- min_move
- 왼쪽으로 갔다가 돌아오는 경우: 현재 위치까지 이동 + 다시 왼쪽 끝까지 이동 + 다음 위치로 이동
- 오른쪽으로 쭉 가는 경우: 현재 위치까지 이동 + 다음 위치로 이동 + 다시 현재 위치로 돌아옴
  
  중에 최소값으로 갱신
사실 이 부분은 잘 이해가 안 간다... 흠

프로그래머스에 있는 다른 풀이

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
        distance = min(idx, n - next_idx)
        move = min(move, idx + n - next_idx + distance)

    answer += move
    return answer