탐욕법(Greedy) > 조이스틱
(개인적으로 어려웠음)
코딩테스트 연습 - 조이스틱
조이스틱으로 알파벳 이름을 완성하세요. 맨 처음엔 A로만 이루어져 있습니다. ex) 완성해야 하는 이름이 세 글자면 AAA, 네 글자면 AAAA 조이스틱을 각 방향으로 움직이면 아래와 같습니다. ▲ - 다
programmers.co.kr
만들고자 하는 이름 name이 매개변수로 주어질 때,
이름에 대해 조이스틱 조작 횟수의 최솟값을 return 하도록 solution 함수 만들기
실패한 코드
아래의 코드는 테스트케이스 11번이 틀림
--> "ABAAAAAAAAABB" 일 때 7이 출력되야 하는데 15가 출력됨
한 방향으로 가는 것만이 아니라 2번째 B까지 갔다가 다시 돌아가는 것이 빠르기 때문에 출력값이 다름
def solution(name):
make_A = list(map(lambda x: ord(name[x]) - ord('A'), range(len(name))))
make_Z = list(map(lambda x: ord('Z') - ord(name[x]) + 1, range(len(name))))
make_name = list(map(lambda x: make_A[x] if make_A[x] < make_Z[x] else make_Z[x], range(len(name))))
count_f = 0
count_l = 0
while len(make_name) > 1 and make_name[1] == 0:
count_f+=1
make_name.pop(1)
while len(make_name) > 2 and make_name[-2] == 0:
count_l+=1
make_name.pop(-2)
max_count = count_f if count_f > count_l else count_l
return sum(make_name)+len(name)-1-max_count
다시 수정한 코드
def solution(name):
make_name = list(map(lambda x: ord(name[x]) - ord('A')
if ord(name[x]) - ord('A') < ord('Z') - ord(name[x]) + 1
else ord('Z') - ord(name[x]) + 1, range(len(name))))
A_str = []
A_list = []
for i in range(len(name)):
if name[i] == 'A':
A_str.append('A')
if i == len(name) - 1:
A_list.append(len(A_str))
else:
if A_str:
A_list.append(len(A_str))
A_list.append(0)
A_str = []
l_c = A_list.index(max(A_list))-1 if A_list.index(max(A_list)) != 0 else 0
r_c = len(name) - (A_list.index(max(A_list))+max(A_list))
min_count = min([len(name)-1, l_c*2+r_c, r_c*2+l_c])
return sum(make_name)+min_count
- make_name list : 각 알파벳을 가장 작게 움직이면서 만들 수 있는 수
make_name = list(map(lambda x: ord(name[x]) - ord('A')
if ord(name[x]) - ord('A') < ord('Z') - ord(name[x]) + 1
else ord('Z') - ord(name[x]) + 1, range(len(name))))
- A를 기준으로 리스트 분할할 때 A가 연속되는 문자열의 크기로 A_list 리스트를 만들어 준다.
예시 - "ABAAAAAAAAABB" --> "A(1)B(0)AAAAAAAAA(9)B(0)B(0)" --> [1, 0, 9, 0, 0]
A_str = []
A_list = []
for i in range(len(name)):
if name[i] == 'A':
A_str.append('A')
if i == len(name) - 1:
A_list.append(len(A_str))
else:
if A_str:
A_list.append(len(A_str))
A_list.append(0)
A_str = []
- A_list 에서 가장 길게 연속 된 A의 개수를 구한다.
- 그 수를 기준으로 왼쪽으로 움직여야 하는 개수 / 오른쪽으로 움직여야 하는 개수를 구해준다.
(아래의 경우의 수 같은 것을 위해 코드를 이렇게 작성)
예시 - "ABAAAAAAAAABB" --> "AB(*)AAAAAAAAAB(*)B" --> l_c = 1, r_c = 2
- 움직일 수 있는 경우의 수 중 가장 작은 값을 구한다.
l_c = A_list.index(max(A_list))-1 if A_list.index(max(A_list)) != 0 else 0
r_c = len(name) - (A_list.index(max(A_list))+max(A_list))
min_count = min([len(name)-1, l_c*2+r_c, r_c*2+l_c])
코드가 지저분하게 짜진 것 같아서 아쉽긴 하지만 직접 풀었다는 것에 만족😫
'study > 알고리즘' 카테고리의 다른 글
[알고리즘] 다이나믹 프로그래밍(동적 계획법) - 2 (0) | 2021.12.07 |
---|---|
[알고리즘] 다이나믹 프로그래밍(동적 계획법) - 1 (0) | 2021.12.03 |
[알고리즘/프로그래머스] 2019 KAKAO BLIND RECRUITMENT - 실패율 (0) | 2021.11.26 |
[알고리즘 / 자료구조] 트리(Tree) (0) | 2021.11.26 |
[알고리즘 / Oracle] 프로그래머스 - 보호소에서 중성화한 동물, 우유와 요거트가 담긴 장바구니 (0) | 2021.11.25 |