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

문제링크

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

프로그래머스

 

 

문제 설명

문자열 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]
"foobar"	[-1, -1, 1, -1, -1, -1]

 

 

입출력 예 설명

입출력 예 #1

지문과 같습니다.

 

입출력 예 #2

설명 생략

 

 

코드

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

코드 설명

주석 참고

1. 맨 처음 글자는 -1로 담고, 이후 등장하는 같은 문자는 이전 문자와의 index 차이를 구하는 문제다.
2. Map은 각 문자의 현재 index를 갱신하여 담는 역할을 한다.
3. 처음 등장하는 문자는 -1이고, 이후 등장하는 문자는 이전에 등장한 같은 문자와의 거리를 answer 배열에 담는다.
4. containsKey() 메서드는 인자로 받은 값이 map의 key 값으로 존재하는지에 대한 여부를 판단한다.
5. key 값이 존재하지 않으면 answer 배열의 해당 위치에 -1을 담는다.
6. 같은 문자가 두 번째 등장하는 경우 해당 문자의 index에 1을 더하는 것과 같은 거리를 가진다.
7. 이후 등장하는 문자는 현재 index에 이전에 등장한 index를 뺀 것과 같은 거리를 가진다.
8. 따라서 현재 인덱스(i) - 이 전에 등장한 index(map에 담긴 value)로 계산할 수 있다.