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

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

프로그래머스

 

문제 접근

return 값 answer를 문자열 s의 길이 만큼 배열 생성

answer의 첫 문자는 앞에 같은 글자가 있을 수 없으니 -1를 먼저 대입하고 시작했다.

answer 배열의 0번 째 요소는 -1을 넣고 시작했으니 1부터 s의 길이보다 작을 때 까지 실행되는 반복문을 만들고

현재 문자값을 담을 변수 check를 선언했다.

이후 내부 반복문에서 j = i - 1로 1씩 감소하면서 현재 문자값을 담은 check와 가까운 같은 글자를 탐색하고 찾으면 해당 순서의 배열 요소에 i - j로 거리값을 대입 후 다음 차례 진행

못찾으면 -1을 대입하고 다시 탐색한다. 

class Solution {
    public int[] solution(String s) {
        int[] answer = new int[s.length()];
        answer[0] = -1; // 처음 글자는 무조건 -1일 수 밖에 없기에
        
        for(int i=1; i <s.length(); i++) {
        	char check = s.charAt(i);
        	
        	for(int j=i-1; j>=0; j--) { // 현재 문자랑 가까운 같은 문자의 거리를 구하기에 현재 위치에서 -1씩 해줌
        		
        		if(check == s.charAt(j)) {
        			answer[i] = i-j;
        			break; // 답 찾았으니 바로 다음 차례 진행
        		}
        		else answer[i] = -1; 		       		
        	}
        }    
        return answer;
    }
}

 

★ Hash Map을 이용한 방법 ★

풀이 후에 다른 사람들의 방법도 봤었는데 해쉬 맵을 이용한 방법들이 꽤 있어서 hash map이 뭔지 찾아보고 다른 사람의 풀이를 참고하였다.

class Solution { 
    public int[] solution(String s) {
        int[] answer = new int[s.length()];
        HashMap<Character,Integer> hm = new HashMap<>(); // char형 키, Int형 값
        for(int i=0; i<s.length();i++){
            char ch = s.charAt(i);
            answer[i] = i-hm.getOrDefault(ch,i+1); // 키 ch에 값이 있다면 그 값 반환, 없다면 i+1반환
                                               // 없다면 i - (i + 1)이라 -1 돌려줌
            hm.put(ch,i); // ch 키에 i 밸류 저장하므로써 이후 같은 글자가 나오면 확인할 수 있다.
        }
        // hash map은 키는 고유하지만 밸류는 고유하지 않다.
        // 그렇기에 키는 중복이 안되고 밸류는 중복 가능하다
        // 처음에 나온 문자들은 앞서 저장되있던 키가 없으니 -1이 저장되고
        // 이후에 다시 같은 키가 나오면 (지금 나온 키의 순서 - 처음에 나왔던 키의 순서)로 거리를 구하는 원리같다.
        return answer;
    }
}