[문제풀이] 01-10. 가장 짧은 문자 거리

인프런, 자바(Java) 알고리즘 문제풀이

String(문자열) 다루기 - 0110. 가장 짧은 문자 거리

---

🗒️ 문제

---

🎈 나의 풀이

	private static int[] solution(String str, char c) {
        char[] chars = str.toCharArray();
        int[] answer = new int[str.length()];

        for(int i=0; i<chars.length; i++) {
            int d = Integer.MAX_VALUE;

            for(int j=0; j<chars.length; j++) {
                if(chars[i] == c) {
                    d = 0;
                    break;
                }
                else if(chars[j] == c ) {
                    if(i>j && i - j < d) d = i - j;
                    else if(i<j && j - i < d) d = j - i;
                }
            }

            answer[i] = d;
        }

        return answer;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String str = sc.nextLine();
        String[] strs = str.split(" ");

        int[] answer = solution(strs[0], strs[1].charAt(0));

        for(int i=0; i<answer.length - 1; i++) {
            System.out.print(answer[i] + " ");
        }
        System.out.print(answer[answer.length - 1]);
    }

---

🖍️ 강의 풀이

	    private static int[] solution(String str, char c) {
        int[] answer = new int[str.length()];
        int p = 1000;
        int len = str.length();

        for(int i=0; i<len; i++) {
            if(str.charAt(i) == c) {
                p = 0;
            } else {
                p++;
            }
            answer[i] = p;
        }

        p = 1000;

        for(int i=0; i<len; i++) {
            if(str.charAt(len - i -1) == c) {
                p = 0;
            } else {
                p++;
            }
            answer[len - i -1] = Math.min(answer[len - i -1 ], p);
        }

        return answer;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String str = sc.nextLine();
        String[] strs = str.split(" ");

        int[] answer = solution(strs[0], strs[1].charAt(0));

        for(int i=0; i<answer.length - 1; i++) {
            System.out.print(answer[i] + " ");
        }
        System.out.print(answer[answer.length - 1]);
    }

---

💬 짚어가기

나의 풀이의 경우 문자열을 최대 n^2번 순회하며 비교한다.
특정 문자와 일치하는 경우에는 0을 저장, 그렇지 않은 경우 거리를 저장하도록 구현했다.

강의에서는 두 단계로 구현하였다.

• 1단계 : 정방향 순회
  정방향으로 순회하며 문자의 왼쪽에 있는 기준 문자와의 거리를 저장한다.
  기준 문자가 등장할 때 마다 p의 값은 0으로 초기화된다.
• 2단계 : 역방향 순회
  역방향으로 순회하며 문자의 오른쪽에 있는 기준 문자와의 거리를 비교한다.
  정방향의 경우보다 더 짧은 경우 역방향 거리를 저장한다.

강의에서 구현한 방식이 시간 복잡도 측면에서 훨씬 유리하다.