[JAVA-알고리즘 문제풀이] 가장 짧은 문자 거리

문제

한 개의 문자열 s, 문자 t가 주어지면 문자열 s의 각 문자가 문자 t와 떨어진 최소 거리를 출력하시오.

 

입력 설명

문자열과 문자는 소문자다.

문자열의 길이는 100을 넘지 않는다.

 

입력 예제

teachermode e

 

 

출력 예제

1 0 1 2 1 0 1 2 2 1 0

 

 

나의 풀이

package com.algorithm._01_그리디_구현;

import java.util.Arrays;
import java.util.Scanner;

/**
 * (문제)
 * 한 개의 문자열 s, 문자 t가 주어지면 문자열 s의 각 문자가 문자 t와 떨어진 최소 거리를 출력
 *
 * (입력설명)
 * 문자열과 문자는 소문자
 * 문자열의 길이는 100을 넘지 않는다.
 *
 * (입력예제)
 *  teachermode e
 * (출력예제)
 *  1 0 1 2 1 0 1 2 2 1 0
 */
public class LC10_가장_짧은_문자거리 {
    static String str;
    static String target;

    public static void main(String[] args) {
        // write your code here
        LC10_가장_짧은_문자거리 sample = new LC10_가장_짧은_문자거리();
        sample.solution();
    }

    public void solution() {
        input();

        StringBuilder sb = new StringBuilder();

        for (int i = 0; i < str.length(); i++) { // 문자열 순회하여 찾기
            int min = Integer.MAX_VALUE;

            // 문자가 동일할 경우 0 고정
            if (String.valueOf(str.charAt(i)).equals(target)) {
                min = 0;
                sb.append(min).append(" ");
            } else {
                for (int j = 0; j < str.length(); j++) { // target 과 동일한 문자 찾기
                    if (String.valueOf(str.charAt(j)).equals(target)) { // target 과 동일한 경우
                        if (Math.abs((i - j)) < min) { // 최소값 찾기
                            min = Math.abs((i - j));
                        }
                    }
                }

                sb.append(min).append(" ");
            }
        }

        System.out.println(sb);
    }

    private void input() {
        Scanner sc = new Scanner(System.in);

        String input = sc.nextLine(); // teachermode e

        str = input.split(" ")[0]; // teachermode
        target = input.split(" ")[1]; // e
    }
}

1) 문자 'e'와 동일한 경우에는 0을 고정하여 담는다.

// 문자가 동일할 경우 0 고정
if (String.valueOf(str.charAt(i)).equals(target)) {
    min = 0;
    sb.append(min).append(" ");
} else {
    ...
}

 

2) 각 문자열의 인덱스와 문자 'e' 와의 인덱스의 차를 절댓값으로 구한다.

if (String.valueOf(str.charAt(j)).equals(target)) { // target 과 동일한 경우
    if (Math.abs((i - j)) < min) { // 최소값 찾기
        min = Math.abs((i - j));
    }
}

 

 

 

해설  풀이

package com.algorithm._01_그리디_구현;

import java.util.Arrays;
import java.util.Scanner;

/**
 * (문제)
 * 한 개의 문자열 s, 문자 t가 주어지면 문자열 s의 각 문자가 문자 t와 떨어진 최소 거리를 출력
 *
 * (입력설명)
 * 문자열과 문자는 소문자
 * 문자열의 길이는 100을 넘지 않는다.
 *
 * (입력예제)
 *  teachermode e
 * (출력예제)
 *  1 0 1 2 1 0 1 2 2 1 0
 */
public class LC10_가장_짧은_문자거리 {
    static String str;
    static String target;

    public static void main(String[] args) {
        // write your code here
        LC10_가장_짧은_문자거리 sample = new LC10_가장_짧은_문자거리();
        sample.solution2();
    }

    /**
     * 강의 해설 1
     */
    public void solution2() {
        int[] answer = new int[str.length()];
        int p = 1000;
        char t = target.charAt(0);

        // 왼쪽 시작
        for (int i = 0; i < str.length(); i++) {
            if (str.charAt(i) == t) {
                p = 0;
                answer[i] = p;
            } else {
                p++;
                answer[i] = p;
            }
        }

        // 오른쪽 시작
        p = 1000;
        for (int i = str.length() - 1; i >= 0; i--) {
            if (str.charAt(i) == t) {
                p = 0;
            } else {
                p++;
                answer[i] = Math.min(answer[i], p); // 작은값으로 대체
            }
        }

        System.out.println(Arrays.toString(answer));
    }

    private void input() {
        Scanner sc = new Scanner(System.in);

        String input = sc.nextLine(); // teachermode e

        str = input.split(" ")[0]; // teachermode
        target = input.split(" ")[1]; // e
    }
}

1) 왼쪽부터 시작하는 경우

문자	변수 p	변수 p 변경	answer
start	p = 1000
t		p++	1001
e		p = 0	0
a		p++	1
c		p++	2
h		p++	3
e		p = 0	0
r		p++	1
m		p++	2
o		p++	3
d		p++	4
e		p = 0	0

변수 p를 선언하여 초기값은 1000으로 셋팅한다. 왼쪽부터 반복문을 수행하여 문자 'e'를 만나는 경우는 p를 0으로 셋팅하고, 그 이후는 p + 1을 수행한다.

// 왼쪽 시작
for (int i = 0; i < str.length(); i++) {
    if (str.charAt(i) == t) {
        p = 0;
        answer[i] = p;
    } else {
        p++;
        answer[i] = p;
    }
}

 

2) 오른쪽부터 시작하는 경우

문자	변수 p	변수 p 변경	answer	위 1)번 결과와 비교
start	p = 1000
e		p = 0	0
d		p++	1	1 < 4
o		p++	2	2 < 3
m		p++	2
r		p++	1
e		p = 0	0
h		p++	1	1 < 3
c		p++	2
a		p++	1
e		p = 0	0
t		p++	1	1 < 1001

다시 p를 1000으로 셋팅하고 오른쪽부터 반복문을 수행한다. 위 1)번과 다른 점은 1)번의 결과와 비교하여 최솟값으로 셋팅해야한다는 점이다.

// 오른쪽 시작
p = 1000;
for (int i = str.length() - 1; i >= 0; i--) {
    if (str.charAt(i) == t) {
        p = 0;
    } else {
        p++;
        answer[i] = Math.min(answer[i], p); // 작은값으로 대체
    }
}