(3차) 압축

작성일: 2024-11-12

문제 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/17684

접근 방식

HashMap 자료구조를 이용해 먼저 A~Z까지를 사전에 입력해 둔다.

그리고 처리해야 할 문자를 한 문자씩 Queue 자료구조에 넣는다.

Queue의 모든 문자를 처리할 때 까지 while문을 돌리는데, 이 과정에서 현재 문자가 사전에 존재하는지 체크하고, 존재한다면, 다음, 그 다음.. 이렇게 하나씩 추가하며 사전에 존재하는지를 확인한다.

추가된 문자열이 사전에 존재하지 않을 때 까지 문자를 추가하고, 존재하지 않는 경우가 발생한다면 해당 문자열을 사전에 추가하고, 바로 이전까지의 색인 번호를 배열에 담는다.

결과

소스 코드

import java.util.*;

class Solution {
    public int[] solution(String msg) {
        List<Integer> list = new ArrayList<>();
        Queue<String> q = new LinkedList<>();
        for(char m:msg.toCharArray()) q.offer(String.valueOf(m)); // 처리해야 할 문자 추가
        Map<String, Integer> map = new HashMap<>();
        int cnt = 1;
        // 사전 생성
        for(int i=65; i<=90; i++){
            map.put(String.valueOf((char)i), cnt++);
        }
        // 처리해야 할 문자가 남아있다면
        while(!q.isEmpty()){
            String tmp = q.poll();
            int idx = map.get(tmp); // 사전에서 색인 번호 가져오기
            tmp+=q.peek(); // 다음 문자도 가져오기
            int idx2 = map.getOrDefault(tmp, -1); // 다음 문자 색인 번호 가져오기
            // 만약 사전에 없는 문자라면
            if(idx2==-1){
                map.put(tmp, map.size()+1); // 사전에 추가
                list.add(idx); // 기존 색인 번호 추가
            }
            // 사전에 있다면
            else{
                while(true){
                    q.poll(); // 문자 처리
                    tmp+=q.peek();
                    idx = map.getOrDefault(tmp, -1);
                    if(idx==-1){
                        map.put(tmp, map.size()+1); // 그다음 문자 없으면 사전에 추가
                        list.add(idx2);
                        break;
                    }
                    idx2 = idx;
                }
            }
        }
        return list.stream().mapToInt(a->a).toArray();
    }
}

개선 사항

현재 코드에는 중복된 코드가 존재한다.

현재 문자가 존재하는지 여부를 판단하고, 추가하는 과정의 코드가 중복된다.

그리고 계속 while문을 순회하며 한 문자씩 비교하기 때문에 의도치 않은 연산을 발생시킬 수 있다.

따라서, 아래의 두 가지를 개선할 수 있다.

- 존재 여부 판단 및 추가 코드 통합
- 한 번에 계산 가능한 문자열 찾기

import java.util.*;
class Solution {
    public int[] solution(String msg) {
        // 결과를 담을 List 선언
        List<Integer> list = new ArrayList<>();

        // 사전을 표현할 Map 선언
        Map<String, Integer> map = new HashMap<>();

        // 사전의 다음 번호를 표현할 변수
        int cnt = 1;

        // 초기 사전 생성 (A-Z)
        for(int i=65; i<=90; i++){
            map.put(String.valueOf((char)i), cnt++);
        }

        // 입력 문자열 처리를 위한 변수
        int idx = 0;
        int size = 27;

        // 입력 문자열 처리 루프
        while(idx<msg.length()){
            int target = 1;

            // 사전에 없는 가장 긴 문자열 찾기
            while(idx+target<=msg.length() && map.containsKey(msg.substring(idx, idx+target))){
                target++;
            }

            // 이전 번호 추가
            list.add(map.get(msg.substring(idx, idx+target-1)));

            if(idx+target>msg.length()) break;
            map.put(msg.substring(idx, idx+target), size++);

            // 처리한 문자열 길이만큼 인덱스 이동
            idx += target-1;
        }

        // List를 int[]로 변환하여 반환
        return list.stream().mapToInt(a->a).toArray();
    }
}

접근 방식은 유지되지만, 전체 로직이 변경되었다.

먼저, 사전에서 찾는 방식을 containsKey로 변경하였다. (시간 복잡도는 동일하게 O(1))
substring을 통해 사전에 등재 여부를 판단하는데, 같을 경우 범위를 계속 늘려간다.
다만, 최대 범위가 msg의 길이를 벗어나지 않도록 설정한다.

이후, 이전 번호를 리스트에 추가한다. (존재하지 않는 문자열을 찾았기 때문에)

만약, idx + target이 msg의 길이를 벗어난다면 while문을 종료시킨다.
왜냐하면, 벗어난다는 의미는 처리할 수 없는 문자열을 의미하기 때문이다. (처리해야 할 마지막 문자임을 의미)

이후에는 처리가능한 상태이기에, 사전에 존재하지 않는 문자열을 추가하고
인덱스의 시작 위치를 변경한다.

다른 접근 방식

비슷한 방식이지만, 리스트로 구현한 케이스가 있었다.

import java.util.ArrayList;

class Solution {
  public int[] solution(String msg) {
    ArrayList<String> dic = new ArrayList<String>();
    ArrayList<Integer> result = new ArrayList<Integer>();

    for(int i = 0 ; i < 26; i++) {
        dic.add(String.valueOf((char)('A'+i)));
    }

    for(int i = 0 ; i < msg.length() ; i++) {
        for(int j = dic.size()-1 ; j >= 0 ; j--) {
            if(msg.substring(i).startsWith(dic.get(j))) {
                i += dic.get(j).length()-1;
                result.add(j+1);
                if(i+1 < msg.length())
                    dic.add(dic.get(j)+msg.charAt(i+1));
                break;
            }
        }
    }

    int[] answer = new int[result.size()];

    for(int i = 0 ; i < result.size() ; i++)
        answer[i] = result.get(i);

    return answer;
  }
}

먼저, 문자열의 길이만큼 반복문을 실행시킨다. (모든 문자열 처리를 위해)

이후, 사전의 역순으로 문자열을 처리한다.
이 과정에서 중요한 점이 있는데, 인덱스에 해당하는 i가 사전에 있는 문자인지를 확인하는 점이다.
만약 사전에 있다면, 해당하는 문자열의 길이만큼 인덱스를 추가하고 리스트에 값을 추가한다.
그리고 현재문자열에서 +1을 했을 때 msg의 길이를 벗어나지 않는다면 해당 문자를 사전에 등재하고 현재 인덱스의 압축을 종료한다.

이 로직의 핵심은 백트래킹이다. 백트래킹을 통해 쓸모 없는 연산을 줄이고 (어차피 한 문자열씩 확인할 텐데, A~Z까지는 이미 사전에 등록되어 있기 때문에)
바로 문자열 추가를 함으로서, 연산 횟수를 줄였다.

느낀 점

항상 백트래킹과 연산 횟수를 줄이는 것이 중요하다는 것을 문제를 다 풀고나서 느끼지만

여전히 감이 오지는 않는 것 같다.

문제를 많이 풀어봐야겠다.. 😥😥