사용자 도구

사이트 도구


ps:problems:programmers:42860

조이스틱

ps
링크programmers.co.kr/…
출처프로그래머스
문제 번호42860
문제명조이스틱
레벨Level 2
분류

애드혹

시간복잡도O(n)
인풋사이즈n<=20
사용한 언어Python
해결날짜2020/12/14
태그

고득점 Kit - 탐욕법

풀이

  • 알파벳을 설정하는 조작 (조이스틱의 위, 아래 방향)과 커서를 이동시키는 조작 (조이스틱의 왼쪽, 오른쪽 방향)을 나눠서 생각하자. 따로 구한다음에 마지막에 더해서 리턴하면 된다,
  • 알파벳을 설정하는 조작은 단순하다. 어떤 알파벳 x를 만들려면, 위로 올려서 만드는 방법과 아래로 내려서 만드는 방법, 두가지 중에서 짧은 것을 선택하면 된다.
  • 커서를 이동시키는 조작은 좀 복잡하다. 거기에 문제 자체도 헷갈리기 쉽게 되어있다.
    • 문제에서 헷갈리기 쉬운 부분은
      • 첫 번째 위치에서 왼쪽으로 이동하면 마지막 문자로 커서가 이동한다
      • 그러나, 마지막 위치에서 오른쪽으로 이동하면 첫 문자로 커서가 이동하지는 않는다
    • 그러면 이동 방식은 다음 네가지중 최소값이 된다
      • 1. 시작 위치에서 커서를 계속 오른쪽으로 이동한다
      • 2. 시작 위치에서 커서를 계속 왼쪽으로 이동한다
      • 3. 시작 위치에서 얼마만큼 커서를 오른쪽으로 이동했다가, 다시 왼쪽으로 계속 이동한다.
        • BBAAAAAAAAAABBBB 같은 경우이다,
      • 4. 시작 위치에서 얼마만큼 커서를 왼쪽으로 이동했다가, 다시 오른쪽으로 계속 이동한다.
        • BBBBAAAAAAAAAABB 같은 경우이다,
    • A가 아닌 문자의 위치를 t[i] 에 저장해 놓으면,
      • 1은 t[-1]까지 이동해야 하니까, 그냥 t[-1]
      • 2은 맨 오른쪽에서부터 t[0]까지 이동해야 하니까, len(name) - t[0]
      • 3는 t[i]번만큼 오른쪽으로 이동했다가 다시 그만큼 왼쪽으로 이동해서 제자리로 온 뒤, 맨 오른쪽에서 t[i+1]까지 왼쪽으로 이동. 그래서 t[i] + t[i] + (len(name) - t[i+1])
      • 4는 t[i+1]까지 왼쪽으로 이동했다가 다시 그만큼 오른쪽으로 이동해서 제자리로 온 뒤, t[i]까지 오른쪽으로 이동. 그래서 (len(name) - t[i+1]) + (len(name) - t[i+1]) + t[i]
    • 이것의 최소값을 구하면 된다

코드

"""Solution code for "Programmers 42860. 조이스틱".

- Problem link: https://programmers.co.kr/learn/courses/30/lessons/42860
- Solution link: http://www.teferi.net/ps/problems/programmers/42860
"""

ORD_A = ord('A')


def solution(name):
    u_d_count = sum(min(ord(c) - ORD_A, ORD_A - ord(c) + 26) for c in name)

토론

댓글을 입력하세요:
B M U H G
 
ps/problems/programmers/42860.txt · 마지막으로 수정됨: 2022/01/17 16:22 저자 teferi