프로그래머스 | Python | 그리디, 단순구현 | 키패드 누르기 (Lv.1)

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

프로그래머스

 

문제 개요

스마트폰의 숫자 키패드를 사용할 때 왼손과 오른손을 이용해서 숫자를 입력하는 방식을 구현하는 문제입니다. 각 손의 초기 위치는 다음과 같습니다:

• 왼손: *에서 시작
• 오른손: #에서 시작

각 손이 이동하는 방식은 아래와 같습니다:

1. 왼쪽 열 (1, 4, 7) → 왼손 사용
2. 오른쪽 열 (3, 6, 9) → 오른손 사용
3. 가운데 열 (2, 5, 8, 0) → 더 가까운 손이 사용
   • 거리가 같다면 주 사용 손(왼손잡이/오른손잡이)에 따라 결정

우리는 주어진 numbers 리스트를 순서대로 입력할 때, 어떤 손을 사용했는지를 연속된 문자열 형태로 반환해야 합니다.

---

📌 문제 접근 방식

1️⃣ 키패드 좌표를 딕셔너리로 저장

키패드를 2차원 배열 형태의 좌표로 변환하여 관리합니다.

1  2  3
4  5  6
7  8  9
*  0  #

각 숫자의 위치를 (행, 열) 좌표로 매핑하면 다음과 같습니다:

keypad = {
    1: (0, 0), 2: (0, 1), 3: (0, 2),
    4: (1, 0), 5: (1, 1), 6: (1, 2),
    7: (2, 0), 8: (2, 1), 9: (2, 2),
    '*': (3, 0), 0: (3, 1), '#': (3, 2)
}

---

2️⃣ 초기 손 위치 설정

• left_pos = keypad['*'] → 왼손 초기 위치는 *
• right_pos = keypad['#'] → 오른손 초기 위치는 #

---

3️⃣ 숫자를 순서대로 입력하면서 손 이동 결정

• 1, 4, 7 → 왼손 사용 (left_pos 업데이트)
• 3, 6, 9 → 오른손 사용 (right_pos 업데이트)
• 2, 5, 8, 0 → 거리를 비교하여 결정
  • 맨해튼 거리(|x1 - x2| + |y1 - y2|)를 계산하여 가까운 손 사용
  • 거리가 같다면 hand 값("left" 또는 "right")에 따라 결정

---

코드 구현 (Python)

def solution(numbers, hand):
    # 키패드 위치 딕셔너리
    keypad = {
        1: (0, 0), 2: (0, 1), 3: (0, 2),
        4: (1, 0), 5: (1, 1), 6: (1, 2),
        7: (2, 0), 8: (2, 1), 9: (2, 2),
        '*': (3, 0), 0: (3, 1), '#': (3, 2)
    }

    # 초기 손가락 위치 설정
    left_pos = keypad['*']
    right_pos = keypad['#']
    result = ""

    for num in numbers:
        if num in [1, 4, 7]:  # 왼손 사용
            result += "L"
            left_pos = keypad[num]
        elif num in [3, 6, 9]:  # 오른손 사용
            result += "R"
            right_pos = keypad[num]
        else:  # 가운데 숫자 (2, 5, 8, 0) → 거리 비교
            num_pos = keypad[num]

            # 맨해튼 거리 계산
            left_dist = abs(left_pos[0] - num_pos[0]) + abs(left_pos[1] - num_pos[1])
            right_dist = abs(right_pos[0] - num_pos[0]) + abs(right_pos[1] - num_pos[1])

            if left_dist < right_dist:  # 왼손이 더 가까우면
                result += "L"
                left_pos = num_pos
            elif left_dist > right_dist:  # 오른손이 더 가까우면
                result += "R"
                right_pos = num_pos
            else:  # 거리가 같다면 주 사용 손으로 결정
                if hand == "right":
                    result += "R"
                    right_pos = num_pos
                else:
                    result += "L"
                    left_pos = num_pos

    return result

---

코드 설명

1️⃣ 키패드 위치를 딕셔너리로 저장하여 좌표 값으로 변환

2️⃣ 손의 초기 위치를 *, #로 설정

3️⃣ 입력된 숫자를 순회하며 손 이동 결정

• 왼손, 오른손 고정 숫자는 즉시 업데이트
• 2, 5, 8, 0은 맨해튼 거리를 비교하여 결정
• 거리가 같으면 주 사용 손(hand)을 사용

---

시간 복잡도 분석

• numbers 리스트 길이 최대 1,000
• 각 숫자에 대해 맨해튼 거리 계산 (O(1)) + 조건문 처리 (O(1))
• 총 시간 복잡도: O(N) (최대 1,000번 연산이므로 충분히 빠름)

---

핵심 정리

✔ 키패드를 (행, 열) 좌표로 변환하여 위치 기반 이동 구현

✔ 맨해튼 거리 공식을 사용해 가까운 손을 결정

✔ 거리 같을 때 hand 값으로 주 사용 손 결정