문제
https://school.programmers.co.kr/learn/courses/30/lessons/42860#
이게 왜 Level 2이지? 알 수가 없다
주요 아이디어
- Greedy 문제 유형에 나와있어서, 한 글자마다 최적의 선택을 하면 solution을 보장하는 문제라고 생각했다
- 상하 이동은 그냥 target이 A에 가까운지 Z에 가까운지에 따라 결정
- 좌우 이동이 중요하다
- 예시
AAAAN
바꿔야 될 position 선택
->: 4
<-: 1
즉 타깃이 되지 못한 알파벳이 좌우로 몇 개 남았는지에 따라서 좌우 결정
- 예시
- 현재 문자열을 앞에 덧붙여서 만든다
- ex. JEREON -> EROENJEREON
- 처음은 중간 위치 (len(str) // 2) 에서 시작
- 매 위치마다 현재 위치에서 변경해야 하는 알파벳까지 가야 하는 거리를 체크한 이후, 알파벳을 변경하고 이동을 진행한다
코드 구현 (Python 3)
더보기
def up_down(alpha):
return min(abs(ord('Z') - ord(alpha) + 1), abs(ord(alpha) - ord('A')))
# 현재 위치에서 변경해야 하는 알파벳까지 가야 하는 거리
def go_left(name, target, idx):
# left
left_cnt = 0
for i in range(idx, 0, -1):
if name[i] == target[i]:
left_cnt += 1
else:
break
# right
right_cnt = 0
for i in range(idx, len(target)):
if name[i] == target[i]:
right_cnt += 1
else:
break
if left_cnt < right_cnt:
return True
else:
return False
def solution(target):
target = target[1:] + target
print(target)
answer = 0
target = [x for x in target]
name = ["A" for _ in range(len(target))]
p = len(target) // 2 # 처음 시작 인덱스 (중간)
while name != target:
if name[p] != target[p]:
# 해당 자리에서 변경
answer += up_down(target[p])
# 현재 인덱스 + len(str) // 2 + 1
# 현재 인덱스가 가운데 기준 왼쪽일 경우
if p < len(target) // 2:
name[p] = target[p]
name[p + len(target)//2 + 1] = target[p]
# 현재 인덱스가 가운데 기준 오른쪽일 경우
# 현재 인덱스 - len(str) //2 -1
elif p > len(target) // 2:
name[p] = target[p]
name[p - len(target)//2 - 1] = target[p]
# 현재 인덱스가 가운데
else:
name[p] = target[p]
# 변경 후
if name == target:
break
# 왼쪽 이동
if go_left(name, target, p):
p -= 1
answer += 1
else:
p += 1
answer += 1
return answer
처음엔 깔끔히 통과한 줄 알았으나..
일부 테스트 케이스에서 실패가 떴다.
코드 재구현 (Python 3)
이동 개수가 같을 때 방향에 따라서도 값이 달라지나 싶어서 다시 코드를 수정해봤다.
def up_down(alpha):
return min(abs(ord('Z') - ord(alpha) + 1), abs(ord(alpha) - ord('A')))
# 현재 위치에서 변경해야 하는 알파벳까지 가야 하는 거리
def go_left(name, target, idx, direction):
# left
left_cnt = 0
for i in range(idx, 0, -1):
if name[i] == target[i]:
left_cnt += 1
else:
break
# right
right_cnt = 0
for i in range(idx, len(target)):
if name[i] == target[i]:
right_cnt += 1
else:
break
print(f"## left cnt : {left_cnt} right cnt : {right_cnt}")
if left_cnt < right_cnt:
return True
elif left_cnt > right_cnt:
return False
else:
if direction == "left":
return True
else:
return False
def solution(target):
target = target[1:] + target
target = [x for x in target]
p = len(target) // 2 # 처음 시작 인덱스 (중간)
left_first = 0; right_first = 0
left_name = ["A" for _ in range(len(target))]
right_name = ["A" for _ in range(len(target))]
while left_name != target:
print(target[p], left_name[p])
print(up_down(target[p]))
if left_name[p] != target[p]:
# 해당 자리에서 변경
left_first += up_down(target[p])
# 현재 인덱스 + len(str) // 2 + 1
# 현재 인덱스가 가운데 기준 왼쪽일 경우
if p < len(target) // 2:
left_name[p] = target[p]
left_name[p + len(target)//2 + 1] = target[p]
# 현재 인덱스가 가운데 기준 오른쪽일 경우
# 현재 인덱스 - len(str) //2 -1
elif p > len(target) // 2:
left_name[p] = target[p]
left_name[p - len(target)//2 - 1] = target[p]
# 현재 인덱스가 가운데
else:
left_name[p] = target[p]
print("변경된 문자열 : ", left_name)
if left_name == target:
break
if go_left(left_name, target, p, "left"):
p -= 1
left_first += 1
print("move left")
else:
p += 1
left_first += 1
print("move right")
print('#' * 10)
p = len(target) // 2 # 처음 시작 인덱스 (중간)
while right_name != target:
print(target[p], right_name[p])
print(up_down(target[p]))
if right_name[p] != target[p]:
# 해당 자리에서 변경
right_first += up_down(target[p])
# 현재 인덱스 + len(str) // 2 + 1
# 현재 인덱스가 가운데 기준 왼쪽일 경우
if p < len(target) // 2:
right_name[p] = target[p]
right_name[p + len(target)//2 + 1] = target[p]
# 현재 인덱스가 가운데 기준 오른쪽일 경우
# 현재 인덱스 - len(str) //2 -1
elif p > len(target) // 2:
right_name[p] = target[p]
right_name[p - len(target)//2 - 1] = target[p]
# 현재 인덱스가 가운데
else:
right_name[p] = target[p]
print("변경된 문자열 : ", right_name)
if right_name == target:
break
if go_left(right_name, target, p, "right"):
p -= 1
right_first += 1
print("move left")
else:
p += 1
right_first += 1
print("move right")
# print(left_first, right_first)
return min(left_first, right_first)
스파게티 코드
다 맞은 줄.. 알았는데..??
결과는 실패..
실패 원인
이번에도 책을 참고해서 원인을 살펴보았다.
반례
"BBABAAAB"
그런데.. 이것보다 더 적은 횟수로 변경할 수 있는 방법이 있다!
바로 왔던 길을 "되돌아가는" 경우다.
일반적인 경우라면 놓치기 쉽지만, 이렇게 A가 연달아 길게 있는 경우, 그대로 이동하는 것보다 되돌아가는 것이 더 횟수를 줄일 수 있다.
반례 찾기 참 힘들다
따라서 커서는 "연속된 A 문자열을 최대한 피해서" 이동해야 한다.
코드 재구현 (Python 3)
def up_down(target):
return min(abs(ord(target) - ord('A')), abs(ord('Z') - ord(target) + 1))
def solution(name):
# 알파벳 변경 횟수, 커서 변경 횟수
spell_move = 0; cursor_move = len(name) - 1 # 최대 이동 거리
for idx, ch in enumerate(name):
# 상하이동부터
spell_move += up_down(ch)
# 해당 인덱스 다음부터 연속된 A 문자열 찾기
next_idx = idx + 1
while next_idx < len(name) and name[next_idx] == 'A':
next_idx += 1
# next_idx : 연속된 A 문자열의 오른쪽 끝 인덱스
# 왼쪽 순회 거리, 오른쪽 순회 거리 중 최소값 비교
distance = min(idx, len(name) - next_idx)
# 실제 이동 거리 계산 (순방향 VS 역방향 거리 계산)
cursor_move = min(cursor_move, idx + len(name) - next_idx + distance)
answer = spell_move + cursor_move
return answer
제출 결과
'알고리즘 > 프로그래머스' 카테고리의 다른 글
[프로그래머스] 행렬 테두리 회전하기 (0) | 2024.04.11 |
---|---|
[프로그래머스] 등굣길 (0) | 2024.04.08 |
[프로그래머스] 튜플 (0) | 2024.04.07 |
[프로그래머스] 두 개 뽑아서 더하기 (0) | 2024.04.07 |
[프로그래머스] 소수 찾기 (0) | 2024.04.07 |