자바 알고리즘 문제 풀이 입문. 섹션1. String (문자열) : 가장 짧은 문자 거리

 

https://hyejin.tistory.com/1205

자바 알고리즘 문제 풀이 입문. 섹션1. String (문자열) : 숫자만 추출

-> 이전 문제 풀이 

 

 

 

9. 가장 짧은 문자 거리 

 

설명

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

public int[] solution(String s, String x)
{
   int[] answer = new int[s.length()];
   Set<Integer> set = new HashSet<>();
   for (int i = 0; i< s.length(); i++)
   {
      set.add(s.indexOf(x, i));
   }
   
   ArrayList<Integer> arrayList = new ArrayList<>();
   for (int i = 0 ; i< answer.length; i++)
   {
      for (Integer integer : set)
      {
         arrayList.add(Math.abs(integer- s.indexOf(s.charAt(i), i)));
      }
      
      answer[i] =  arrayList.stream().min(Integer::compareTo).get();
      arrayList = new ArrayList<>();
   }
   
   return answer;
}

👩‍💻 : 미련한 나의 풀이 방법 ... 우선 indexOf를 이용해서 주어진 문자 x에 대한 index 위치를 모두 구했다. 

그리고 Set을 이용해서 중복을 제거해서 index 위치들을 저장하고, 

 

그 다음, answer를 반복문으로 도는데 set에 저장된 index 값을 해당 문자열의 위치에서 뺀 다음 (Math.abs를 한 이유는 절대값으로 음수 값을 없애기 위해서) 그 값을 Arraylist에 담았고, 그 다음.. 뺀 값 중 가장 작은 값(가장 짧은 거리)을 구해서 answer 배열에 넣어줬고, 

그 다음 answer를 리턴했다. .

(참 힘들게도 풀었다.) 

 

 

문제 풀이 2

    public int[] solution2(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;
   }
}

👾 : 먼저 강사님은 문자열을 왼쪽에서 오른쪽으로 한번 가고, 오른쪽에서 왼쪽으로 한번 반복문을 돌도록 했다. 

p는 우선 적당히 큰 값으로 초기화해준다. 

 

1. 왼쪽에서 오른쪽 

먼저 주어진 문자열 s 의 길이만큼 for문을 돌면서 

s.charAt(i)가 주어진 문자 t 와 같으면 p 에는 0으로 설정한 다음 answer 배열에 p 값을 저장했다. (p가 주어진 문자에서 해당 문자의 거리가 된다.) 

 

그리고 t와 같지 않다면 p 에서 +1 을 해주고, answer 배열에 p 값을 저장한다. 

그렇게 하면 왼쪽에서 오른쪽으로 진행하면서 왼쪽 t 값에 대한 문자 거리를 구하게 된다. 

for (int i = 0; i < s.length(); i++)
{
   if (s.charAt(i) == t)
   {
      p = 0;
      answer[i] = p;
   }
   else
   {
      p++;
      answer[i] = p;
   }
}

 

2. 오른쪽에서 왼쪽 

그 다음엔 이제 오른쪽에서 왼쪽으로 진행하면서 주어진 문자 t와의 거리를 구해서 answer 값에 넣어주는 데 이때 기존에 들어있던 값보다 값이 적은 경우에만 p 값을 answer 배열에 넣어주면 된다. 

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);
   }
}

 

👩‍💻 : 이렇게 간단한 방법을 놔두고 엄청 빙빙 돌려서 문제를 푼 것 같다... 이 방식 기억해둬야지..