[leetcode] Freedom Trail

·2024년 4월 27일
0

코딩

목록 보기
41/45

문제

  • 문제 링크
  • 문자열 ringkey가 주어진다. ring은 첫 문자가 12시 방향에 놓인 원형의 다이얼을 나타낸다. ring을 시계방향 또는 반시계방향으로 돌릴 수 있다. keyring의 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 {
	// ring에서 i번째와 j번째의 거리를 구한다.
    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);
    }

	// 해당 함수는 특정 ring 위치에서 출발했을 때 가장 짧은 경로를 구한다.
    // idmap의 key는 ring에 있는 문자이고, value는 ring에서 key가 위치한 인덱스 값들이다.
    // results는 'ring의 특정 문자에서 특정 key로 가는 짧은 경로 값'을 나타낸다.
    private int DFS(int ringIdx, int keyIdx, Map<Character, List<Integer>> idmap, int[][] results, char[] keys, int n) {
    	// key를 모두 구했으면 0을 반환한다.
        if (keyIdx == keys.length)
            return 0;

		// 이미 계산된 값이 있으면 해당 값을 반환한다.
        if (results[ringIdx][keyIdx] != 0)
            return results[ringIdx][keyIdx];
        
        int minResult = Integer.MAX_VALUE;
        // 다음 key가 있는 위치들을 순회한다.
        for (int nextIdx : idmap.get(keys[keyIdx])) {
        	// 현재 ring 위치에서 출발했을 때 가장 짧은 경로는
            // 현재 위치에서 다음 위치(nextIdx)까지의 거리와
            // 다음 위치에서 출발했을 때 가장 짧은 경로를 더한다.
            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)이다.
profile
개발 일지

0개의 댓글