개발의변화
조이스틱- 그리디 낚시 본문
반응형
https://school.programmers.co.kr/learn/courses/30/lessons/42860
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
처음에 탐욕법이라고 적혀있어서 A가 아닌 글자 중에 왼쪽으로 혹은 오른쪽으로 갈 때 최단 거리를 선택해서 하면 되는 줄 알았다. 하지만 2시간 동안 머리를 쥐어싸봐도 테스트 코드 5개를 해결하지 못하고 완전탐색으로 바꿔 풀었다. 진짜 쉽지않았다...
처음 그리디로 생각한 방식
def solution(name):
alphabet = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
obj = {}
for i in range(len(alphabet)):
obj[alphabet[i]] = i
k = 'A'
arr = []
for i in range(len(name)):
if name[i] != 'A':
arr.append(i)
count = 0
now = 0
def plusCount(x):
nonlocal count # count 변수를 외부 변수로 선언
nonlocal now # now 변수를 외부 변수로 선언
count += findDistance(x)
count += min(obj[name[x]] - 0, 25 - obj[name[x]] + 1)
now = x
def findDistance(a):
innerDistance = abs(now - a)
outerDistance = len(name) - innerDistance
return min(innerDistance, outerDistance)
while len(arr) > 0:
if len(arr) == 1:
x = arr.pop()
plusCount(x)
else:
first = findDistance(arr[0])
last = findDistance(arr[-1])
if first <= last:
x = arr.pop(0)
plusCount(x)
else:
x = arr.pop()
plusCount(x)
return count
완전탐색으로 푼 문제
def solution(name):
alphabet = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
obj = {}
for i in range(len(alphabet)):
obj[alphabet[i]] = i
k = 'A'
arr = []
for i in range(len(name)):
if name[i] != 'A':
arr.append(i)
count = 9999999999
def plusCount(x):
return min(obj[name[x]] - 0, 25 - obj[name[x]] + 1)
def findDistance(now,a):
innerDistance = abs(now - a)
outerDistance = len(name) - innerDistance
return min(innerDistance, outerDistance) + plusCount(a)
def findAll(arr,c,now):
if len(arr) == 0:
nonlocal count
count = min(count,c)
return
if len(arr) == 1:
first = findDistance(now,arr[0])
return findAll([],c+first,now)
first = findDistance(now,arr[0])
last = findDistance(now,arr[-1])
findAll(arr[1:],c+first,arr[0])
findAll(arr[:-1],c+last,arr[-1])
findAll(arr,0,0)
return count
그리고 개인적으로 레벨2보다는 높은 느낌이다.
반응형