구현 코딩테스트 연습
여러 방법들을 찾아보고 비교/이해하는 것이 중요. 나의 방법으로 다시 정리하기. 반복해서 체화하기
구현 : 주어진 상황을 코드화
정렬 : 알고리즘 -> 어떻게 할 것인가?
탐색 : DFS/BFS + etc 알고리즘 ..
최단거리 : 다익스트라알고, 마샬, ...
01. 구현_지도상 이동
N x N 크기의 정사각형 공간에서 한 칸씩 이동하는 상황. Right/Left/Up/Down
(공간을 벗어나는 움직임은 무시된다)
1. 좌표 도입
* 좌표를 설정할 때 수학적인 좌표평면이 아닌 상황에 맞게 기준을 세워 설정해야함.
2. N 크기의 정사각형
2-1) 지시사항 세팅
n = 5
plans = ["R","R","R","U","D","D"]
2-2) 문제 상황과 초기 값에 대한 세팅
x, y = 1, 1
3. 이동에 대한 세팅
L : (x, y-1)
R : (x, y+1)
U : (x-1, y)
D : (x+1, y)
⬇️ 증감에 대해 갱신의 관점으로 생각한다면
L : (x, y) + (0, -1) = (x+0, y-1)
R : (x, y) + (0, +1) = (x+0, y+1)
U : (x, y) + (-1, 0) = (x-1, y+0)
D : (x, y) + (+1, 0) = (x+1, y+0)
3-1) ⬇️ 이동을 Dict로 구현
move_dict = {
'L':[0,-1],
'R':[0,1]
'U':[-1,0]
'D':[1,0]
}-> x에 대한 R 이동 : x + move_dict["R"][0]
3-2) ⬇️ 이동을 List로 구현
move_types = ['L', 'R', 'U', 'D']
dx = [0, 0, -1, 1]
dy = [-1, 1, 0, 0]-> x에 대한 R 이동 : x + dx[move_types.index('R')]
* list.index()에서 중복되는 값이 있으면 첫번째 값의 index를 출력함.
4. 전체 흐름에 따라 입력으로 주어지는 지시사항을 수행해야 함 (for문)
지시사항대로 움직인다면, in/out 체크 (if문)
지시사항 후 나의 위치 좌표값 갱신
#dict로 구현했을 때
for plan in plans : #지시사항 롤링. 바로 갱신하면 안됨! 이동 가능한 곳인지 체크 필요
next_x = x + move_dict[plan][0]
next_y = y + move_dict[plan][1]
if next_x < 1 or next_x > n or next_y < 1 or nexy_y > n : #아웃바운드
continue
else : #인바운드 #좌표값 갱신
x, y = next_x, next_y
print(x, y)
#list로 구현했을 때
for plan in plans :
for i in range(len(move_types)): #정수인덱스 값을 찾아야 함. range() 또는 move_types.index(plan) 사용
if plan == move_types[i]:
next_x = x + dx[i]
next_y = y + dy[i]
if next_x < 1 or next_x > n or next_y < 1 or nexy_y > n : #동일
continue
else :
x, y = next_x, next_y
print(x, y)먼저 문제 상황을 이해+분석하고,
조건을 어떻게 표현할 지 파이썬의 자료형, 세팅을 선택하고 그에 맞는 표현을 선택한다(규칙에 따라서).
코드의 큰 틀을 생각하면서 하나씩 세팅을 기반으로 풀어나가면 된다!
02. 구현_L자 이동
Q. 8X8 좌표 평면에 특정한 한 칸에 나이트가 서 있다. 나이트는 평면 내부에서 다음과 같은 2가지 경우(L자)로 이동할 수 있다.
1. 수평으로 두 칸 이동한 후 수직으로 한 칸 이동
2. 수직으로 두 칸 이동한 후 수평으로 한 칸 이동
나이트의 위치가 주어졌을 때 나이트가 이동할 수 있는 경우의 수를 출력하는 프로그램을 작성하라. (행 위치는 1부터 8로, 열 위치는 a부터 h로 표현한다.)
A. * 이동 1에서 4가지, 이동 2에서 4가지로 총 8가지 패턴으로 이동할 수 있다.
* positioning x -> counting 해야함
1. 주어진 지도는 8 by 8 평면 (2D) -> 좌표 도입
2. 위치 좌표
(문자,숫자) -> (숫자,숫자)로 좌표 표현 (in/out 부등식으로 표현 가능하도록)
in_txt = "c2"
row = int(in_txt[1])
col = ord(in_txt[0])-ord("a")+1 #기준 숫자를 1로 세팅 3. 이동에 대한 세팅
명확하게 어떤 이동인지 상관 없으니까 list로 표현
l_moves = [[-2,-1],[-2,1],[2,-1],[2,1],[1,-2],[1,2],[-1,-2],[-1,2]]4. 지시사항 수행
l_move (8가지 이동 패턴) 다 돌려보기 (for문)
그 이동이 in/out 체크 (if문, 부등식)
in 조건 만족하면 counting
count = 0
for move in l_moves:
if (row + move[0] > 0) and (row + move[0] > 8) and (col + move[1] > 0) and (col + move[1] > 8) :
count += 1
print(count)03. 구현_카카오키패드
Q. 전화 키패드에서 왼손과 오른손의 엄지손가락만을 이용해서 숫자만을 입력하려고 합니다.
맨 처음 왼손 엄지손가락은 * 키패드에 오른손 엄지손가락은 # 키패드 위치에서 시작하며, 엄지손가락을 사용하는 규칙은 다음과 같습니다.
- 엄지손가락은 상하좌우 4가지 방향으로만 이동할 수 있으며 키패드 이동 한 칸은 거리로 1에 해당합니다.
- 왼쪽 열의 3개의 숫자 1, 4, 7을 입력할 때는 왼손 엄지손가락을 사용합니다.
- 오른쪽 열의 3개의 숫자 3, 6, 9를 입력할 때는 오른손 엄지손가락을 사용합니다.
- 가운데 열의 4개의 숫자 2, 5, 8, 0을 입력할 때는 두 엄지손가락의 현재 키패드의 위치에서 더 가까운 엄지손가락을 사용합니다. 만약 두 엄지손가락의 거리가 같다면, 오른손잡이는 오른손 엄지손가락, 왼손잡이는 왼손 엄지손가락을 사용합니다.
순서대로 누를 번호가 담긴 배열 numbers, 왼손잡이인지 오른손잡이인 지를 나타내는 문자열 hand가 매개변수로 주어질 때, 각 번호를 누른 엄지손가락이 왼손인 지 오른손인 지를 나타내는 연속된 문자열 형태로 return 하도록 solution 함수를 완성해주세요.
[제한사항]
numbers 배열의 크기는 1 이상 1,000 이하입니다.
numbers 배열 원소의 값은 0 이상 9 이하인 정수입니다.
hand는 "left" 또는 "right" 입니다.
"left"는 왼손잡이, "right"는 오른손잡이를 의미합니다.
왼손 엄지손가락을 사용한 경우는 L, 오른손 엄지손가락을 사용한 경우는 R을 순서대로 이어붙여 문자열 형태로 return 해주세요.
case by case (if문)
1) 1,4,7 : Left
2) 3,6,9 : Right
3) 2,5,8,0 : 가장 가까운 거리
* 거리가 같을 때 : 왼손잡이/오른손잡이
입력: numbers - 누를 숫자들 (list) / hand - 무슨 손 잡이 (string)
출력: answer - numbers에 해당하는 누른 손(L/R) 공백없는 문자열로 출력
💡 키패드 평면을 좌표화 하면 좋지 않을까?
문제를 해석해보며 큰 틀 짜기
for num in numbers :
if 1/4/7 :
무조건 왼손
elif 3/6/9 :
무조건 오른손
else : #2,5,8,0
양 손에서의 거리 계산
여러번 반복되기 때문에 함수 사용이 용이
(입력 : 손의 위치, 누를 버튼 -> 출력 : 직선 거리)
D_L, D_R
if 거리가 다를 때:
짧은 거리 손을 선택
else : #거리가 같을 때
hands 입력 변수의 정보 사용하기
나의 썩은 코드,,,,,,
def solutions(numbers, hand):
L = 10
R = 12
answer = ''
for n in list(numbers) :
if n == 0 :
n = 11
if n == 1 or n == 4 or n == 7 :
answer += 'L'
L = n
elif n == 3 or n == 6 or n == 9 :
answer += 'R'
R = n
else :
l1 = (L-1) // 3
l2 = (L-1) % 3
r1 = (R-1) // 3
r2 = (R-1) % 3
n1 = (n-1) // 3
n2 = (n-1) % 3
if (abs((l1 - n1)) + abs((l2 - n2))) < (abs((r1 - n1)) + abs((r2 - n2))) :
answer += 'L'
L = n
elif (abs((l1 - n1)) + abs((l2 - n2))) == (abs((r1 - n1)) + abs((r2 - n2))):
if hand == 'left' :
answer += 'L'
L = n
else :
answer += 'R'
R = n
else :
answer += 'R'
R = n
return answer답안
#키패드 좌표화
#List로
keypad_list = ["1", "2", "3", ...]
pos_x = [0,0,0,1, ...]
pos_y = [0,1,2,0, ...]
or #Dict로
key_pad = {"1":[0,0], "2":[0,1], "3":[0,2], "4":[1,0], ...}
temp_x, temp_y = key_pad["?"]
#2/5/8/0 거리 구하기 #함수 #재사용가능
def get_distance(number, pos): #입력 : 2개 키패드 위치 (누를 키패드 위치, 현재 손 위치)
number = str(number)
pos = str(pos)
x_number, y_number = key_pad[number] #멀티할당 #누를 키패드
x_pos, y_pos = key_pad[pos] #손 위치
abs_distance = abs(x_number - x_pos) + abs(y_number - y_pos) #기능 : 위치 상 직선거리 계산
return abs_distance #출력 : 거리값
def solution(numbers, hand):
answer = ''
left = "*"
right = "#"
if hand == 'right' :
hand = 'R'
elif hand == 'left' :
hand = 'L'
for num in numbers:
if num in [1,4,7] : #in으로 간단히 listup
answer += 'L'
left_pos = num #왼손 위치 갱신
elif num in [3,6,9] :
answer += 'R'
right_pos = num
elif num in [2,5,8,0] :
dis_left = get_distance(num, left_pos) #왼손과의 거리 계산
dis_right = get_distance(num, right_pos) #오른손과의 거리
if dis_left < dis_right : #왼손이 더 가까울 때
answer += 'L'
left_pos = num
elif dis_left > dis_right : #오른손이 더 가까울 때
answer += 'R'
right_pos = num
elif dis_left == dis_right : #거리가 동일할 때
answer += hand
if hand == 'R' :
right_pos = num
elif hand == 'L' :
left_pos = num
return answer
