[Inflearn] 가장 짧은 문자거리 with Java

문제

한 개의 문자열 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

처음에 고난을 겪었던 부분은 바로 문자 사이 간 증가했다 감소하는 부분이였다.

우선 StringTokenizer를 사용하여 문자열을 토큰 단위로 쪼개였고, 쪼개는 단위는 입력 받은 문자였다.

그리고 단어의 길이 만큼 증가하고 감소하고를 반복했지만, 쪼갠 토큰의 길이가 홀수냐 짝수냐에 따라 많은 작업이 요구되었다.

 

String str = sc.next();
char c = sc.next().charAt(0);
StringTokenzier st = new StringTokenizer(str, Character.toString(c));

위 코드는 입력 받은 문자열 (teachermode) 를 문자 (e) 를 구분점으로 하는 토큰을 생성해준다. 

+ 참고로 StringTokenizer의 구분은 문자는 안되기 때문에 입력 받은 문자를 Character.toString()으로 바꿔주었다. 

 

그러면 teachermode 가 t ach rmod 로 나누어진다. 

 

하지만 여기에서 문제점은 맨 앞 혹은 맨 뒤에 e가 있을 때 이 e들이 없는 취급 당한다는 점이였다. 이를 보완하기 위해 배열로 코드를 다시 구현하였다. 

 

시도2

두 번째 시도는 간단하다. 문자열 길이 만큼의 배열을 선언하고, 해당 문자가 있으면 해당 인덱스에 0을 집어 넣고 cnt를 증가한다.

여기서 강조해야 할 부분은 초기 cnt 값은 따로 선언한 MAX 값을 넣는다는 것이다. 

보면 이해가 될 것이다. 

 

teachermode

t : e가 아니네 cnt 값 

999

teachermode

e: e네 0값! 이제 부터 cnt는 1씩 증가 

999

0

teachermode

a, c, h 까지 계속 증가 후 다시 e를 만남 (다시 0으로 초기화)

999

0

1

2

3

0

teachermode

모든 문자열을 실행했을 때의 결과

999

0

1

2

3

0

1

2

3 ...

근데 결과 값은 0 1 2 1 0 과 같이 증가와 감소를 반복해야 한다. 여기서 등장한 기법이 바로 거꾸로도 한번 더 실행해주는 것이다. 

t 부터 시작했으니 이번엔 왼쪽 e 부터 시작한다. 이 때 두 값이 겹친다면 조금 더 작은 쪽의 손을 들어준다. 

(999와 1을 비교해서 더 작은 값으로 )

999  1

0

1

2

1

0

1

2

1

코드

import java.util.*;
class Main {	
	public int[] solution(String s, char t){
		int[] answer=new int[s.length()];
		int p=1000;
		for(int i=0; i<s.length(); i++){
			if(s.charAt(i)==t){
				p=0;
				answer[i]=p;
			}
			else{
				p++;
				answer[i]=p;
			}
		}
		p=1000;
		for(int i=s.length()-1; i>=0; i--){
			if(s.charAt(i)==t) p=0;
			else{
				p++;
				answer[i]=Math.min(answer[i], p);
			}
		}
		return answer;
	}

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