2024년 5월 14일 알고리즘 문제풀이
문제
난이도
Lv.2
코드
1차
55.6점 / 100점 진짜 어려웠다. A글자를 원하는 글자로 바꾸는 것은 어렵지 않았으나, 어떤 방향으로 커서를 움직이도록 설정할지가 고민됐다. 양 옆의 글자를 보고 바꾸기 위해 조작을 많이해야 하는 쪽으로 움직이도록 설정해주었다. 그래야 혹시 바꿀 필요가 없는 쪽으로 이동하지 않을 거라고 생각했다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
def solution(name):
def cal(x):
max_val = ord("Z")+1
return min(ord(name[x])-ord(tmp[x]),(max_val-ord(name[x])))
n = len(name)
name = list(name)
answer = 0
idx = 0
tmp = list('A'*n)
while True:
if name[idx] != tmp[idx]:
answer += cal(idx)
tmp[idx] = name[idx]
if name == tmp:
break
if cal((idx-1)%n) >= cal((idx+1)%n):
idx = (idx-1)%n
else:
idx = (idx+1)%n
answer += 1
return answer
2차
51.9점 / 100점
이동해야 할 방향을 정할 때 봐야할 글자 수를 늘렸다. 만약 현재 커서 기준으로 1칸 왼쪽, 오른쪽을 확인했을 때 양 쪽이 바꿔야할 글자 수가 동일하다면 더 먼 2칸 옆을 보도록 설정했다. 기존에는 같을때 그냥 오른쪽으로 가도록 했었다. 로직이 더 나아졌다고 생각했는데, 오히려 점수가 낮아졌다. 내가 감을 전혀 못잡고 있나보다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
def solution(name):
def cal(x):
max_val = ord("Z")+1
return min(ord(name[x])-ord(tmp[x]),(max_val-ord(name[x])))
n = len(name)
name = list(name)
answer = 0
idx = 0
tmp = list('A'*n)
while True:
if name[idx] != tmp[idx]:
answer += cal(idx)
tmp[idx] = name[idx]
if name == tmp:
break
answer += 1
for i in range(1,n):
min_idx = idx-i
max_idx = idx+i
if cal(min_idx%n) > cal(max_idx%n):
idx = (min_idx)%n
break
else:
idx = (max_idx)%n
break
return answer
3차
7.4점 / 100점 JY-mary’s blog를 보고 참고했다. 내가 전혀 생각하지도 못한 방식이었다.. 글자를 바꾸는 것은 그리 중요하지 않고, 좌우로 커서를 움직이는게 중요했다. 나는 경우에 따라 왼쪽으로 움직일지 오른쪽으로 움직일지를 결정해주어야 한다고 생각했는데 결국 최대 한번만 꺾으면 됐다. 그 이상 꺾으면 최솟값이 나올리가 없기 떄문이다. 왜냐하면 결국 글자를 바꾸기 위한 조이스틱 조작은 정해져있다. 무슨말이냐면, “CEZ” 라는 글자가 있다면 C는 2번, E는 4번, Z는 1번 움직이면 된다(거꾸로). CEZ, EZC, ZCE 어떤 순서로든 AAA에서 각 글자를 바꾸기 위한 횟수는 동일하다는 의미다. 2+4+1, 4+1+2, 1+2+4 순서의 차이일뿐 글자를 만들기 위해선 7번으로 고정이다. 따라서 전체 조작 횟수를 최소한으로 하는데 중요한 것은 좌우 커서를 움직이는 것이다. 이 값을 작게 만들어야 한다. 2번 꺾으면 결국 방향은 진행방향은 맨 처음 시작할 때와 동일한데 의미없이 중복된 곳을 2번 지난다. 하지만 1번만 꺾을 때는 중복된 글자를 보더라도 최솟값이 나올 수있다. CAEHAAB 라는 글자를 가정해보자. 3글자를 본 이후로 방향을 꺾어 반대로 진행한다고 볼때, 왼쪽으로(거꾸로) 시작하면 C-B-A-B-C-A-E-H-A 순으로 보게되고 오른쪽으로 시작하면 C-A-E-A-C-B-A-A-H 가 된다. 왼쪽으로 시작할 떄의 봐야할 문자열인 CBABCAHEA 는 마지막 A는 바꾸지 않아도 되니 볼 필요가 없다. 즉 CBABCAHEH 라는 문자열의 길이가 9짜리가 되므로 커서를 바꾸기 위해 8번만 누르면된다. 반면 오른쪽으로 시작할 때인 CAEACBAAH 는 끝까지 가서 H도 바꿔줘야한다. 문자열의 길이가 10이고 커서를 이동하기 위한 조작수는 9이다. 위에서 말했듯 둘다 글자를 바꾸기 위한 조작수는 똑같다. 이해가 덜된채로 코드를 짜다보니 마지막 정답을 구하는 과정에서 오류가 발생했다. 제대로된 코드를 위해선 마지막 코드를 보자.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
def solution(name):
n = len(name)
name = list(name)
tmp = list('A'*n)
def cal(x):
max_val = ord("Z")+1
return min(ord(name[x])-ord('A'),(max_val-ord(name[x])))
answer = 0
cnt = 0
for i in range(n):
cnt += cal(i)
for i in range(len(name)//2 + 1):
left = name[-i:] + name[:-i]
right = name[i: :-1] + name[i+1:][::-1]
for n in [left,right]:
for x in range(len(left)-1,-1,-1):
if n[x] != 'A':
break
n = n[:x+1]
answer = min(answer, answer + i)
return answer+ cnt
4차(정답)
100점 / 100점
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
def solution(name):
# 최솟값 구하기 위해 최댓값으로 설정
answer = 10**9
# 특정 글자를 만들기 위해 "A"에서 눌러야 할 조이스틱 조작 횟수를 반환하는 함수
def cal(x):
max_val = ord("Z")+1
return min(ord(x)-ord('A'),(max_val-ord(x)))
# 찍고 방향을 바꿀 지점을 절반까지로 설정. 절반을 넘어간 시점에서 뒤돌아 오는 것은 최솟값일리가 없음.
for i in range(len(name)//2 + 1):
# 시작지점에서 왼쪽으로 간 후 방향을 바꿔 오른쪽으로 계속 갔을 떄의 문자열
left = name[-i:] + name[:-i]
# 시작지점에서 오른쪽으로 간 후 방향을 바꿔 왼쪽으로 계속 갔을 떄의 문자열
right = name[i: :-1] + name[i+1:][::-1]
# 두 경우를 모두 살펴봄
for n in [left,right]:
arr = []
# 문자열을 살펴볼때 남은 것들이 모두 "A"라면 볼 필요가 없음
# 뒤에서부터 어디까지가 "A"로만 이루어졌는지 확인하는 과정
for x in range(len(left)-1,-1,-1):
if n[x] != 'A':
break
n = n[:x+1]
# 각 글자들을 "A"에서 원하는대로 바꾸는데 까지 필요한 조작 수들을 배열에 담음
for x in n:
arr.append(cal(x))
# i : 처음 커서를 움직인 방향으로 조작한 횟수
# len(arr)-1 : 방향을 바꾼 후 커서를 움직이기 위한 조작 횟수
# sum(arr) : 각 글자들을 원하는 글자로 바꾸기 위한 조작 횟수
answer = min(answer, i + sum(arr)+len(arr)-1)
return answer
출처 : JY-mary’s log
