JS알고리즘 | 가장 짧은 문자거리

1. 문제

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

 

입력설명 |

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

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

입력예제 | teachermode e

출력예제 | 1 0 1 2 1 0 1 2 2 1 0

 

*만약 문제를 읽고도 이해가 안가면, 입력예제와 출력예제를 보면서 어떻게 나오는건지 유추하는 것도 문제해결능력이다. 

 

 

 

2. 접근방법

문자열 앞에서부터 탐색, 뒤에서부터 탐색 비교해서 최소값으로 변경해주기

 

반목문으로 문자열 하나씩 돌면서 탐색

e가 아닐 경우 카운팅하면서 증가시킨다. 

반대로 마지막 인덱스부터 문자열 하나씩 돌면서 탐색

e가 아닐 경우 카운팅하면서 증가시킨다. 

그리고 비교해서 최소값으로 변경해준다. 

 

 

3. 문제풀이

e에서부터의 가장 짧은 거리를 리턴해야한다. 

answer를 배열로 넣고, 값을 배열에 push하기로 한다.

최대문자열의 길이 100이므로 변수 p를 최대값 100으로 작성해주기로 한다.

 

1. 문자 e에서 우측방향으로의 거리 구하기

for of 반복문을 사용해서 문자열을 돌면서 문자가 e가 아니면 p++을 해준다.

e이면 0으로 초기화한다. 

이 방법은 문자 e에서 우측방향으로의 거리를 구한 것이다.

 

2. 문자 e에서 좌측방향으로의 거리 구하고 비교

다시 반복문으로 문자열을 반대로 돈다. 

반대로 돌면서 e에서 좌측방향으로의 거리를 구한다. 

즉, 좌측이든 우측이든 둘중에서 가장 더 작은 수를 리턴하도록 한다. 

 

function solution(str, e){
	let answer = [];
    let p = 100; // 문자열의 길이는 100을 넘지 않으므로 최대값 100으로 설정해준다. 
    for(x of str){
    	if(x === e){
        	p=0; // p를 0으로 초기화해준다
            answer.push(p);
        } else {
        	p++;
            answer.push(p);
        }
    }
    p = 100; // 반복문을 다시 시작하기 전에 변수 p 원래대로 초기화
    for(let i = str.length-1; i>=0; i--){
    	if(str[i] ===e){
        	p=0;
        } else {
        	p++;
            answer[i] = Math.min(answer[i], p);
            // 첫번째 반복문을 통해 들어있는 p와 현재 answer[i]를 비교해서 작은 값으로 바꿔준다.
        }
     }
     return answer;
}

let str = "teachermode";
console.log(solution(str, 'e');

 

 

 

4. 사용개념

Math.min()

Math.min([value1[, value2[, )

여기서 value는 숫자형이어야한다. 1개 이상의 인자값이 숫자형으로 변환이 불가능한 경우 NaN 반환