2023-04-21 문자열 압축

Summary

처음에 시행착오로 깔끔하게 작성하지 못한 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

import java.util.*;

class Solution {
	public int solution(String s) {
		int ans = Integer.MAX_VALUE;
		if (s.length() == 1) return 1;
		for (int k=1; k<=s.length() / 2; k++) {
			StringBuilder builder = new StringBuilder();
			int cnt = 1;
			String prev = s.substring(0, k);
			boolean lastMatched = true;
			for (int i=k; i<s.length(); i += k) {
				if (i+k-1 >= s.length()) {
					String rest = s.substring(i, s.length());
					if (rest.equals(prev)) {
						cnt += 1;
					} else {
						if (cnt == 1) builder.append(prev + rest);
						else builder.append(String.valueOf(cnt) + prev + rest);
						lastMatched = false;
					}
					break;
				}

				String cur = s.substring(i, i+k);
				if (cur.equals(prev)) {
					cnt += 1;
				} else {
					if (cnt != 1) builder.append(String.valueOf(cnt) + prev);
					else builder.append(prev);
					cnt = 1;
					prev = cur;
				}
			}

			if (lastMatched) {
				if (cnt == 1) builder.append(prev);
				else builder.append(String.valueOf(cnt) + prev);
			}

			String res = builder.toString();
			ans = Math.min(ans, res.length());
		}

		return ans;

	}
}

예전에 풀었던 python 코드를 보고 수정한 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

import java.util.*;

class Solution {
    public int solution(String s) {
        int ans = Integer.MAX_VALUE;
        if (s.length() == 1) return 1;
        for (int k=1; k<=s.length() / 2; k++) {
            StringBuilder builder = new StringBuilder();
            int cnt = 1;
            String prev = s.substring(0, k);
            for (int i=k; i<s.length(); i += k) {
                String cur;
                if (i+k-1 >= s.length()) cur = s.substring(i, s.length());
                else cur = s.substring(i, i+k);
                
                if (cur.equals(prev)) {
                    cnt += 1;
                } else {
                    if (cnt != 1) builder.append(String.valueOf(cnt) + prev);
                    else builder.append(prev);
                    cnt = 1;
                    prev = cur;
                }
            }
            
            if (cnt == 1) builder.append(prev);
            else builder.append(String.valueOf(cnt) + prev);
            
            String res = builder.toString();
            ans = Math.min(ans, res.length());
        }
        
        return ans;
        
    }
}

파이썬과 Java 의 list slicing 과 substring

파이썬에서 list slicing 이 동작할 때 list 의 범위를 벗어나는 값에 대해 slicing 한다면 어떻게 동작할까?

예를 들어

1
2

a = "012345"
print(a[4:10])

를 생각해보자.

이 경우에 파이썬은 runtime error 를 발생시키지 않고 “45” 를 출력한다.

Java 는 어떨까?

1
2

String a = "12345";
String substr = a.substring(4, 10);

인덱스 에러가 난다. 어떻게 보면 너무 당연한거 아닌가 라는 생각이 들 수 있지만, 나의 경우 알고리즘 문제는 파이썬으로 푸는 것이 너무 익숙해져서 문제를 풀 때 컴파일 에러, 런타임 에러를 여러번 만나다보니 문제를 푸는 데에 차분히 생각하는 여유가 부족해지는 느낌을 받았다.

기초를 위한 문제들의 난이도를 점진적으로 올려가면서 하루 빨리 익숙해져서 Java 로 문제를 푼다고 하더라도 큰 어려움이 없도록 만들어야겠다.

그럼에도 불구하고 논리적으로 했어야 할 다음 사고 과정은

첫번째로는, 문자열 s 에 대해 순회할 때 인덱스가 마지막에 다다르는 지점에서 논리적인 사고가 부족했다. 인덱스가 마지막에 도달했을 때, Java 를 이용한 인덱스 처리에 익숙하지 못했다고 하더라도 이 때 도달했어야 할 다음 사고는

  1. 마지막 문자열까지 받아올 방법을 찾고 (인덱스 에러 없이)
  2. 받아온 문자열과 prev 이 같거나, 다른 경우 두 가지로 나눠서 생각하면

일관된 로직으로 문제를 풀 수 있다는 점을 떠올리는 것이었다고 본다.

comments powered by Disqus