자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비(문자열_가장 짧은 문자거리)

https://cote.inflearn.com/contest/10/problem/01-10

OnlineJudge

(위의 링크는 인프런 로그인 후, 해당 강의를 사지 않으면 접속이 되지 않습니다)

 

10. 가장 짧은 문자거리

 

예시 입력 1 

teachermode e

예시 출력 1

1 0 1 2 1 0 1 2 2 1 0

 

내가 푼 틀린 풀이

나는 해당 문제를 indexOf()를 통해 풀 수 있을 거라고 생각했지만, 중간에 타겟 문자가 있을경우 최소거리를 찾지 못한다는 단점이 있다.

// 출력값
fromLeft = 10321043210
fromRight = 10321043210
1 0 3 2 1 0 4 3 2 1 0

import java.util.Scanner;

public class Main {

    public String solution(String str, char c) {
        String answer = "";

        StringBuilder fromLeft = new StringBuilder();
        StringBuilder fromRight = new StringBuilder();
        for (int i = 0; i < str.length(); i++) {
            int tmp = str.indexOf(c, i * 1);
            System.out.println("tmp = " + tmp);
            System.out.println("i = " + i);
            System.out.println("(tmp-i) = " + (tmp-i));
            fromLeft.append(tmp-i);
        }
        System.out.println("fromLeft = " + fromLeft);

        //
        String reverseStr = new StringBuilder(str).reverse().toString();
        for (int i = 0; i < reverseStr.length(); i++) {
            int tmp = str.indexOf(c, i * 1);
            fromRight.append(tmp-i);
        }
        System.out.println("fromRight = " + fromRight);

        for (int i = 0; i < fromLeft.length(); i++) {
            int min = Math.min(fromLeft.charAt(i) - '0', fromRight.charAt(i) - '0');
            answer += min;
            if (i != fromLeft.length() - 1) {
                answer += " ";
            }
        }

        return answer;

    }

    public static void main(String[] args) {
        Main main = new Main();
        Scanner sc = new Scanner(System.in);
        String str = sc.next();
        char c = sc.next().charAt(0);
        System.out.println(main.solution(str, c));
    }
}

 

 

강의 답안 (Time: 157ms Memory: 27MB)

- 이런 방법을 외우자!

- 왼쪽부터 먼저 탐색하고, 오른쪽 탐색한 다음 그 중에 Math.min()함수로 최솟값 설정

import java.util.Scanner;

public class Main {

    public int[] solution(String str, char c) {
        int[] answer = new int[str.length()];

        // 왼쪽부터 탐색
        int p = 1000;
        for (int i = 0; i < str.length(); i++) {
            if (str.charAt(i) == c) {
                p = 0;
                answer[i] = p;
            }
            else  {
                p++;
                answer[i] = p;
            }
        }
        // answer = [1001, 0, 1, 2, 3, 0, 1, 2, 3, 4, 0]

        // 오른쪽 부터 탐색
        p = 1000;
        for (int i = str.length()-1; i >= 0 ; i--) {
            if (str.charAt(i) == c) p = 0;
            else {
                p++;
                answer[i] = Math.min(answer[i], p);
            }
        }
        return answer;
    }

    public static void main(String[] args) {
        Main main = new Main();
        Scanner sc = new Scanner(System.in);
        String str = sc.next();
        char c = sc.next().charAt(0);
        for(int x : main.solution(str,c)) {
            System.out.print(x + " ");
        }

    }
}

 

 

다른 사람 풀이 (Time: 151ms Memory: 27MB)

1. c가 나타난 인덱스만 따로 list에 저장한다.

2. 입력 문자열과 targetlist를 순회하면서, str의 입덱스값 - target(e가 나타난 인덱스값)을  한 절대값을 또 따로 리스트에 저장한다

3. 그 리스트에서 가장 최소값 Collections.min()을 찾아서 answer변수에 더하기 연산한다.

import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;

public class Main {

    public String solution(String str, char c) {
        String answer = "";

        ArrayList<Integer> targetList = new ArrayList<>();
        for (int i = 0; i < str.length(); i++) {
            int tmp = str.indexOf(c, i * 1);
            targetList.add(tmp);
        }
        
        // 아래 디버깅 출력값 참고
        for (int i = 0; i < str.length(); i++) {
            ArrayList<Integer> test = new ArrayList<>();
            for (int target : targetList) {
                test.add(Math.abs(i-target));
            }
            // 리스트 내에서 최솟값을 찾아서 변수에 할당
            Integer min = Collections.min(test);
            answer += min + " ";
        }

        return answer;
    }

    public static void main(String[] args) {
        Main main = new Main();
        Scanner sc = new Scanner(System.in);
        String str = sc.next();
        char c = sc.next().charAt(0);
        System.out.println(main.solution(str, c));
    }
}

i : 0
target : 1
test : [1]
i : 0
target : 1
test : [1, 1]
i : 0
target : 5
test : [1, 1, 5]
i : 0
target : 5
test : [1, 1, 5, 5]
i : 0
target : 5
test : [1, 1, 5, 5, 5]
i : 0
target : 5
test : [1, 1, 5, 5, 5, 5]
i : 0
target : 10
test : [1, 1, 5, 5, 5, 5, 10]
i : 0
target : 10
test : [1, 1, 5, 5, 5, 5, 10, 10]
i : 0
target : 10
test : [1, 1, 5, 5, 5, 5, 10, 10, 10]
i : 0
target : 10
test : [1, 1, 5, 5, 5, 5, 10, 10, 10, 10]
i : 0
target : 10
test : [1, 1, 5, 5, 5, 5, 10, 10, 10, 10, 10]
min ~~~~~~~ : 1
 : 1
target : 1
test : [0]
i : 1
target : 1
test : [0, 0]
i : 1
target : 5
test : [0, 0, 4]
i : 1
target : 5
test : [0, 0, 4, 4]
i : 1
target : 5
test : [0, 0, 4, 4, 4]
i : 1
target : 5
test : [0, 0, 4, 4, 4, 4]
i : 1
target : 10
test : [0, 0, 4, 4, 4, 4, 9]
i : 1
target : 10
test : [0, 0, 4, 4, 4, 4, 9, 9]
i : 1
target : 10
test : [0, 0, 4, 4, 4, 4, 9, 9, 9]
i : 1
target : 10
test : [0, 0, 4, 4, 4, 4, 9, 9, 9, 9]
i : 1
target : 10
test : [0, 0, 4, 4, 4, 4, 9, 9, 9, 9, 9]
min ~~~~~~~ : 0