★ [카카오기출][Python] 키패드 누르기

 

 

목차

 

 

🫡 Overview

체감 난이도: ★☆☆☆☆

소요시간: 30분

문제 레벨: Lv1. / 문제 유형: 단순 구현 
풀이 상태:  스스로 해결
추후: 간단복습

 

---

문제 링크 

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

요구사항 분석

<문제 이해>
왼쪽과 같이 3*4 번호판이 주어진다. 

 

문제: 누를 숫자 배열이 주어질 때 
어떤 손가락이 눌렀는지 배열을 리턴(오른손 R, 왼손 L)

손가락 누르는 방법
- 시작점: 왼손(*), 오른손(#)
- 왼손(1,4,7), 오른손(3,6,9)
- 가운데 2,5,8,0은 거리가 가까운 손가락이 누른다. 
   - 만약 거리가 같을 경우, 왼손잡이/오른손잡이에 따라서 달라짐 

예시를 보면, 이때 거리는 맨해튼 거리이다!

 

 

 

 

 

시간 복잡도 분석 

입력 numbers 1<=len(numbers)<=1000

최악의 경우 매번 2,5,8,0을 눌러야해서 매번 눌러야하는 번호의 위치와 왼손/오른손의 거리를 구해야 한다. 

-> 거리 구하기 O(2)*1000번 이므로 시간 내에 연산할 수 있을 것 같았다. 

 

 

 

나의 코드

• 자료형: dict
  • key: 번호판 내 숫자, value는 위치로 설정하여, 번호판 숫자를 넣으면 좌표 위치가 나오도록 함. 
• 그리고 무지성 단순 구현을 했다. 

# key: 번호판 내 숫자, value는 위치 
coordinate = {'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],
                 } 

def distance(current_str, num): # current: str, num : int 
    cx, cy = coordinate[current_str]
    nx, ny = coordinate[str(num)]
    
    return abs(cx-nx) + abs(cy-ny)
    

def solution(numbers, hand):
    ans = ''
    
    left, right = '*', "#"
    for num in numbers:
        if num in (1,4,7): # left 
            left = str(num)
            ans += 'L'
        
        elif num in (3,6,9): # right
            right = str(num)
            ans += 'R'
        else: # 2,5,8,0 일 때 
            l_dist = distance(left, num)
            r_dist = distance(right, num)
            if l_dist < r_dist: 
                left = str(num)
                ans += 'L'
            elif l_dist > r_dist: 
                right = str(num)
                ans += 'R'
            else: # 둘이 똑같을 때 
                if hand == 'left': 
                    left = str(num)
                    ans += 'L'
                else:
                    right = str(num)
                    ans += 'R' 
    return ans

 

 

참고 코드

- 각 숫자 좌표 구할 때 dict을 쓰지 않고 구현하자 

 

3x4의 행렬이고, 행렬은 다음과 같이 생겼다. 

<행>

1,2,3 => 0행

4,5,6 => 1행 

7,8,9 => 2행 

10,11,12 => 3행 

=> 행 인덱스: (N-1)//3

 

<열>

1,4,7,10 => 0열 

2,5,8,11 => 1열 

3,6,9,12 => 2열 

=> 열 인덱스 (N-1)%3

def distance(current, num):  # current: str, num : int
    cx, cy = (current - 1) // 3, (current - 1) % 3
    nx, ny = (num - 1) // 3, (num - 1) % 3

    return abs(cx - nx) + abs(cy - ny)


def solution(numbers, hand):
    ans = ''
    left, right = 10, 12
    for num in numbers:
        if num in (1, 4, 7):  # left
            left = num
            ans += 'L'

        elif num in (3, 6, 9):  # right
            right = num
            ans += 'R'
        else:  # 2,5,8,0 일 때
            if num == 0:
                num = 11
            l_dist = distance(left, num)
            r_dist = distance(right, num)
            if l_dist < r_dist:
                left = num
                ans += 'L'
            elif l_dist > r_dist:
                right = num
                ans += 'R'
            else:  # 둘이 똑같을 때
                if hand == 'left':
                    left = num
                    ans += 'L'
                else:
                    right = num
                    ans += 'R'
    return ans

 

 

 

 

 

 

 

---

배운 점/느낀 점

기초 구현력을 탄탄히 하는 게 중요하다!!!

 

 

---