Leetcode 75 day10 (String Compression, Container With Most Water, Reverse Words in a String)

리트코드 75 10일 차, Array / String 2문제, Two pointers 1문제를 풀었다.

443. String Compression

주어진 문자열에서 연속으로 나오는 문자가 있을 때, 길이가 1이면 해당 문자만, 더 길다면 해당 문자 개수를 덧붙여준다. 압축된 문자열은 따로 반환하지 않고 입력 문자 배열에 덮어쓴다. 문자열 길이가 10보다 큰 경우는 길이가 나눠서 저장된다. 반환값은 새로운 배열의 길이를 반환한다. 알고리즘은 상수개의 공간만 사용해야 한다.

Given an array of characters chars, compress it using the following algorithm:
Begin with an empty string s. For each group of consecutive repeating characters in chars:
If the group's length is 1, append the character to s.Otherwise, append the character followed by the group's length.
The compressed string s should not be returned separately, but instead, be stored in the input character array chars. Note that group lengths that are 10 or longer will be split into multiple characters in chars.
After you are done modifying the input array, return the new length of the array.
You must write an algorithm that uses only constant extra space.

현재 카운트하고 있는 문자를 저장할 변수 c, 문자의 개수를 저장할 변수 freq, 그리고 다음 문자열 그룹을 저장할 위치를 저장한 변수 cur을 선언한다. chars 배열을 순회하면서 문자가 c와 같으면 freq를 증가시키고, 다르면 chars 배열에 결과를 저장하고 c를 현재 문자로 갱신한다. 반복문을 나왔을 때 가장 마지막 문자열 그룹의 결과도 저장해줘야 한다.

class Solution {
    public int compress(char[] chars) {
        int cur=0;
        int freq=1;
        char c=chars[cur];
        for(int i=1; i<chars.length; i++) {
            if (c == chars[i]) {
                freq++;
            } else {
                chars[cur] = c;
                cur++;
                if (freq > 1) {
                    String freqStr = Integer.toString(freq);
                    for(int j=0; j<freqStr.length(); j++) {
                        chars[cur+j] = freqStr.charAt(j);
                    }
                    cur += freqStr.length();
                }
                c = chars[i];
                freq = 1;
            }
        }
        chars[cur] = c;
        cur++;
        if (freq > 1) {
            String freqStr = Integer.toString(freq);
            for(int j=0; j<freqStr.length(); j++) {
                chars[cur+j] = freqStr.charAt(j);
            }
            cur += freqStr.length();
        } 

        return cur;
    }
}

문자열 chars 길이를 n이라고 할 때 시간 복잡도는 O(n), 공간 복잡도는 O(1)이다.

11. Container With Most Water

(i, height[i]) 값에 따라 수직 막대기를 그려서 물을 담는 컨테이너를 만든다고 할 때, 가장 많이 담을 수 있는 양을 리턴한다. 컨테이너를 기울이거나 하진 않는다.

You are given an integer array height of length n. There are n vertical lines drawn such that the two endpoints of the ith line are (i, 0) and (i, height[i]).
Find two lines that together with the x-axis form a container, such that the container contains the most water.
Return the maximum amount of water a container can store.
Notice that you may not slant the container.

이 문제는 여러 번 풀어봤음에도 풀이가 잘 기억나지 않는 것 같다. 😂 결국 힌트를 보고 솔루션을 생각해 냈는데 100% 이해하진 못한 것 같다. Two pointers 패턴으로 배열 양 쪽 끝에서부터 컨테이너가 담을 수 있는 물의 양을 계산한다. 여기까진 알겠는데 과연 어떤 식으로 포인터를 이동할 것인가? 가 고민이었다. 힌트는 Always move the pointer that points to the lower line.인데, 높이가 낮은 쪽 좌표를 이동시키는 것이다. 곰곰이 생각하면 height[l], height[r] 중 작은 것을 기준으로 컨테이너가 담을 수 있는 물의 양이 정해지니까 높이가 낮은 쪽 포인터를 안쪽으로 이동시켜야 더 큰 컨테이너가 있을 가능성을 찾을 수 있기 때문인 것 같다.

class Solution {
    public int maxArea(int[] height) {
        int maxArea = 0;
        int l=0, r=height.length-1;
        while(l < r) {
            int area = Math.min(height[l], height[r]) * (r - l);
            maxArea = Math.max(maxArea, area);
            if (height[l] < height[r]) {
                l++;
            } else {
                r--;
            }
        }
        return maxArea;
    }
}

시간 복잡도는 O(n), 공간 복잡도는 O(1)이다.

151. Reverse Words in a String

단어들의 순서를 뒤집은 문자열을 리턴한다. '단어(word)'의 정의는 공백이 아닌 문자 시퀀스로 정의한다. 단어들은 최소 1개의 공백으로 나눠진다. 반환할 문자열은 단어들이 딱 1개의 공백문자로 구분되어야 한다.

Given an input string s, reverse the order of the words.
A word is defined as a sequence of non-space characters. The words in s will be separated by at least one space.
Return a string of the words in reverse order concatenated by a single space.
Note that s may contain leading or trailing spaces or multiple spaces between two words. The returned string should only have a single space separating the words. Do not include any extra spaces.

문자열을 공백 문자로 스플릿 후 StringBuilder에 뒤에서부터 append 해준다. split(" ")을 사용하면 스플릿 된 문자열 중에 빈 문자열이 들어갈 수 있다. split() 함수는 정규식을 사용할 수 있기 때문에 split("\\s+")를 호출하면 공백 문자가 여러 개 나오는 경우에도 단어들만 뽑아낼 수 있다.

코틀린이라면  s.trim().split("\\s+".toRegex()).reversed().joinToString(" ") 1라인으로 가능한 문제다. 😅

class Solution {
    public String reverseWords(String s) {
        String[] words = s.trim().split("\\s+");
        StringBuilder sb = new StringBuilder();
        for(int i=words.length-1; i>=0; i--) {
            sb.append(words[i]);
            sb.append(" ");
        }
        sb.deleteCharAt(sb.length()-1);
        return sb.toString();
    }
}

시간복잡도 O(n), 공간복잡도 O(n).