[탐욕법(Greedy)] 조이스틱
Link: https://programmers.co.kr/learn/courses/30/lessons/42860?language=python3
문제 설명
조이스틱으로 알파벳 이름을 완성하세요. 맨 처음엔 A로만 이루어져 있습니다.
ex) 완성해야 하는 이름이 세 글자면 AAA, 네 글자면 AAAA
조이스틱을 각 방향으로 움직이면 아래와 같습니다.
▲ - 다음 알파벳
▼ - 이전 알파벳 (A에서 아래쪽으로 이동하면 Z로)
◀ - 커서를 왼쪽으로 이동 (첫 번째 위치에서 왼쪽으로 이동하면 마지막 문자에 커서)
▶ - 커서를 오른쪽으로 이동 (마지막 위치에서 오른쪽으로 이동하면 첫 번째 문자에 커서)
예를 들어 아래의 방법으로 "JAZ"를 만들 수 있습니다.
- 첫 번째 위치에서 조이스틱을 위로 9번 조작하여 J를 완성합니다.
- 조이스틱을 왼쪽으로 1번 조작하여 커서를 마지막 문자 위치로 이동시킵니다.
- 마지막 위치에서 조이스틱을 아래로 1번 조작하여 Z를 완성합니다.
따라서 11번 이동시켜 "JAZ"를 만들 수 있고, 이때가 최소 이동입니다.
만들고자 하는 이름 name이 매개변수로 주어질 때, 이름에 대해 조이스틱 조작 횟수의 최솟값을 return 하도록 solution 함수를 만드세요.
[제한 사항]
name은 알파벳 대문자로만 이루어져 있습니다.
name의 길이는 1 이상 20 이하입니다.
입출력 예
name return
"JEROEN" 56
"JAN" 23
Code
def check(alpha):
if ord(alpha)-ord('A') <= ord('Z') - ord(alpha) + 1:
return ord(alpha) - ord('A')
else:
return ord('Z') - ord(alpha) + 1
def solution(name):
answer = len(name)-1 #양옆으로 움직일 수 있는 최대치
for x in name:
#각각의 알파벳이 최소한으로 변환될 수 있는 횟수를 반환하여 저장
answer += check(x)
left = 0
right = 0
#좌,우에 'A'알파벳이 연속적으로 존재하는지 확인.
for l in range(1,len(name)):
if name[l] != 'A': break
else: left += 1
for r in range(len(name)-1,0,-1):
if name[r] != 'A': break
else: right += 1
#만약 두번째 알파벳 부터 연속하는 'A'가 오른쪽 끝부터 연속하는 'A'보다 많다면 정답에 이동수 줄이기
if left >= right:
answer -= left
else:
answer -= right
return answer Code 풀이
- 위로올리면 알파벳이 순차적으로 변하고 내리면 A에서 Z순으로 변하기 때문에 비교할 필요가 있다. check() 함수를 통해 적은 횟수를 반환한다.
- 두번째 알파벳부터 'A'가 연속적으로 존재하는지 확인 후 left에 저장 & 가장 마지막 오른쪽 알파벳부터 'A'가 연속적으로 존재하는지 확인 후 right에 저장
- 만약 left가 더 많다면 left만큼 정답에서 차감하고 right가 더 많다면 right 만큼 차감.
Code Output / Screenshot
Code 오류
만약 name이 "ABAAB"라면 오른쪽으로 한번 이동후 고친다음 다시 왼쪽으로 돌아와 마지막 알파벳에 도달하여 'B'로 바꿔야한다. 즉 정답이 6이 아닌 5가 나와야한다.
따라서 좌우 이동의 계산을 다시 해줄 수 있는 코드 필요.
Code 1차 수정
def check(alpha):
if ord(alpha)-ord('A') <= ord('Z') - ord(alpha) + 1:
return ord(alpha) - ord('A')
else:
return ord('Z') - ord(alpha) + 1
def solution(name):
answer = 0 #양옆으로 움직일 수 있는 최대치
for x in name:
#각각의 알파벳이 최소한으로 변환될 수 있는 횟수를 반환하여 저장
answer += check(x)
left = 0
right = 0
middle = 0
middleIndex = 0
middleStart = 0
middleIndexR = 0
middleEnd = 0
#좌,우에 'A'알파벳이 연속적으로 존재하는지 확인.
for l in range(1,len(name)):
if name[l] != 'A':
middleIndex = l
break
else: left += 1
for r in range(len(name)-1,0,-1):
if name[r] != 'A':
middleIndexR = r
break
else: right += 1
boolCheck = False
for m in range(middleIndex+1,middleIndexR-1):
if name[m] == 'A':
middleStart = m
boolCheck = True
while True:
middle += 1
m += 1
if m > middleIndexR -1:
middleEnd = m-1
break
if name[m] != 'A':
middleEnd = m-1
break
break
middleCount = 0
if middleStart - 1 < len(name) -1 - middleEnd:
middleCount = (middleStart-1)*2 + len(name) -1 - middleEnd
else:
middleCount = (middleStart-1) + (len(name) -1 - middleEnd)*2
leftCount = len(name)-1 -left
rightCount = len(name)-1 -right
if boolCheck:
answer += min(leftCount,rightCount,middleCount)
else:
answer += min(leftCount,rightCount)
return answer "ABAAB"의 문제는 해결했지만 여전히 오류가 존재한다.
Code 최종 수정
# 1. 오른쪽으로만 가면서 체크해보기
def right(check):
d = 0
for i in range(len(check)):
if check[i] == False:
d = i
return d
# 2. 왼쪽으로만 가면서 체크해보기
def left(check):
d = 0
for i in range(len(check)-1,0,-1):
if check[i] == False:
d = len(check)-i
return d
# 3. 오른쪽으로 절반 갔다가 왼쪽으로 가서 체크해보기
def rightLeft(check):
d,temp = 0,0
for i in range(0,len(check)//2):
if check[i] == False:
d = i*2
for i in range(len(check)-1,(len(check)//2)-1,-1):
if check[i] == False:
temp = len(check)-i
return d + temp
# 4. 왼쪽으로 절반 갔다가 오른쪽으로 가서 체크해보기
def leftRight(check):
d,temp = 0,0
for i in range(len(check)-1,(len(check)//2),-1):
if check[i] == False:
d = (len(check)-i) * 2
for i in range(0,(len(check)//2)+1):
if check[i] == False:
temp = i
return d + temp
def solution(name):
answer = 0
check = [False for _ in range(len(name))]
# Bool 체크리스트 만들기 | 만약 "A"면 True
for i in range(0,len(check)):
if i == 0: check[i] = True
if name[i] == 'A':
check[i] = True
#최소 좌우이동 갯수 계산 4가지 방법
r = right(check)
l = left(check)
rl = rightLeft(check)
lr = leftRight(check)
answer = min(r, l, rl, lr)
#알파벳 상하로 움직이기 계산
for x in name:
up = ord(x)-ord('A')
down = 1 + ord('Z')-ord(x)
answer += min(up,down)
return answer코드 접근 및 풀이
[접근]
정답은 두가지 계산을 구한 후 더해줍니다.
1. 각 알파벳 별 최소 상하 움직임들을 합한 수
2. 필요한 알파벳('A'가 아닌 알파벳들)을 최소 한번씩은 확인 할 경우의 좌우 이동간의 최소 경로
[설명]
1. A부터 Z까지 거리와 Z부터 A까지의 거리를 비교하여 작은 수를 선택하고, name에 있는 모든 값들의 최소 움직임을 더해준다.
2. 총4가지 방법으로 확인 후 최소값을 선택한다.
-
오른쪽으로 끝까지 확인
-
왼쪽으로(역방향) 끝까지 확인
-
오른쪽으로 절반만 갔다가 다시 돌아오면서 역방향의 절반까지 확인(오른쪽으로 간만큼 돌아와야하기 때문에 돌아온 거리x2 필요)
-
왼쪽(역방향)으로 절반만 갔다가 다시 돌아온 후 오른쪽(정방향)의 절반까지 확인(왼쪽으로 간만큼 돌아와야하기 때문에 돌아온 거리x2 필요)
name리스트에 A가 있다면 들릴 필요가 없으니 True, A가 아니면 False로 정의 한 bool 리스트를 하나 만들어 준 후.
True/False를 이용하여 거리를 계산한다.
