[문제풀이] 압축

업데이트:

2018 Kakao Blind Recruitment 기출 문제

문제 링크 : 압축

풀이 시간 : 20분

1. 문제 풀이

문제에서 제시된 LZW 압축 알고리즘 구현

1) HashMap을 이용하여 사전을 구현

2) “현재 입력 + 다음 글자”가 사전에 있는지 판별

3-1) 사전에 있을 경우

- 현재 입력을 다음 글자까지 포함하고 2번으로

3-2) 사전에 없을 경우

​ - 현재 입력의 사전 값을 arr에 따로 저장

​ - “현재 입력 + 다음 글자”을 사전에 저장

4) 문자열 끝까지 가면 종료

2. 소스 코드

static public int[] solution(String msg) {
    int[] answer;
    // 출력값 리스트
    LinkedList<Integer> arr = new LinkedList<Integer>();
    // 사전
    HashMap<String, Integer> hm = new HashMap<String, Integer>();
    char c = 'A';
    // A ~ Z까지 기본 사전 만들기
    for (int i = 1; i <=26; i++) {        						
		hm.put(c+"", i);
		c++;
	}
    int num = 27;
    for (int i = 0; i < msg.length(); i++) {
		for (int j = 1; ; j++) {					
			// 문자열 끝까지 갔을 때
			if(i+j>msg.length()) {
				// 마지막 출력 값 저장
				arr.add(hm.get(msg.substring(i, i+j-1)));	
				i=i+j-2;									
				break;
			}
			// 현재 입력 + 다음 글자
			String temp = msg.substring(i,i+j);			
			if(!hm.containsKey(temp)) {					
				// 출력 값 저장
				arr.add(hm.get(msg.substring(i, i+j-1)));
				// 현재 입력 + 다음 글자 사전에 저장
				hm.put(temp, num);		
				num++;
				i=i+j-2;
				break;
			}
		}
	}
    // return 형식 int[]
    answer = new int[arr.size()];
    // 출력 값을 배열에 저장
    for (int i = 0; i < answer.length; i++) {	
		answer[i] = arr.poll();
	}
    return answer;
}

`` 3. 후기

영상처리 수업에서 구현해봤기 때문에 쉬웠다.

참고