가장 가까운 같은 글자

매일 1일 1커밋을 목표로 알고리즘 문제를 하나씩 풀고 있는데, 생각해보니 이걸 기록을 안하고 있었습니다...

그래서 지금 부터라도 기록을 하기 위해서 글을 작성토록 하겠읍디다...

 

오늘 풀었던 문제는 아래와 같습니다.

 

 

문제

 

풀이

class Solution {
    public int[] solution(String s) {
    	// 기본적으로 문자열의 길이만큼의 크기로 빈 배열을 만듭니다.
        // 이후 확인용으로 사용될 빈 문자열을 만듭니다.
        int[] answer = new int[s.length()];
        String check = "";

		// 받아온 문자열의 길이만큼 반복문을 시작합니다.
        for (int i = 0; i < s.length(); i++) {
        	// 기본적으로 숫자 1을 카운트한 카운트용 변수를 만듭니다.
            int cnt = 1;
            
            // 새롭게 생성된 문자열에 반복문을 따라 나온 순번의 문자가 있는지 확인합니다.
            // 있을 경우 반복문을 시작합니다.
            if (check.contains(String.valueOf(s.charAt(i)))) {
            	// 2중 반복문을 이용해 같은 문자가 있을 경우 하나씩 탐색합니다.
                // 없을 경우 cnt 를 증가시킵니다. 있을경우 2번째 반복문을 종료하고 해당 숫자를
                // 반환할 answer 배열의 해당 i번째에 cnt 값을 넣습니다.
                for (int j = i; j > 0; j--) {
                    if (s.charAt(j - 1) == s.charAt(i)) {
                        answer[i] = cnt;
                        break;
                    }
                    cnt++;
                }
            } else {
            	// 없을 경우 answer 배열의 i번째에 -1을 넣습니다.
                answer[i] = -1;
            }
            
            // 반복문의 마지막엔 항상 확인용 문자열에 받아온 문자열의 i번째 문자를 넣습니다. 
            check += s.charAt(i);
        }
        return answer;
    }
}

 

결과

 

일부러 LinkedList 나 HashMap 같은 다른 자료구조는 사용하지 않고 풀어보았습니다.

확실히 통과는 되었으나 연산에 엄청 긴 시간이 소요됩니다.
뭐 사실 HashMap 은 사용할 생각도 못했다고 하는게 맞는거 같기는 합니다만...

 

그래서 이 이후에 다른 사람들의 풀이 방식중에 HashMap 을 사용한 코드가 가장 인상적이었어서 해당 코드를 가져와서 한번 사용해 봤습니다.

 

 

다른사람의 풀이

import java.util.*;

class Solution {
    public int[] solution(String s) {
    	// 마찬가지로 문자열 길이만큼의 빈 배열을 선언합니다.
        int[] answer = new int[s.length()];
        
        // HashMap 을 이용해서 key 값으로 character 를 지정 value 로는 Integer 를 지정합니다.
        // 이러한 형태의 HashMap 을 선언해줍니다.
        HashMap<Character,Integer> map = new HashMap<>();
        
        // 문자열의 길이 만큼 반복문을 시작합니다.
        for(int i=0; i<s.length();i++){
        	// char 타입의 변수 c 에 받아온 문자열의 i번째 문자를 넣어줍니다.
            // 응답할 배열 answer 의 i번째에 i 번째 에서 map 안에 가져온 ch 값이 존재하는지 확인합니다.
            // 만약 존재하면 i + 1 의 값을 반환합니다.
            // 존재하지 않을 경우에는 i 에서 i + 1 값만큼 뺀 값 즉, -1 을 반환합니다.
            // 이후 mapd에는 key 값에는 받아온 ch를, value 에는 i 를 넣어줍니다.
            char ch = s.charAt(i);
            answer[i] = i-map.getOrDefault(ch,i+1);
            map.put(ch,i);
        }
        return answer;
    }
}

다른사람의 풀이를 보면 굉장히 빠른 시간에 연산이 끝난것을 알 수 있었습니다.

확실히 다양한 자료구조를 알고 또 이를 활용할 줄 알아야 하는 것 같습니다.

 

아래의 글들은 오늘 풀이 과정에서 새롭게 알게 된 사실들을 정리한 내용들 입니다.