사용자 도구

사이트 도구


ps:problems:programmers:42860

조이스틱

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

애드혹

시간복잡도O(n)
인풋사이즈n<=20
사용한 언어Python
해결날짜2020/12/14
  • 사이트에서는 문제 분류가 그리디로 되어있는데, 그리디로 접근하는 방법은 찾지 못했다;

풀이

  • 알파벳을 설정하는 조작 (조이스틱의 위, 아래 방향)과 커서를 이동시키는 조작 (조이스틱의 왼쪽, 오른쪽 방향)을 나눠서 생각하자. 따로 구한다음에 마지막에 더해서 리턴하면 된다,
  • 알파벳을 설정하는 조작은 단순하다. 어떤 알파벳 x를 만들려면, 위로 올려서 만드는 방법과 아래로 내려서 만드는 방법, 두가지 중에서 짧은 것을 선택하면 된다.
  • 커서를 이동시키는 조작은 좀 복잡하다. 거기에 문제 자체도 헷갈리기 쉽게 되어있다.
    • 문제에서 헷갈리기 쉬운 부분은
      • 첫 번째 위치에서 왼쪽으로 이동하면 마지막 문자로 커서가 이동한다
      • 그러나, 마지막 위치에서 오른쪽으로 이동하면 첫 문자로 커서가 이동하지는 않는다
    • 그러면 이동 방식은 다음 세가지중 최소값이 된다
      • 1. 시작 위치에서 커서를 계속 오른쪽으로 이동한다
      • 2. 시작 위치에서 커서를 계속 왼쪽으로 이동한다
      • 3. 시작 위치에서 얼마만큼 커서를 오른쪽으로 이동했다가, 다시 왼쪽으로 계속 이동한다.
        • BBBAAAAAAAAAABBB 같은 경우이다,
    • 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])
    • 이것의 최소값을 구하면 된다

코드

"""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
"""


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

    t = [i for i, c in enumerate(name) if c != 'A']
    l_r_count = len(name) - t[0]
    for i in range(len(t) - 1):
        l_r_count = min(l_r_count, t[i] * 2 + len(name) - t[i + 1])
    l_r_count = min(l_r_count, t[-1])

    return u_d_count + l_r_count

토론

댓글을 입력하세요:
W E O U P
 
ps/problems/programmers/42860.txt · 마지막으로 수정됨: 2021/01/21 16:29 저자 teferi