[Ch.01 - String] 10. 가장 짧은 문자거리 # (+ Math.min, charAt)

10. 가장 짧은 문자거리

 

설명

한 개의 문자열 s와 문자 t가 주어지면 문자열 s의 각 문자가 문자 t와 떨어진 최소거리를 출력하는 프로그램을 작성하세요.

입력

첫 번째 줄에 문자열 s와 문자 t가 주어진다. 문자열과 문자는 소문자로만 주어집니다.

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

출력

첫 번째 줄에 각 문자열 s의 각 문자가 문자 t와 떨어진 거리를 순서대로 출력한다.

 

예시 입력 1 

teachermode e

예시 출력 1

1 0 1 2 1 0 1 2 2 1 0

---

1. 거리 이용

2. 직접 한 칸씩 계산

 

 

 

1. 거리 이용

: Math.abs();

import java.util.*;

public class Main {
	public int[] solution(String str, char s) {
		ArrayList<Integer> list = new ArrayList<>();
		int[] arr = new int[str.length()];
		for (int i = 0; i < str.length(); i++) {
			if (s == str.charAt(i))
				list.add(i);
		}
		for (int i = 0; i < str.length(); i++) {
			int min = Integer.MAX_VALUE;
			for (int j : list) {

				min = Math.min(min, Math.abs(j - i));
				if (Math.abs(j - i) == min)
					arr[i] = min;
			}
		}

		return arr;
	}

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

	}
}

 

 

2. 직접 한 칸씩 계산

import java.util.Scanner;
  
public class Main {
  public int[] solution(String str, char x){
    int[] arr = new int[str.length()];
    int min=Integer.MAX_VALUE;
    char[] s = str.toCharArray();
    int p=1000;
    for(int i=0;i<str.length();i++){
      if(x==s[i]){
        p=0;
        arr[i]=0;
      }
      else{
        p++;
        arr[i]=p;
      }
       
    }
    p=1000;
    for(int j=str.length()-1;j>=0;j--){
      if(x==s[j]){
        p=0;
      }
      else{
        p++;
        min=Math.min(arr[j], p);
        if(p==min) arr[j]=p;
      }
    }
    return arr;
  }
  public static void main(String[] args){
    Main T = new Main();
    Scanner kb=new Scanner(System.in);
    String str = kb.next();
    char x =kb.next().charAt(0);
    for(int i: T.solution(str, x))
    System.out.print(i+" ");
  }
}

-> if문을 이용해 최솟값인지 확인하지 않고, 바로 배열과 비교하도록 변경 

 

import java.util.Scanner;
  
public class Main {
  public int[] solution(String str, char x){
    int[] arr = new int[str.length()];
    int min=Integer.MAX_VALUE;
    char[] s = str.toCharArray();
    int p=1000;
    for(int i=0;i<str.length();i++){
      if(x==s[i]){
        p=0;
        arr[i]=0;
      }
      else{
        p++;
        arr[i]=p;
      }
       
    }
   for(int j=str.length()-1;j>=0;j--){
      if(x==s[j]){
        p=0;
      }
      else{
        p++;
        arr[j]=Math.min(arr[j], p);
        
      }
    }
    return arr;
  }
  public static void main(String[] args){
    Main T = new Main();
    Scanner kb=new Scanner(System.in);
    String str = kb.next();
    char x =kb.next().charAt(0);
    for(int i: T.solution(str, x))
    System.out.print(i+" ");
  }
}

 

 

 

+) 세련된 풀이

해당 문자가 아니면, p++을 이용해 거리를 한칸씩 늘리고, 결과 배열에 입력

1. 앞에서 부터 거리 계산

2. 뒤에서 부터 거리 계산 -> Math.min()을 이용해 최소 거리 구하기

import java.util.*;
public class Main {
	public static void main(String[] args) {
		Main T = new Main();
		Scanner kb = new Scanner(System.in);
		String s = kb.next();
		char c = kb.next().charAt(0);
		// char를 입력받는 방법, next()는 String을 받는데, charAt을 이용해 0번째자리만 추출
		for (int x : T.solution(s, c)) {
			System.out.print(x + " ");
		}
		kb.close();
		}// 소문자로 바꾸는 과정 생략

	public int[] solution(String s, char c) {
		// 1.ds
		int[] answer = new int[s.length()];
		// 문자열 길이 만큼의 결과 배열 생성
		int p = 1000;
        // 1000글자 이하이기 때문에 임의지정
        
        //2. for, while
        
        //앞에서 부터 거리 계산
        for (int i = 0; i < s.length(); i++) {
              if (s.charAt(i) == c) {
                  p = 0;
                  //해당 문자가 있으면 거리를 0으로 초기화
                  answer[i] = p;
                  //결과 배열에 거리를 입력하기 위해 설정
              } else {
                  p++;
                  //해당 문자가 아니면 거리를 하나씩 늘림

                  answer[i] = p;
                  //결과 배열에 거리 입력
              }
          }
      //뒤에서 부터 거리 계산
      for(int i=s.length()-1; i>=0; i--){
        if(s.charAt(i)==c)
          	p=0;
       	else{
          p++;
          answer[i]=Math.min(answer[i], p);
         }
       }
		
		return answer;
	}
}

 

