[알고리즘] 가장 가까운 같은 글자 찾기: HashMap으로 이중 루프 예방하기

문제 본문

문자열 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,000s은 영어 소문자로만 이루어져 있습니다.

나의 풀이

3줄 접근

초기화: 정수 리스트를 만들고, -1을 넣는다.
문자 길이가 2 이상이면 문자들을 2번째자리부터 읽어가며 알고리즘을 실행한다.
정수 리스트를 배열로 변환하여 반환한다.

 

실제 코드

import java.util.List;
import java.util.ArrayList;

class Solution {
    public int[] solution(String s) { // e.g. s = "banana"
        List<Integer> answerList = new ArrayList<>();
        answerList.add(-1);
        
        if(s.length() > 1) {
            for(int i = 1; i < s.length(); i++) {
                answerList.add(-1);
                
                for(int j = 1; j <= i; j++) {
                    if(s.charAt(i) == (s.charAt(i - j))) {
                        answerList.remove(i);
                        answerList.add(j);
                        break;
                    }
                }
    
            }
        }
        
        return answerList.stream()
            .mapToInt(Integer::intValue)
            .toArray();
    }
}

 

분석

• 시간 복잡도: O(n²)
• 공간 복잡도: O(n)
• 사용하는 자료구조: List(ArrayList)

장점

• 접근 자체는 직관적이고 정확함. 가장 가까운 것부터 역순 탐색하는 방향이 논리적
• 3줄 접근 주석으로 사고 과정을 명시한 점은 좋음

한계

• answerList.remove(i) 후 answerList.add(j)는 불필요한 조작. 처음부터 -1을 넣지 않고 결과값을 직접 set하거나, 배열을 사용하면 회피 가능
• ArrayList → stream().mapToInt() → int[] 변환 과정이 불필요하게 복잡함. 처음부터 int[]를 쓰는 것이 명확
• if(s.length() > 1) 조건은 불필요. 길이가 1이면 루프가 실행되지 않음
• 시간복잡도 O(n²), 공간복잡도 O(n)

 

---

 

모범답안

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 ch = s.charAt(i);
            answer[i] = i-map.getOrDefault(ch,i+1);
            map.put(ch,i);
        }
        return answer;
    }
}

 

분석

• 시간 복잡도: O(n)
• 공간 복잡도: O(1)
• 사용하는 자료구조: Map(HashMap)

장점

• getOrDefault(ch, i+1)로 미등록 문자일 때 자동으로 -1이 나오게 한 설계가 깔끔함 (i - (i+1) = -1)
• 루프 한 번으로 해결. 시간복잡도 O(n), 공간복잡도 O(1) (알파벳 26자 고정)
• 실무 수준에 가장 가까운 풀이

한계

• getOrDefault의 default값으로 i+1을 쓴 의도가 코드만 보면 즉시 파악되지 않음. 짧은 주석이 있었다면 가독성이 더 좋았을 것

 

모범답안 2

class Solution {
    public int[] solution(String str) {
        int[] result = new int[str.length()];

        for(int i=0;i<str.length();i++){

            String subStr = str.substring(0,i);
            if(subStr.indexOf(str.charAt(i))==-1) {
                result[i] = -1;
            }else {
                result[i] = i-subStr.lastIndexOf(str.charAt(i));
            }
        }
        return result;
    }
}

 

분석

• 시간 복잡도: O(n²)
• 공간 복잡도: O(n)
• 사용하는 자료구조: String

장점

• lastIndexOf를 활용해 "가장 가까운 이전 위치"라는 문제 의도를 코드로 자연스럽게 표현함
• 가독성이 세 풀이 중 가장 높음

한계

• 루프마다 substring() 객체를 새로 생성 → 시간복잡도 O(n²), 추가 메모리 O(n) 반복 할당
• n이 10,000에 가까워질수록 성능 저하가 명확함

---

최종 개선 코드

import java.util.HashMap;

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 ch = s.charAt(i);
            answer[i] = i - map.getOrDefault(ch, i+1); 
            map.put(ch, i); // 마지막으로 발견된 위치 업데이트
        }   
        
        return answer;
    }
}

/*
HashMap의 목적: "이 글자를 마지막으로 본 인덱스"를 기억하는 저장소
map.put(ch,i) -> ch라는 글자는 i라는 인덱스에서 마지막으로 발견됐음을 기록
answer[i] = i - map.getOrDefault(ch, i+1); -> 마지막으로 발견된 위치가 있다면 getOrDefault가 반환하는 인덱스는 i보다 작음. 
i에서 이 값을 빼면 거리가 산출됨. 그 값을 answer에 인덱스 접근하여 넣어줌. 
마지막으로 발견된 위치가 없다면 -1을 넣어줘야 하므로 i에서 빼는 값을 (i+1)로 고정해주면 됨.
*/

 

무엇이 개선되었나

• 모범답안과 동일
  • 주석을 더하여 이해도를 높임
  • import 시 HashMap만 import
• 시간복잡도: 루프가 딱 한 번 돌고, 루프 내 연산(getOrDefault, put)은 모두 HashMap이기 때문에 총 시간복잡도는 O(n).
• 공간복잡도: HashMap에 저장되는 key는 영어 소문자 26개로 고정돼 있으므로 s의 길이에 따라 변화하지 않으므로 O(1)임.

 

 

---

인사이트

 

다양한 기본 자료 구조형을 많이 학습하고, 활용해봐야겠다.
List와 String만 공부했었는데, Map 구조를 통해 복잡도를 획기적으로 개선시킬 수 있음을 깨달았다.

Github 링크 (많은 방문 바랍니다)

[level 1] Title: 가장 가까운 같은 글자, Time: 19.58 ms, Memory: 94.7 MB -Baekj… · ginsengcandy/Coding-Test-Practice@

 

문제 출처

프로그래머스

 

학습 자료 출처

Map (Java Platform SE 8 )