문제
: 영어 소문자로만 구성된 문자열과 , 영어 소문자 한개가 입력되었을 때,
그 문자열을 구성하는 각 문자별로 - 그 문자열 안에서 - 입력된 소문자 까지의 최소 거리를 구하라
(이때 문자열의 길이는 100을 넘지 않는다)
이 문제는 문제만 읽고선 최소 거리를 어떻게 구할 수 있는지 , 요구사항에 따른 - 해결책이 직관적으로 떠오르지 않는 문제였다.
그런 와중에 나는 노트에 예시 문자열을 적어가면서 , 각 문자별로 어떻게 저 최소 거리값이 나오는지 시뮬레이션을 해 보았다.
이때 "teachermode" 안에서 문자 h가 e까지의 최소거리가 어떻게 1이 되는거지, 에 주목했다.
그 해답은 바로 , h 오른쪽에 있는 e 때문에 최소 거리가 1이 되는 것이었다.
그렇다면 최소 거리라고 했으니깐 이 h와 e와의 거리가 더 있다는 의미였고, 잘 살펴보니 문자 h기준 왼쪽 e까지는 거리가 3칸 떨어져 있었다.
이를 통해 아래와 같이 해결책을 마련할 수 있었다.
[해결책]
- 입력한 문자열을 구성하는 임의의 문자는 모두 자신의 위치 기준으로 왼쪽 방향 또는 오른쪽 방향 중 적어도 한곳에서 , 입력한 소문자를 만날 수 있다.
- 그말은 즉 문자열을 구성하는 각 문자가 갖는 거리는
- 자신 기준으로 오른쪽 방향으로 가면서 가장 먼저 특정 문자를 만나는 거리와
- 자신 기준으로 왼쪽 방향으로 가면서 가장 먼저 특정 문자를 만나는 거리
- 이렇게 2가지 case밖에 없음을 알게 되었다.
- 이렇게 2가지 case 밖에 없다면 해결책은 간단했다.
1) 바로 오른쪽 방향으로 이동하면서 만나는 거리를 다 기록하고
2) 왼쪽 방향으로 이동하면서 만나는 거리를 다 기록한 후
3) 이들간의 더 작은 값을 구하면 되는 문제였다
그런데 한가지 중요한 점이, 그 문자열 안에 특정 문자가 반드시 존재하는지의 여부였다.
나는 이 점에 대해서 , 최소한 1개의 문자는 반드시 존재한다고 확신하였는데,
-> 왜냐하면 그렇지 않았을 경우 [최소거리] 라고 표현할 값을 문제에서 제시하고 있지 않기 때문이다.이점이 왜 중요한 이유는 최소한 1개의 문자가 존재한다면 임의의 문자 별로,
- 오른쪽 방향으로 가면서 거리를 기록할 때와
- 왼쪽 방향으로 가면서 거리를 기록할 때
두 case 중 반드시 한 case에서 만난다는 사실이 보장되기 때문이다
이 사실만 보장된다면 , 두 방향 중 각 방향으로 탐색을 하면서
- 한쪽 방향에서 만나지 못해 , 문제 조건상 나올 수 없는 거리 100을 기록해두어도 (문자열 길이는 100을 넘지 않는다)
- 다른쪽 방향에서 반드시 만나 100보다 작은 거리값이 기록됨이 보장되면
- 두 방향의 거리를 가지고 최소 거리를 구할 때 유효한 최소거리가 반드시 나오기 때문이다.
위와 같은 사고의 흐름으로, 어떻게 최소거리가 구해지는지 시뮬레이션 해보고,
이 때 놓치지 않는 조건은 없는지 생각해 봄으로써
오른쪽/왼쪽 각 방향으로 탐색한 거리를 기록 후 - 이들을 가지고 최소거리를 구하자
라는 해결책을 고안해 낼 수 있었다.
이에 대한 코드 구현은 아래와 같다.
import java.util.Arrays;
import java.util.Scanner;
public class Main {
/**
* 이 문제의 중요한 가정 : 반드시 입력한 문자 c는 문자열 안에 있다!
* 만약 그렇지 않으면 , 최소 거리를 어떻게 표시할 지 문제에 주어져 있지x
* -> 이렇게 최소 한개의 문자 c가 문자열 안에 있다면 , 오른쪽으로 이동하면서 거리를 찾든 or 왼쪽으로 이동하면서 거리를 찾든 ,
* 둘 중 한 방향에서는 만나게 되어 있음 !! -> 이를 전제로 해결하기 때문에 , 100을 넣어도 됨!!
* */
public static int[] solution(String str, char c){
int[] minDistance = new int[str.length()];
int[] distanceFromRight = new int[str.length()];
int[] distanceFromLeft = new int[str.length()];
int distance = 0;
int idx = 0;
//0. 문자열을 char 배열로 변환
char[] charArr = str.toCharArray();
//1. for문과 내부 while문을 돌면서 - 오른쪽 c하고 떨어진 거리를 계산
for(int i=0; i<str.length(); i++){
idx = i;
// 오른쪽으로 이동하면서 문자 c가 있는지 살펴보되 , 오른쪽 끝까지 가도 업으면 절대 나오지 않을 큰 값 100을 대입
while(idx < str.length()){
if(charArr[idx] == c){
distanceFromRight[i] = distance;
distance = 0;
break;
} else{
distance++;
idx++;
}
}
if(idx >= str.length()){
distanceFromRight[i] = 100;
distance = 0;
}
}
//2. for문과 내부 while문을 돌면서 - 왼쪽 e하고 떨어진 거리를 계산
for(int i=0; i<str.length(); i++){
idx = i;
// 왼쪽으로 이동하면서 문자 c가 있는지 살펴보되 , 오른쪽 끝까지 가도 업으면 절대 나오지 않을 큰 값 100을 대입
while(idx >= 0){
if(charArr[idx] == c){
distanceFromLeft[i] = distance;
distance = 0;
break;
} else{
distance++;
idx--;
}
}
if(idx < 0){
distanceFromLeft[i] = 100;
distance = 0;
}
}
//3. 위 1,2 결과 배을 값을 가지고 , 각 element중 작은값으로만 이루어진 최소 거리를 배열에 담아서 리턴
for(int i=0; i<str.length(); i++){
minDistance[i] = (distanceFromRight[i] < distanceFromLeft[i]) ? distanceFromRight[i] : distanceFromLeft[i];
}
return minDistance;
}
public static void main(String[] args) {
//0. Scanner 준비
Scanner sc = new Scanner(System.in);
//1. 문자열 과 문자를 입력받음 (공백을 구분자로 하여)
String str = sc.next();
char c = sc.next().charAt(0);
//2. 입력받은 문자열과 문자를 인자로 넘겨 solution()을 호출후 -> 결과 배열을 반환받음
int[] result = solution(str, c);
//3. 결과 배열 출력
Arrays.stream(result)
.forEach(i -> System.out.print(i + " "));
}
}
사실 이 문제의 해결책을 어느정도 생각한 후, 스택으로 코드 구현을 시도했다가 실패했었는데,
너무 어렵게 접근하기 보다는 - 출제자의 의도 / 문제에서 물어보고자 하는 점을 잘 파악안 후 , 이를 코드로 구현하는 것이 중요한 것 같다고 느꼈다.
[정리할 내용]
- sc.next().charAt(0)
: 문자 콘솔 입력방법을 몰라 이렇게 입력받았었는데,
강의를 보고 이렇게 입력받는게 맞다는걸 확실히 알게 되었다!