Arrays 클래스의 메소드

1. sort() - UDT인 경우, Comparator 인터페이스 구현 필요

2. 배열 복사 메서드

	System.arraycopy(int[] src, int srcPos, int[] dest, int destPos, int length);
	// (원본배열, 원본시작인덱스, 타겟배열, 타겟시작인덱스, 복사개수)

3.

	char[] arr2 = Arrays.copyOf(arr1, arr1.length);
	// arr1 배열 arr1.length 만큼을 arr2로 복사
	char[] arr3 = Arrays.copyOfRange(arr1, 1, 3);
	// arr1[1] ~ arr1[2] 를 arr3[0] ~ arr3[1] 로 복사
	// 1~3 전까지

 

4. binarySearch() - 정렬 후 사용가능 : 원하는 항목 인덱스값 반환

5.

void fill(배열, 값)
void fill(배열, 시작인덱스, 끝인덱스, 값)

 

 

1. 배열의 모든 값을 배열의 길이로 초기화

2. 문자열을 돌면서, 문자열의 값이 문자값과 동일할 경우,

: 값을 비교하는데, 해당 배열 인덱스의 값과, 동일한 인덱스와 해당 문자의 인덱스 위치까지의 거리를 비교해 작은 값 선택

import java.util.*;
  
public class Main {
  public static void main(String[] args){
    Scanner in=new Scanner(System.in);
    String input1 = in.next();
    char c=in.next().charAt(0);
    solution(input1, c);
  }
  static void solution(String str, char c){
    int[] arr = new int[str.length()];
    //왼쪽에서부터, 오른쪽에서부터 서로 체크 필요
    int n=str.length();
    
    Arrays.fill(arr, str.length());
    for(int i=0;i<n;i++){
      if(str.charAt(i)==c){
        for(int j=0;j<n;j++){
          arr[j]=Math.min(arr[j],Math.abs(i-j));
        }
      }
    }
    
    for(int x: arr) System.out.print(x+" ");
  }
}

 

---

1. flag를 이용해, 아직 해당 문자가 나오지 않았을 땐, MAX_VALUE로 초기화, 그 외엔 cnt++로 초기화

2. 해당 문자 발견시 cnt++하면서 해당 위치 배열값과 비교해 작은값 선택 -> cnt++하지 않고, 거리와 해당 배열값 비교하도록 변경

import java.util.Scanner;
  
public class Main {
  public static void main(String[] args){
    Scanner in=new Scanner(System.in);
    String str = in.next();
    char c=in.next().charAt(0);
    int[] arr = new int[str.length()];
    char[] charr= str.toCharArray();
    boolean flag=false;
    int cnt=0;
    for(int i=0;i<str.length();i++){
      if(flag) {
        cnt++;
        arr[i]=cnt;
      }else{
        arr[i]=Integer.MAX_VALUE;
      }
      if(charr[i]==c){
        cnt=0;
        arr[i]=0;
        flag=true;
        int j=i-1;
        while(j>=0 && charr[j]!=c){
          cnt++;
          arr[j]=Math.min(arr[j],cnt);
          j--;
        }
        cnt=0;
      }
    }
    for(int x: arr) System.out.print(x+" ");
  }
}

1. flag를 이용해, 아직 해당 문자가 나오지 않았을 땐, MAX_VALUE로 초기화, 그 외엔 cnt++로 초기화

2. 해당 문자 발견시 거리와 해당 배열값 비교해 작은 값으로 변경

import java.util.Scanner;
  
public class Main {
  public static void main(String[] args){
    Scanner in=new Scanner(System.in);
    String str = in.next();
    char c=in.next().charAt(0);
    int[] arr = new int[str.length()];
    char[] charr= str.toCharArray();
    boolean flag=false;
    int cnt=0;
    for(int i=0;i<str.length();i++){
      if(flag) {
        cnt++;
        arr[i]=cnt;
      }else{
        arr[i]=Integer.MAX_VALUE;
      }
      if(charr[i]==c){
        cnt=0;
        arr[i]=0;
        flag=true;
        int j=i-1;
        while(j>=0&&charr[j]!=c){
          arr[j]=Math.min(arr[j],i-j);
          j--;
        }
      }
    }
    for(int x: arr) System.out.print(x+" ");
  }
}