문제 간단 해석
기존 문자열에서 원하는 문자열을 만들되, 최소로 움직여야 하는 문제. 효율을 생각하고 코드를 구성했으나, 많이 미흡했다. 따라서 다른 분이 푸신 Java 최대 효율 코드의 해석도 첨부.
Java
첫 풀이, 효율을 살린 풀이, 다른 분의 풀이를 모두 해석하겠다.
첫 풀이
풀이 코드
import java.util.List;
import java.util.ArrayList;
class Solution {
private List<Integer> list = new ArrayList<>();
private int head;
private int tail;
private int length;
public int cal(int now, int to, int dir) {
return Math.min(
Math.abs(now - to),
length + (to - now) * dir
);
}
public int move(int now, int cost) {
if (head > tail)
return cost;
int next, left, right;
next = list.get(head++);
left = move(next, cost + cal(now, next, 1));
head--;
next = list.get(tail--);
right = move(next, cost + cal(now, next, -1));
tail++;
return Math.min(left, right);
}
public int solution(String name) {
int total = 0;
char c;
length = name.length();
for (int i = 0; i < length; i++) {
c = name.charAt(i);
if (c == 'A')
continue;
total += Math.min(c - 'A', 'Z' + 1 - c);
list.add(i);
}
if (list.isEmpty())
return total;
head = list.get(0) == 0 ? 1 : 0;
tail = list.size() - 1;
return total + move(0, 0);
}
}해석
length = name.length();
for (int i = 0; i < length; i++) {
c = name.charAt(i);
if (c == 'A')
continue;
total += Math.min(c - 'A', 'Z' + 1 - c);
list.add(i);
}
if (list.isEmpty())
return total;
head = list.get(0) == 0 ? 1 : 0;
tail = list.size() - 1;
return total + move(0, 0);'A'인 경우는 건드리지 않아도 되니, 'A'가 아닌 글자를 찾고 위 방향 혹은 아래 방향 중 어떤 쪽이 더 빠를지 계산한다. 'A'부터 시작하는 경우인 c - 'A'와, 'Z'로 만든 후 계산하는 'Z' + 1 - c 중 적은 횟수를 구해 더한다.
그 후 'A'가 아니었던 글자의 index를 list에 추가시킨다.
만약 list가 비었다면 (모든 글자가 'A'라면) total을 반환한다. 어차피 total은 0일 테니 0을 반환해도 상관없다.
head와 tail을 선언. 몇 번째 글자를 목표로 잡고 전진 혹은 후진할지를 고를 것이다. 단, 시작은 0이므로 만약 list의 시작이 0이었다면 head를 1로 잡는다.
그 다음 레버를 조작하여 좌우로 이동한다.
public int move(int now, int cost) {
if (head > tail)
return cost;
int next, left, right;
next = list.get(head++);
left = move(next, cost + cal(now, next, 1));
head--;
next = list.get(tail--);
right = move(next, cost + cal(now, next, -1));
tail++;
return Math.min(left, right);
}move 함수는 head나 tail을 목표로 현재의 커서를 좌, 우로 이동시키는 역할이다.
현재 위치에서 어디로 갈 지를 정한다. 처음에는 head를 목표로 이동한다. (head가 상대적으로 좌측에 있기에 left라고 표현했을 뿐, 무조건 왼쪽으로 가는 건 아니다.)
head가 지정하는 index값을 구해 next에 대입한 후 head를 1 증가시킨다. 다음 재귀를 위함이다.
next로 이동하며, 이동거리에 따른 cost를 계산한다.
재귀가 끝났다면 head를 원상복귀 시킨다.
tail을 목표로도 마찬가지.
그 후 양 쪽의 이동거리 중 가장 짧은 것을 반환한다.
head, tail을 목표로 잡으며 이동하는데, 그 둘이 만나게 되면 더 이상 남은 글자가 없다는 뜻이니 지금까지 계산한 이동횟수인 cost를 반환하게끔 했다.
public int cal(int now, int to, int dir) {
return Math.min(
Math.abs(now - to),
length + (to - now) * dir
);
}정방향, 역방향으로 이동할 때의 최솟값을 구한다.
전체 길이 20, 현재 위치 2, 가야할 위치 18, dir은 -1이라고 가정하겠다.
현재 위치에서 목표하는 위치로 그냥 이동했을 때는 두 값의 차를 절댓값으로 반환하면 된다.
따라서 |2 - 18| = 16이 나온다.
만약 끝에서 끝으로 이동하는 경우에는 전체 길이에서 해당 방향성에 따른 값을 구해주면 된다.
length - to + now = 20 - 18 + 2 = 4이다.
내 현재 위치만큼 좌측으로 이동해야하니 + now를, 전체 길이에서 목표 위치만큼을 빼야 하니 length - to가 된다.
단, 이는 head와 tail을 통해 양쪽 방향을 모두 체크하므로 성립하는 좋지 않은 코드이다. 비효율적인 코드가 많이 생산될 수 밖에 없는 구조이다. 맨 밑의 최대 효율 코드 해석을 보고 다시 이해해보도록 하자. 우선은 해당 코드의 효율을 살짝 살려보도록 하겠다.
효율을 살린 풀이
풀이 코드
import java.util.List;
import java.util.ArrayList;
class Solution {
private List<Integer> list = new ArrayList<>();
private int head;
private int tail;
private int length;
public int cal(int now, int to, int dir) {
return Math.min(
Math.abs(now - to),
length + (to - now) * dir
);
}
public int move(int now, int cost, int dir, boolean flag) {
if (head > tail)
return cost;
int[] val = new int[] {-1, -1};
int next;
for(int i = 0; i < 2; i++) {
next = list.get(dir == 1 ? head++ : tail--);
val[i] = move(next, cost + cal(now, next, dir), dir, flag);
if (dir == 1)
head--;
else
tail++;
if (flag) {
dir *= -1;
flag = false;
} else
break;
}
return val[1] == -1 ? val[0] : Math.min(val[0], val[1]);
}
public int solution(String name) {
int total = 0;
char c;
length = name.length();
for (int i = 0; i < length; i++) {
c = name.charAt(i);
if (c == 'A')
continue;
total += Math.min(c - 'A', 'Z' + 1 - c);
list.add(i);
}
if (list.isEmpty())
return total;
head = list.get(0) == 0 ? 1 : 0;
tail = list.size() - 1;
return total + Math.min(move(0, 0, 1, true), move(0, 0, -1, true));
}
}해석
return total + Math.min(move(0, 0, 1, true), move(0, 0, -1, true));좌측, 우측으로 방향성을 미리 지정하고 그 둘 중 최소값을 구한다.
public int move(int now, int cost, int dir, boolean flag) {
if (head > tail)
return cost;
int[] val = new int[] {-1, -1};
int next;
for(int i = 0; i < 2; i++) {
next = list.get(dir == 1 ? head++ : tail--);
val[i] = move(next, cost + cal(now, next, dir), dir, flag);
if (dir == 1)
head--;
else
tail++;
if (flag) {
dir *= -1;
flag = false;
} else
break;
}
return val[1] == -1 ? val[0] : Math.min(val[0], val[1]);
}잘 생각해보면, 방향 전환은 한 번 밖에 일어나지 않는다. 가장 긴 0의 반복을 만났을 때만 하면 되기에, flag로 방향전환을 했는지 안했는지를 판단하도록 했다.
방향전환을 했다면 해당 방향으로만 간 값을 계산해서 반환, 아니라면 방향전환 전후의 값을 구해 최솟값을 반환.
매 순간마다 방향성을 지정하는 위의 코드보다는 나아졌지만, 대신 코드의 가독성을 잃었으며 효율도 해당 문제에서는 크게 차이나진 않는다. 고작 재귀 몇번 안 탈 뿐이다.
따라서, 좋아요를 제일 많이 받은 최대 효율 코드를 해석해보도록 하겠다.
최대 효율 코드
풀이 코드
class Solution {
public int solution(String name) {
int answer = 0;
int[] diff={0,1,2,3,4,5,6,7,8,9,10,11,12,13,12,11,10,9,8,7,6,5,4,3,2,1};
for(char c:name.toCharArray())
answer+=diff[c-'A'];
int length=name.length();
int min=length-1;
for(int i=0;i<length;i++){
int next=i+1;
while(next<length && name.charAt(next)=='A'){
next++;
}
min=Math.min(min,i+length-next+Math.min(i,length-next));
}
return answer+min;
}
}해석
int[] diff={0,1,2,3,4,5,6,7,8,9,10,11,12,13,12,11,10,9,8,7,6,5,4,3,2,1};
for(char c:name.toCharArray())
answer+=diff[c-'A'];알파벳에 따른 글자의 차이값을 미리 적은 후 answer에 가산.
int min=length-1;
for(int i=0;i<length;i++){
int next=i+1;
while(next<length && name.charAt(next)=='A'){
next++;
}
min=Math.min(min,i+length-next+Math.min(i,length-next));
}초기 최솟값은 글자 길이 - 1이다. 0에서 시작하여 끝 글자까지 한번에 이동한 경우이다.
그 후, 한 글자씩 시작점을 잡고 뒤쪽의 글자들을 본다. 만약 'A'라서 연산할 필요가 없으면 건너뛴다.
'A'가 아닌 글자를 찾았다면, 해당 시작점 i부터 해당 글자 next 사이의 'A'들을 제외한 경로를 탐색한다.
해당 문자열을 예시로 들어보자. 0에서 시작했다면, index가 3인 B를 찾게 된다.
사이의 'A'들을 제외한 경로는 다음과 같다.
이번엔 i를 늘려서 생각해보자.
i가 3일 때, next는 10이 된다.
사이의 'A'들을 모두 피하는 방법은 0에서 3까지 갔다가, 3에서 다시 0으로, 그리고 문자열의 끝으로 이동하여 10까지 가면 된다.
이번엔 i가 0과 멀리 있는 경우, i보다 더 큰 next까지 갔다가 i까지 간다.
즉, i와 next를 비교하여 0과 더 가까운 곳을 찾고, 0으로 돌아와 먼 값까지 진행하면 된다.
min=Math.min(min,i+length-next+Math.min(i,length-next));0에서 i까지는 i, 0에서 next까지는 length - next이다.
해당 값 중 최솟값을 찾아 더해준다.
0으로 돌아와 먼 값까지 진행한다면, i가 가까웠던 경우에는 돌아오는 값 i, 먼 값까지 진행하는 값 length - next가 더해진다.
next가 가까웠던 경우에는 돌아오는 값 length - next, 먼 값까지 진행하는 값 i가 더해진다.
따라서 이 둘은 같은 값이 나온다.
고로 식을 정리하면, 위와 같이 i+length-next+Math.min(i,length-next)가 도출된다.
Python
별로 좋지 않은 풀이. Java의 최대 효율 코드 풀이를 참고하자.
풀이 코드
def solution(name):
text = [min(ord(ch) - 65, 91 - ord(ch)) for ch in name]
stack = [(text, 0, 0)]
answer = 99 * len(name)
while stack:
now, idx, cnt = stack.pop()
cnt += now[idx]
now[idx] = 0
if sum(now) == 0 and answer > cnt:
answer = cnt
continue
left_flag = True
right_flag = True
for step in range(1, len(name)):
if left_flag and now[(idx + step) % len(name)]:
stack.append((now[:], (idx + step) % len(name), cnt + step))
left_flag = False
if right_flag and now[(idx - step) % len(name)]:
stack.append((now[:], (idx - step) % len(name), cnt + step))
right_flag = False
if not (left_flag or right_flag):
break
return answer해석
text = [min(ord(ch) - 65, 91 - ord(ch)) for ch in name]
stack = [(text, 0, 0)]'A'와의 글자 최소 거리값을 구해 list에 넣어주고 stack 선언.
while stack:
now, idx, cnt = stack.pop()
cnt += now[idx]
now[idx] = 0
if sum(now) == 0 and answer > cnt:
answer = cnt
continue
...stack에서 꺼내온 후 현재 idx에 해당하는 값만큼 cnt에 가산. 그 후 0으로 만들어 원하는 글자에 맞췄다는 표시를 한다.
만약 모든 값들이 0이 되어 목표한 문자열을 만들었다면 answer가 최솟값을 들고 있게끔 한다.
하지만 answer보다 cnt가 같거나 크다면 이후 코드가 진행되니, 이중 if문으로 구현해야 한다. 좋지 않은 코드.
left_flag = True
right_flag = True
for step in range(1, len(name)):
if left_flag and now[(idx + step) % len(name)]:
stack.append((now[:], (idx + step) % len(name), cnt + step))
left_flag = False
if right_flag and now[(idx - step) % len(name)]:
stack.append((now[:], (idx - step) % len(name), cnt + step))
right_flag = False
if not (left_flag or right_flag):
break현재 위치에서 좌측으로 이동. 만약 0이 아닌 값을 만났다면 stack에 현재 문자열과 위치, cnt 갱신해서 넣는다.
우측도 마찬가지.
둘 다 flag가 False면 중지.
여담
세상엔 천재가 많다.. 노력을 더 해야겠다.
