[코테TIL#16] 프로그래머스 가장 가까운 같은 글자

처음 풀이

import java.util.ArrayList;
import java.util.List;
import java.util.Objects;

class Solution {
    public int[] solution(String s) {
        int[] answer = new int[s.length()];

        String[] str = s.split("");

        String start = str[0];
        answer[0] = -1;

        for(int i = 1; i < str.length; i++) {
            boolean flag = false;
            int gap = 0;

            for(int j = i - 1; j > -1; j--) {
                gap += 1;
                if(Objects.equals(str[i], str[j])) {
                    flag = true;
                    answer[i] = gap;
                    break;
                }
            }

            if(flag == false) {
                answer[i] = -1;
            }
        }

        return answer;
    }
}

 

문제점 1 

자료구조를 고민하다가 stack을 사용하려고 잠깐 생각했었다. 근데 계속 push하고 pop해야 한다는 점이 적합하지 않은 것 같아서 다른 자료 구조를 고민 했는데 마땅히 떠오르지 않아서 일단 배열로 처리를 했다.

 

문제점 2 

for문 안에서 if문으로 조건을 찾고 있었는데 break;를 안 걸어줬었다. 조건과 부합하는 걸 찾았으니 바로 나오도록 break를 추가해주었다.

 

문제점 3

딱히 flag가 필요 없었을 것 같다. 그리고 gap도 for문의 조건을 조금만 수정했더라면 필요 없었을 것 같다.

 

문제점을 고려한 두번째 풀이

import java.util.ArrayList;
import java.util.List;
import java.util.Objects;

class Solution {
    public int[] solution(String s) {
        int[] answer = new int[s.length()];

        String[] str = s.split("");
        
        for(int i = 0; i < str.length; i++) {
		        answer[i] = -1;
            for(int j = 1; j < i + 1; j++) {
                if(Objects.equals(str[i], str[i - j])) {
                    answer[i] = j;
                    break;
                }
            }
        }

        return answer;
    }
}

이렇게 까진 정리해볼 수 있을 것 같다.

최대한 필요 없는 변수를 사용하지 말자 코드가 너무 난잡스러워진다.

 

 

 

다른 사람의 풀이 1 : 자료 구조를 HashMap을 사용하셨다.

import java.util.*;

class Solution {
    public int[] solution(String s) {
        int[] answer = new int[s.length()];
        HashMap<Character,Integer> map = new HashMap<>();
        for(int i=0; i<s.length();i++){
            char ch = s.charAt(i);
            answer[i] = i-map.getOrDefault(ch,i+1);
            map.put(ch,i);
        }
        return answer;
    }
}

 

다른 사람의 풀이 2 : 자료 구조를 HashMap을 사용하셨다.

import java.util.*;

class Solution {
    public int[] solution(String s) {
        int[] answer = new int[s.length()];

        HashMap<Character, Integer> map = new HashMap<>();
        for(int i=0; i<s.length(); i++) {
            if(!map.containsKey(s.charAt(i))) {
                answer[i] = -1;
                map.put(s.charAt(i), i);
            }else {
                int before = map.get(s.charAt(i));
                answer[i] = i - before;
                map.put(s.charAt(i), i);
            }
        }
        return answer;
    }
}

 

 

 

이 문제에서 왜 HashMap 사용이 적합할까 ?

 

1. 빠른 조회 속도 (평균 시간복잡도 O(1) )

이 문제에서는 각 문자의 가장 최근 등장 위치를 저장해야 한다. HashMap을 사용하여 특정 문자가 마지막으로 등장한 위치를 O(1)의 평균 시간복잡도로 조회할 수 있다. 처음엔 리스트 사용을 고려했었는데 리스트를 사용하면 매번 선형 탐색을 해야 하므로 O(n)이 걸릴 수 있어 비효율적이다.

 

2. 효율적인 업데이트

새로운 문자가 등장할 때마다 해당 문자의 위치를 갱신해야 하는데 HashMap을 사용하면 기존 값을 빠르게 업데이트할 수 있어 추가적인 탐색 없이 즉시 반영할 수 있다는 장점이 있다.

 

3. 중복 문자 처리 용이

각 문자의 마지막 위치만 저장하면 되므로, HashMap을 사용하면 불필요한 중복 데이터를 저장하지 않아도 된다. 리스트나 배열을 사용하면 문자마다 여러 개의 위치를 저장하거나 매번 탐색해야 하므로 비효율적일 것이다.

 

 

 

다른 사람의 풀이 3 : String의 index 함수를 사용하셨다.

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

 

 

 

오랜만에 코테를 다시 준비하니까 까먹은 점도 많고 부족한 부분이 많은 거 같다.

Java에서 String과 HashMap Class에서 제공하는 함수들에 대해 더 공부해야겠다.