[코딩테스트] 프로그래머스 - [3차] 압축(Java)

🎢 설명

레벨: 2
언어: 자바(Java)

🎫 느낀점

해당 문제는 알고리즘 문제라기보단 적절한 자료구조를 이용하면 풀수 있는문제입니다..
간단하지는 않으니 레벨2로 분류된듯 싶습니다.

저의 풀이방법을 대해 설명드리면
1. 순차적이며 필요할때는 다음단어를 꺼내쓰기위해 단어들 queue에 저장
2. 사전역할을 할 list 변수 stream으로 초기화
3. 결과값 담아서 나중에는 배열로 변경할 list 변수
4. queue에 있는 것과 현재 지금 확인중인 단어가 비어있는지 여부로 루프
5. 해당하는 값이 사전에 있다면 다음단어 포함시켜서 확인시도
6. 해당하는 값이 없다면 현재값에 다음단어 포함시켜서 사전등록 및 인덱스값 저장

이런식으로 풀었습니다

1. 사전변수 역할 dic과 결과 result 선언 및 초기화
2. A ~ Z까지 dic변수에 값 추가
3. msg 순차적인 루프와 dic 역 루프 조회를 하는데
4. msg 순차적으로 돌때 현재 인덱스 이후의 문자열값에서 최근 사전에 등록된 단어 순을 기준으로 앞자리부분이 같은 경우가 있는지 먼저 확인 (제가 작성한 코드보다 시간복잡도가 더 좋게 나올듯 싶습니다)
5. 현재 사전에서 구한값길이 -1을 변수에 대입 및 결과 인덱스값을 추가
6. 사전에서 구한값길이 더한거랑 msg 길이를 비교하는데 (이게 마지막단어가 사전에 안들어가는 경우를 계산하기 위해서인듯?)
7. 나머지는 배열로 변환해서 반환

공간복잡도, 시간복잡도 면에서는 좋아요 많이 받은 코드가 더 나은듯 싶습니다!

🥿 내가 작성한 코드

import java.util.*;
import java.util.stream.*;

class Solution {
    
    public int[] solution(String msg) {
        
        Queue<String> queue = new LinkedList<>();
        
        for(String word: msg.split("")) {
            queue.offer(word);
        }
        
        List<String> list = IntStream.range('A', 'Z'+1)
            .mapToObj(val -> String.valueOf((char) val))
            .collect(Collectors.toList());
        
        List<Integer> result = new ArrayList<>();
        
        String value = "";
        while(!queue.isEmpty() || !"".equals(value)) {
            if(list.contains(value + queue.peek())) {   
                value = value + queue.poll();
                continue;
            }
            
            list.add(value+queue.peek());
            result.add(list.indexOf(value)+1);
            value = "";
        }
        
        
        return result.stream()
            .mapToInt(val -> val.intValue())
            .toArray();
    }
}

🏀 가장 좋아요 많이 받은 코드

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;  
  }
}