[연습문제] 가장 가까운 같은 글자

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

• 설명 생략

---

문자열 s가 주어졌을 때, s의 각 위치마다 자신보다 앞에 나왔으면서, 자신과 가장 가까운 곳에 있는 같은 글자가 어디 있는지 찾는 문제입니다.

 

자신을 기준으로 얼마나 앞에 있는지를 파악하기 때문에 기존의 문자의 위치를 기억하면서 문제를 풀어야 합니다.

이 문제를 보자마자 파이썬에서는 defaultdict를 사용한 방법이 떠올랐는데, 자바에서 사용한다면 맵 구조(key-value)를 사용할 수 있을 것 같네요.

 

정답 코드를 작성해보겠습니다.

 

1. 자바

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

class Solution {
    public int[] solution(String s) {
        int[] answer = new int[s.length()];
        // Character(key) - Integer(value) 구조의 해시 맵을 구성합니다.
        HashMap<Character, Integer> hmap = new HashMap<Character, Integer>();
        // 반복문을 통해 해시 맵에 값을 집어넣습니다.
        for (int i = 0; i < s.length(); i++) {
            // String에서 값을 가져옵니다.
            char c = s.charAt(i);
            // 해당 키가 존재하면
            if (hmap.containsKey(c)) {
                // 위치가 얼마나 앞인지 answer에 기록합니다.
                answer[i] = i - hmap.get(c);
            }
            // 해당 키가 존재하지 않는다면
            else {
                // 첫 등장이므로 -1로 설정합니다.
                answer[i] = -1;
            } // 위치를 갱신합니다.
            hmap.put(c, i);
        }
        return answer;
    }
}

 

2. 파이썬

from collections import defaultdict
def solution(s):
    answer = []
    # 딕셔너리를 구성합니다. (초기값: -1)
    dt = defaultdict(lambda: -1)
    # 반복문을 통해 위치를 구합니다.
    for i, c in enumerate(s):
        # 초기값 -1이 아니라면 (이전에 등장했으므로)
        if dt[c] != -1:
            # 해당 위치의 차이만큼 answer에 추가합니다.
            answer.append(i - dt[c])
        # 초기값이 -1이라면 (이전에 등장하지 않았으므로)
        else:
            # -1을 기록합니다.
            answer.append(dt[c])
        # 딕셔너리에서 현재 위치로 갱신합니다.
        dt[c] = i
    return answer

 

특정 키에 대해서 값을 계속 갱신한다는 점에서 key - value 구조를 떠올리면 쉽게 풀 수 있는 문제였습니다.