문제
- 문제 링크
- 문자열
ring
과 key
가 주어진다. ring
은 첫 문자가 12시 방향에 놓인 원형의 다이얼을 나타낸다. ring
을 시계방향 또는 반시계방향으로 돌릴 수 있다. key
는 ring
의 12시 방향에 순서대로 놓아야 하는 문자들이다. ring
을 최소한으로 돌려서 key
에 있는 문자를 순서대로 맞출 때, 가장 작은 step을 구해야 한다. 각 step은 아래 규칙에 따라 증가한다.
ring
에 있는 문자를 한 칸 돌릴 때마다 1 step이 추가된다.
ring
12시 방향에 목표하는 문자를 위치시킨 뒤 버튼을 눌러야 하는데, 이때 1 step이 추가된다.
- 제약 조건
- 문자열 범위:
1 <= ring.length, key.length <= 100
- ring과 key는 알파벳 소문자로 구성되어 있다.
- key에 있는 문자는 항상 ring에 존재한다.
- 예시

풀이
풀기 전
- DP인데 난이도가 hard다ㅠ 제약 조건이 쎄지 않아서 쉬울까 했는데 쉽지 않아보였다. 처음에는 목표 문자들 중에서 항상 가까운 문자로만 이동하면 되지 않을까 했는데, 이후에 나오는 문자들에 대해서도 항상 총 길이가 짧은지를 보장할 수 없었다.
- 최악의 경우가 발생하는 예시는
ring="aaa...bbb...", key="ababab..."
인 거 같다. 만약 a->b->a->...
에 대한 모든 경우의 수를 구하려고 하면 50 * 50 * 50 * ... = 50^100
가지가 나온다. 무리다..
- 모든 경로를 구하지 않고, 특정 순서에서 특정 문자로 가는 경로 중 가장 작은 값을 택하는 방법도 있다. 이렇게 하면 각 단계마다 독립적이기 때문에 경우의 수는
50*50 + 50*50 + ... = 50*50*100
이 된다. 사실 처음에 이 방법으로 풀어서 통과되긴 했는데 영 시원치 않았다. DP가 아닌 거 같다.
- 다른 코드를 참고해보니 제대로 된 DP 방식이 따로 있었다. 내가 풀었던 방식은 앞에서부터 뒤로 가는 방식이었다면, 다른 코드에서는 뒤에서부터 계산하며 저장한 뒤 이미 계산된 값은 재사용 하는 방식이었다. 마치 피보나치 계산하는 느낌으로 풀 수 있었다. 그래서 다시 새로 풀었다.
코드
class Solution {
private int getDistance(int n, int i, int j) {
int d1 = (i - j + n) % n;
int d2 = (j - i + n) % n;
return Math.min(d1, d2);
}
private int DFS(int ringIdx, int keyIdx, Map<Character, List<Integer>> idmap, int[][] results, char[] keys, int n) {
if (keyIdx == keys.length)
return 0;
if (results[ringIdx][keyIdx] != 0)
return results[ringIdx][keyIdx];
int minResult = Integer.MAX_VALUE;
for (int nextIdx : idmap.get(keys[keyIdx])) {
int dist = getDistance(n, ringIdx, nextIdx) + DFS(nextIdx, keyIdx+1, idmap, results, keys, n);
minResult = Math.min(minResult, dist);
}
return results[ringIdx][keyIdx] = minResult + 1;
}
public int findRotateSteps(String ring, String key) {
int n = ring.length();
char[] rings = ring.toCharArray();
char[] keys = key.toCharArray();
Map<Character, List<Integer>> idmap = new HashMap<>();
for (int i=0; i<rings.length; i++) {
char r = rings[i];
if (!idmap.containsKey(r))
idmap.put(r, new ArrayList<>());
idmap.get(r).add(i);
}
return DFS(0, 0, idmap, new int[rings.length][keys.length], keys, n);
}
}
푼 후
- 풀이를 적으면서도 이해가 됐다가 안 됐다가 한다. 헷갈린다. DP 문제를 많이 풀어야 좀 이해가 빨라질 거 같다.
ring
의 특정 문자에서 key
의 특정 문자로 가는 최단 값을 한 번씩만 구하기 때문에 시간 복잡도는 O(ring.length * key.length)
이다. 계산된 값을 저장하므로 공간 복잡도도 O(ring.length * key.length)
이다.