가장 가까운 같은 글자 - Java [코딩테스트 연습]

 

 

❤️ Problem

• 문제
  문자열 s가 주어졌을 때, s의 각 위치마다 자신보다 앞에 나왔으면서, 자신과 가장 가까운 곳에 있는 같은 글자가 어디 있는지 알고 싶습니다.
  예를 들어, s="banana"라고 할 때,  각 글자들을 왼쪽부터 오른쪽으로 읽어 나가면서 다음과 같이 진행할 수 있습니다.
  
  b는 처음 나왔기 때문에 자신의 앞에 같은 글자가 없습니다. 이는 -1로 표현합니다.
  a는 처음 나왔기 때문에 자신의 앞에 같은 글자가 없습니다. 이는 -1로 표현합니다.
  n은 처음 나왔기 때문에 자신의 앞에 같은 글자가 없습니다. 이는 -1로 표현합니다.
  a는 자신보다 두 칸 앞에 a가 있습니다. 이는 2로 표현합니다.
  n도 자신보다 두 칸 앞에 n이 있습니다. 이는 2로 표현합니다.
  a는 자신보다 두 칸, 네 칸 앞에 a가 있습니다. 이 중 가까운 것은 두 칸 앞이고, 이는 2로 표현합니다.
  따라서 최종 결과물은 [-1, -1, -1, 2, 2, 2]가 됩니다.
  
  문자열 s이 주어질 때, 위와 같이 정의된 연산을 수행하는 함수 solution을 완성해주세요.

 

• 제한 사항
  • 1 ≤ s의 길이 ≤ 10,000
  • s은 영어 소문자로만 이루어져 있습니다.

 

• 입출력 예 & 설명

no	participant	result
1	"banana"	[-1, -1, -1, 2, 2, 2]
2	"foobar"	[-1, -1, 1, -1, -1, -1]

1. 지문과 같습니다.
2. 설명 생략

---

 

💛 Solution

풀이

import java.util.Arrays;
class Solution {
    public int[] solution(String s) {
        int[] answer = new int[s.length()];
        int[] alpha = new int[26];
        Arrays.fill(alpha, -1);

        for(int i=0; i<s.length(); i++) {
            int tmp = s.charAt(i)-97;
            if(alpha[tmp] == -1) {
                answer[i] = alpha[tmp];
            } else {
                answer[i] = i - alpha[tmp];
            }
            alpha[tmp] = i;
        }
        return answer;
    }
}

 

처리속도 VERY GOOD😎

 

---

 

💜 Comment

먼저 반환할 int[] answer을 s.length길이만큼 만들어 둔다. 그 다음, 알파벳 개수만큼의 배열 int[] alpha를 만든다. alpha[0]은 a라고 가정한다. alpha[]에는 Arrays.fill();을 사용해서 -1씩을 넣어둔다. 이렇게 하는 이유는 처음 등장하는 알파벳은 -1 값을 가져야하기 때문이다.

for문 안에서 int tmp = s.charAt(i)-97;을 선언한다. 97을 빼는 이유는 아스키 코드에서 소문자 a가 97부터 시작하기 때문에, 배열 0번이 a가 될 수 있도록 그 숫자만큼을 빼는 것이다.

그 다음 if문을 사용해서 alpha[tmp]가 -1이면 == 즉, 처음 등장한 경우에는 answer[i]에 alpha[tmp] 값을 넣도록 하였다. 그렇지 않은 경우에는 alpha[tmp] 안에 들어있는 배열 위치를 i에서 빼준다. 그 이유는 i는 현재 알파벳의 현재 위치이므로 여기서 얼마나 떨어져있는지를 알기 위해서 특정 알파벳이 등장한 현재위치에서 해당 알파벳이 이전에 등장한 배열 번호를 빼야하기 때문이다.

그 다음, alpha[tmp] = i;를 넣어서 alpha[]의 해당 알파벳이 등장한 최신 위치를 갱신해준다.

 

 

 

8478위!!