[알고리즘/인프런]1-10 가장 짧은 문자거리(인프런 자바(Java) 알고리즘 문제풀이 : 코딩테스트 대비 강의)

인프런의 자바(Java) 알고리즘 문제풀이 : 코딩테스트 대비 강의를 수강하며 예습 풀이 코드, 강의에서 설명하는 풀이 코드를 정리하고 있습니다.

• 문제 링크 : https://cote.inflearn.com/contest/10/problem/01-10
• 문제 설명 : 문자열과 문자가 주어졌을때 문자열의 각 문자가 주어진 문자로부터 떨어진 최소 거리를 구하는 문제

내 풀이

• 문자열 중 주어진 문자 t의 위치를 모두 찾아 저장해놓고, 문자열의 각 문자들을 대상으로 어떤 위치의 t와 가까운지 비교해서 풀이

import java.io.*;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class Main {

    public String solution(String s, char t) {
        List<Integer> pos = new ArrayList<>();
                //문자 t가 있는 위치를 찾는다.
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == t) {
                pos.add(i);
            }
        }

        StringBuilder sb = new StringBuilder();

        for (int i = 0; i < s.length(); i++) {
            //어떤 위치의 문자 t와 가장 가까운지 찾는다.
            int min = Math.abs(pos.get(0)-i);

            for (int j = 1; j < pos.size(); j++) {
                if (min > Math.abs(pos.get(j) - i)) {
                    min = Math.abs(pos.get(j) - i);
                }
            }

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

        return sb.toString();
    }


    public static void main(String[] args) throws IOException {
        Main T = new Main();
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(br.readLine());
        String s = st.nextToken();
        char t = st.nextToken().charAt(0);
        System.out.println(T.solution(s, t));
    }
}

강의 풀이

• 각 문자의 좌측에 있는 가까운 문자 t로부터의 거리, 우측에 있는 가까운 문자 t로부터의 거리를 구한다.
• 둘 중 작은 값이 최소 거리

import java.io.*;
import java.util.Scanner;

public class Main {

    public int[] solution(String s, char t) {
        int[] retArr = new int[s.length()]; //거리 배열
        int p = 1000; //t와의 거리

        //좌측에 있는 가장 가까운 t로부터의 거리
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == t) {
                p = 0;
            } else {
                p++;
            }

            retArr[i] = p;
        }

        //우측에 있는 가장 가까운 t로부터의 거리
        p = 1000;
        for (int i = s.length() - 1; i >= 0; i--) {
            if (s.charAt(i) == t) {
                p = 0;
            } else {
                p++;
            }

            retArr[i] = Math.min(retArr[i], p); //좌측과 우측 어디 쪽의 t와 가까운지
        }

        return retArr;
    }


    public static void main(String[] args) {
        Main T = new Main();
        Scanner sc = new Scanner(System.in);

        String s = sc.next();
        char t = sc.next().charAt(0);

        int[] arr = T.solution(s, t);

        for (int i : arr) {
            System.out.print(i + " ");
        }
    }
}