여러가지/알고리즘 & 자료구조

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

hyeseong-dev 2024. 10. 16. 14:40

가장 가까운 같은 글자 문제 풀이

문제 설명
문자열 s가 주어졌을 때, 각 위치마다 자신보다 앞에 나온 동일한 글자가 있는지 확인하고, 가장 가까운 동일한 글자의 거리를 계산하는 문제입니다. 만약 같은 글자가 없으면 -1로 표시하고, 가장 가까운 동일한 글자가 있으면 그 거리를 반환합니다.

예시

예를 들어, 문자열 s = "banana"가 주어졌을 때, 각 문자는 다음과 같이 처리됩니다:

  • b: 처음 등장했으므로 -1.
  • a: 처음 등장했으므로 -1.
  • n: 처음 등장했으므로 -1.
  • a: 앞에서 두 번째 인덱스에 같은 글자 'a'가 있으므로 2.
  • n: 앞에서 두 번째 인덱스에 같은 글자 'n'이 있으므로 2.
  • a: 앞에서 두 번째, 네 번째 인덱스에 'a'가 있지만, 가까운 곳은 두 번째 앞이므로 2.

결과는 [-1, -1, -1, 2, 2, 2]입니다.

문제 분석

이 문제에서 중요한 점은 문자가 등장한 마지막 위치를 기록하면서, 새로운 문자가 등장할 때마다 이전 위치와의 거리를 계산하는 것입니다. 이를 효율적으로 처리하기 위해서는 각 문자의 마지막 등장 위치를 기록할 자료구조가 필요합니다.

Map 자료구조를 사용하면 각 문자가 마지막으로 등장한 위치를 저장할 수 있으며, 새로운 문자가 등장할 때마다 이를 갱신하여 O(1) 시간에 접근이 가능합니다.

제한 사항

  1. 문자열 s의 길이는 최대 10,000입니다.
  2. 문자열 s는 영어 소문자로만 이루어져 있습니다.

자바 코드 풀이

package lv1.가장가까운같은글자;

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

class Solution {
    public int[] solution(String s) {
        // 문자와 마지막으로 등장한 인덱스를 저장하는 맵
        Map<Character, Integer> map = new HashMap<>();
        // 결과를 저장할 배열
        int[] intArr = new int[s.length()];

        // 첫 번째 문자는 무조건 -1 처리
        intArr[0] = -1;
        map.put(s.charAt(0), 0);  // 첫 문자의 인덱스 0을 기록

        for(int i = 1; i < s.length(); i++){
            char c = s.charAt(i);

            // 같은 문자가 이전에 등장했는지 확인
            if(!map.containsKey(c)){
                // 이전에 등장하지 않았다면 -1
                intArr[i] = -1;
            } else {
                // 이전에 등장했다면 현재 인덱스와의 거리 계산
                intArr[i] = i - map.get(c);
            }

            // 현재 문자의 마지막 등장 위치 갱신
            map.put(c, i);
        }
        return intArr;
    }

    public static void main(String[] args) {
        var solution = new Solution();
        System.out.println(Arrays.toString(solution.solution("banana")));  // [-1, -1, -1, 2, 2, 2]
        System.out.println(Arrays.toString(solution.solution("foobar")));  // [-1, -1, 1, -1, -1, -1]
    }
}

코드 설명

  1. 자료구조 사용: Map<Character, Integer>를 사용하여 각 문자가 마지막으로 등장한 위치를 저장합니다. Map을 사용하면 특정 문자가 마지막으로 등장한 위치에 대해 빠르게 접근할 수 있습니다.

  2. 첫 번째 문자 처리: 첫 번째 문자는 앞에 동일한 문자가 없으므로 -1로 처리됩니다. 이를 먼저 설정하고, 이후의 문자는 반복문을 통해 처리됩니다.

  3. 거리 계산: 각 문자가 등장할 때마다, Map에서 해당 문자가 이전에 등장했는지 확인합니다. 만약 등장했으면 현재 인덱스에서 마지막으로 등장한 인덱스를 빼서 거리를 계산하고, 이전에 등장하지 않았다면 -1을 반환합니다.

  4. 결과 배열 생성: 각 문자의 결과값을 배열에 저장하여 최종적으로 반환합니다.

시간 복잡도

  • 시간 복잡도: 문자열의 각 문자를 한 번씩 순회하면서, 각 문자에 대해 Map을 사용하여 인덱스 값을 갱신하고 조회하는 작업을 수행합니다. Map에서의 조회 및 삽입 작업은 평균적으로 O(1)에 수행되므로, 전체 시간 복잡도는 O(n)입니다. 여기서 n은 문자열 s의 길이입니다.

  • 공간 복잡도: 각 문자를 기록하는 Map과 결과를 저장하는 배열을 사용하므로, 공간 복잡도는 O(n)입니다. 문자열이 최대 10,000자이므로 충분히 효율적으로 처리할 수 있습니다.

결론

이 문제는 각 문자의 마지막 등장 위치를 추적하여, 새로운 문자가 등장할 때마다 그 거리를 계산하는 방식으로 해결됩니다. 이를 효율적으로 처리하기 위해 Map 자료구조를 사용하였으며, 시간 복잡도는 O(n)으로 매우 효율적입니다.

입출력 예시:

  • "banana" -> [-1, -1, -1, 2, 2, 2]
  • "foobar" -> [-1, -1, 1, -1, -1, -1]

시저 암호처럼 간단한 암호화 문제와는 다르게, 이 문제는 각 문자의 마지막 등장 위치를 추적하여 빠르게 처리해야 하는 점이 특징입니다.

저작자표시 (새창열림)