algorithm
가장 짧은 문자거리
juuuuuuun
2024. 4. 28. 23:41
설명
한 개의 문자열 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
import java.util.Arrays;
import java.util.Scanner;
public class Main {
public static int[] solution(String s, String t) {
int[] ans = new int[s.length()];
Arrays.fill(ans, 101); //ans의 모든 배열을 101로 초기화 해준다. (문자열 길이가 100이 넘지 않으므로)
//s에서 t를 찾는다.
//s 와 t 같을 시 배열에 0 저장
for (int i = 0; i < s.length(); i++) {
if (s.charAt(i) == t.charAt(0)) {
ans[i] = 0;
}
}
//왼쪽 t부터 차례대로 비교해가며 최단거리 ans 배열에 대입
for (int i = 0; i < s.length(); i++) {
if (ans[i] == 0) {
for (int j = 0; j < s.length(); j++) {
if (i > j) {
if (ans[j] > i - j) {
ans[j] = i - j;
}
} else {
if (ans[j] > j - i) {
ans[j] = j - i;
}
}
}
}
}
return ans;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String s = sc.next();
String t = sc.next();
for (int sol : solution(s, t)) {
System.out.print(sol + " ");
}
}
}
소스 코드 2
import java.util.Scanner;
public class Main {
public static int[] solution(String s, char t) {
int[] ans = new int[s.length()];
int p = 1000; //큰 수로 초기화 해 놓는다.
//t와 같은 문자가 있다면 0 대입, 아니라면 p를 1씩 증가시켜 대입한다.
//왼쪽 t 기준으로 거리를 대입하는 알고리즘
for (int i = 0; i < s.length(); i++) {
if (s.charAt(i) == t) {
p = 0;
ans[i] = p;
} else {
p++;
ans[i] = p;
}
}
//오른쪽 t 기준으로 거리를 대입하는 알고리즘
for (int i = s.length() - 1; i >= 0; i--) {
if (s.charAt(i) == t) { //이미 위에서 0을 대입했으니 대입은 안 해줘도 됨
p = 0;
} else {
p++;
ans[i] = Math.min(p, ans[i]); //먼저 있던 거리와 새로운 거리중 최단거리 대입
}
}
return ans;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String s = sc.next();
char t = sc.next().charAt(0);
for (int sol : solution(s, t)) {
System.out.print(sol + " ");
}
}
}