[프로그래머스 Level 1] 가장 가까운 같은 글자(Java)

문제

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

프로그래머스

 

풀이

1. 2중 for문을 통해 글자를 찾는다

2. 가까운 글자를 찾으면 break 시켜주고 현재 인덱스에서 찾은 인덱스를 빼 answer 배열에 넣는다.

3. 글자를 찾지 못하면 -1을 answer 배열에 넣는다.

 

코드

class Solution {    
    public int[] solution(String s) {
        int[] answer = new int[s.length()];
        for(int i=0; i<s.length(); i++){
            char ch = s.charAt(i);
            boolean find = false;
            for(int j=i-1; j>=0; j--){
                if(ch==s.charAt(j)){ //가까운 같은 글자가 있는 경우
                    answer[i] = i-j;
                    find = true;
                    break;
                }
            }
            if(!find){ //가까운 같은 글자가 없는 경우
                answer[i]=-1;
            }
        }
        return answer;
    }
}

 

찾으면 break를 시켜주지만 아무래도 2중 for문이라서 시간 복잡도 효율이 좋지 않다.

HashMap을 통해 푸는게 훨씬 효율이 좋을 것이다.

 

다른사람 풀이 코드

import java.util.Map;
import java.util.HashMap;

class Solution {
    public int[] solution(String s) {
        // 결과를 담을 배열 선언
        int[] answer = new int[s.length()];
        // s의 문자와 index를 담을 map 선언
        Map<Character, Integer> map = new HashMap<>();
        
        // s의 길이만큼 반복
        for (int i = 0; i < s.length(); i++) {
            // 해당 문자가 map에 없다면 -1
            if (!map.containsKey(s.charAt(i))) {
                answer[i] = -1;
                map.put(s.charAt(i), i);
            } else {
                // 해당 문자가 map에 존재하면 i - 이전 문자의 인덱스
                answer[i] = i - map.get(s.charAt(i));
                map.put(s.charAt(i), i);
            }
        }
        
        return answer;
    }
}