[프로그래머스] 압축

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

프로그래머스

코드

package Programmers.Level2;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedHashMap;
import java.util.List;
import java.util.Map;

public class Compress2 {

	public static void main(String[] args) {

		String msg = "TOBEORNOTTOBEORTOBEORNOT";

		int[] result = solution(msg);

		System.out.println(Arrays.toString(result));
	}

	public static int[] solution(String msg) {

		String[] msgArr = msg.split("");

		Map<String,Integer> addMsg = new LinkedHashMap<String,Integer>();
		List<Integer> result = new ArrayList<Integer>();

		int addIndex = 27;

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

			if ( i == msgArr.length-1 ) result.add(msg.charAt(i)-64);

			else {
				String word = msgArr[i]+msgArr[i+1];

				// 문자열 길이가 3이상인 대상은 해당조건에 탈 수 없다.
				if ( addMsg.get(word)==null ) {
					result.add(msg.charAt(i)-64);
					addMsg.put(word,addIndex++);
				}else {

					i+=2;

					String w = "";
					String c = "";

					while( i < msgArr.length && addMsg.get(word) != null ) {
						w = word;
						c = msgArr[i++];
						word  = w+c;
					}

					// loop에서 +1되서넘어오고, for문에의해 +1됨으로 -2해줌.
					i-=2;

					if( i == msgArr.length-2 && addMsg.get(word) != null){
						result.add(addMsg.get(word));
						break;
					}else{
						result.add(addMsg.get(w));
						addMsg.put(word, addIndex++);
					}
				}
			}
		}

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

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

		return answer;
	}

}

제출 결과

나의 풀이

풀릴 듯.. 안 풀려서 상당히 많은 시간을 소요했다...ㅠㅠㅠㅠ

 

문법적으로 어려운 문제는 아니지만, 의사 코드를 정확하게 코드로 풀어내는 게 관건이었던 것 같다... 그렇기 위해서는 문제를 정확히 이해해야 되겠다..

 

문제를 보면 주어진 msg를 압축하여, 사전 색인 번호를 배열로 출력하면 된다.

 

먼저, 예시처럼 KAKAO로 주어진 경우를 보자.

 

나는 아래와 같이 풀어나갔다.

 

최초 0번째 K와 1번째 A를 합친다.

 

합쳐진 문자열 KA가 사전(map) 에있는지 확인한다.

 

사전(map)에없으므로 이전 글자 K의 색인 번호를 List에 add 하고, KA를 사전(map)에 넣어준다.(put)

 

다음은 1번째 A와 2번째 K를 합친다.

 

AK도 없으니, 이전 글자를 add 하고, 사전(map)에 put 해준다.

 

다음은 2번째 K와 3번째 A를 합친다.

 

KA는 사전(map)에 존재함으로 4번째 글자 O를 추가로 붙여서 사전에 있는지 확인한다.

 

이때, 3글자 이상의 문자열은 이후에 누적되어 나타날 수 있기 때문에, 다음 index의 문자를 추가해 합쳐진 문자열이 사전에 없을 때까지 확인한다.

( 2글자가 map에 존재하지 않으면 3글자는 존재할 수 없다. 즉, KA 없이는 KAO가 들어올 수 없다. )

 

KAO는 사전에 존재하지 않음으로, KAO를 사전에 추가해준다.

 

그리고 이전 색인 번호(KA의 색인 번호)를 List에 add 해준다.

 

그리고 사전에 존재하는 경우에는 색인 번호에 해당하는 문자열이 2글자 이상이므로, 원본 msg의 index도 같이 늘려주어야 한다.

KAO가 사전에 추가된 시점의 현재 입력은 KA가 된다. ( 사전에 있는 문자열 )

 

고로, KAKA까지 봤으므로 남은 O를 처리해주어야 한다. ( 고로 다음 처리될 index는 4가 된다. )

 

이경우와 같이 마지막 문자가 1글자인 경우 ( i == msg.length-1 )에는 마지막 문자열을 색인 번호에 추가해주면 된다.

( 삽질했던 조건 1.. )

 

추가적으로 고려할 사항은 아래와 같다.

 

모든 문자열을 검사하였을 때, 마지막 단어가 사전에 존재하는지를 확인하는 것이다.

 

주어진 msg를 전부 확인하였을 때, 마지막 단어가 사전에 존재한다면, 해당 단어의 색인 번호를 List에 add 해주고 종료시키면 된다. ( 삽질했던 조건 2.. )

 

아직도 index가 어디를 가리키고 있는지 계속 헷갈리는 것 같다 ㅠㅠ.. i++했다가, ++i 했다가.. 종료된 index가 몇인지 여러 번 예상을 벗어났다... 좀 더 집중해서 풀어야겠다..