가장 가까운 글자

작성일: 2024-10-19

문제 링크 : 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
설명 생략

접근 방식

  1. HashMap을 이용한다.
  2. 키는 문자, 밸류는 해당 문자의 인덱스
  3. 문자열을 문자 배열로 변환하고 for문을 돌린다.
  4. 해당 문자가 map의 key에 포함되어 있는지 여부를 판단한다.
    • 포함되어 있지 않다면, answer 배열에는 -1을 넣고 map에는 해당 문자와 인덱스를 넣는다.
    • 포함되어 있다면, 해당 문자의 밸류(인덱스)를 answer에 넣고, 밸류를 현재 인덱스로 수정한다.

결과

소스 코드 

import java.util.*;

class Solution {

    public int[] solution(String s) {
        int[] answer = new int[s.length()];

        HashMap<Character, Integer> map = new HashMap<>();

        char tmp[] = s.toCharArray();

        for (int i=0; i<tmp.length; i++){
            if(map.containsKey(tmp[i])){
                answer[i] = i - map.get(tmp[i]);
                map.put(tmp[i], i);
            } else{
                answer[i] = -1;
                map.put(tmp[i], i);
            }
        }

        return answer;
    }
}

결과 이미지

alt text

다른 접근 방식

최적화

  • HashMap && answer에 데이터 입력/수정하는 코드의 중복
  • tmp배열을 사용하지 않고, charAt()으로 대체 가능
import java.util.*;

class Solution {

    public int[] solution(String s) {
        int[] answer = new int[s.length()];

        HashMap<Character, Integer> map = new HashMap<>();

        for (int i=0; i<s.length(); i++){
            char tmp = s.charAt(i);
            answer[i] = i - map.getOrDefault(tmp, i+1);
            map.put(tmp, i);
        }

        return answer;
    }
}

알게 된 점