[프로그래머스/Lv.1] 가장 가까운 같은 글자

문제 설명

문자열 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은 영어 소문자로만 이루어져 있습니다.

 

입출력 예

s	result
"banana"	[-1,-1,-1,2,2,2]

 

입출력 예 설명

입출력 예 #1

지문과 같습니다.

 

 

 

⭕ 풀이

class Solution {
    public int[] solution(String str) {
        int[] result = new int[str.length()];
        
        for(int i=0;i<str.length();i++){
            
            String subStr = str.substring(0,i);
            if(subStr.indexOf(str.charAt(i))==-1) {
                result[i] = -1;
            }else {
                result[i] = i-subStr.lastIndexOf(str.charAt(i));
            }
        }
        return result;
    }
}

 

✅ 흐름

 

1. 입력받는 문자열의 길이만큼 int배열의 길이를 설정한다

2. 문자열의 길이만큼 반복문을 실행하며 입력받은 문자열 str을 0번째자리부터 i번째 자리까지 잘라 subStr 에 할당한다

3. 잘라낸 문자열 subStr에서 입력받은 문자열 str의 첫글자부터 차례대로 하나씩 찾아나간다

3-1. 찾지못했다면 결과배열 result[]에 -1을 할당해주고

3-2. 찾았다면 현재글자위치인 i 에서 찾아낸 글자의 위치를 빼 result에 담는다

 

banana
잘라낸문자열 :  / 찾을문자 : b / i의 값 : 0 / 찾아낸문자의 위치(제일마지막) : -1
잘라낸문자열 : b / 찾을문자 : a / i의 값 : 1 / 찾아낸문자의 위치(제일마지막) : -1
잘라낸문자열 : ba / 찾을문자 : n / i의 값 : 2 / 찾아낸문자의 위치(제일마지막) : -1
잘라낸문자열 : ban / 찾을문자 : a / i의 값 : 3 / 찾아낸문자의 위치(제일마지막) : 1
잘라낸문자열 : bana / 찾을문자 : n / i의 값 : 4 / 찾아낸문자의 위치(제일마지막) : 2
잘라낸문자열 : banan / 찾을문자 : a / i의 값 : 5 / 찾아낸문자의 위치(제일마지막) : 3

banana로 값을 찍어본다면 이런식으로 나오게되고 

마지막 a를 돌릴때 i의 값은 5이며 lastIndexOf로 우측부터 찾아낸 a의 위치는 3이므로 5 - 3 = 2 를 할당하게 된다.

 

 

 

처음에는 알파벳배열을 만들어 찾았다면 체크해두는식으로 풀어야하나 생각하다가

문자열 메서드를 활용해 풀이했는데 아무래도 문자열로써 다루다보니 테스트케이스별로 시간편차가 컸다...

 

다른사람의 풀이를 보니 다들 HashMap을 사용해 풀이하신것같은데 난 아직 해야할 공부가 많이 남은것같다. 

알고리즘 문제풀이에 List, Map을 자유자재로 사용해보고싶다.

 

 

 

 

 

 

-출처

https://school.programmers.co.kr/learn/courses/30/lessons/142086