TIL (2024.06.08)

문제 1️⃣ (리트 코드_모음 문자열 정렬)

https://leetcode.com/problems/count-sorted-vowel-strings/description/

💡 IDEA : 규칙성을 파악한다.

[a, e, i, o, u]
-> a(1) e(1) i(1) o(1) u(1) = 5

[aa, ae, ai, ao, au, ee, ei, eo, eu, ii, io, iu, oo, ou, uu]
-> a(5) + e(4) + i(3) + o(2) + u(1) = 15

[aaa, aae, aai, aao, aau, aee, aei, aeo, aeu, ali, ...]
-> a (15) + e(10) + i(6) + o(3) + u(1) = 35

풀이 (1)

➡️ 앞에서부터 갱신하는 방식. 앞의 줄의 합을 a의 값에 넣고 나머지는 전의 값에서 하나씩 빼면 된다는 규칙성을 생각했었다.

class Solution {
    public int countVowelStrings(int n) {
        List<Integer>[] answer = new List[n+1];

        // ArrayList 생성
        for (int i=0; i<=n; i++) {
            answer[i] = new ArrayList<>();
        }

        // 첫째줄 초기화
        for (int i=1; i<=5; i++) {
            answer[1].add(1);
        }

        for (int i=2; i<=n; i++) {
            for (int j=1; j<=5; j++) {
                if (j==1) {
                    int sum = answer[i-1].stream().mapToInt(Integer::intValue).sum();
                    answer[i].add(sum);
                    continue;
                }

                answer[i].add(answer[i].get(j-2) - answer[i-1].get(j-2));
            }
        }

        return answer[n].stream().mapToInt(Integer::intValue).sum();
    }
}

해당 방식은 규칙성은 맞으나 굳이 ArrayList 를 통해 모든 값을 저장하려고 했다는 점과 비효율적인 규칙성이라는 점에서 시간이 O(n2) 이고 메모리 차지가 많이 생길 수 있는 코드이다.

풀이 (2)

➡️ 뒤에서 부터 갱신하는 방식, 구하고자하는 위치 (j) 의 값과 전 차례에서의 구하고자 하는 값 다음값 (j+1) 의 합이 해당 위치 (j) 의 값이라는 규칙성을 활용.

class Solution {
    public int countVowelStrings(int n) {
        int[] strs = new int[] {1,1,1,1,1};

        for (int i=1; i<n; i++) {
            for (int j=3; j>=0; j--) {
                strs[j] += strs[j+1];
            }
        }

        int answer = 0;

        for (int num : strs) {
            answer += num;
        }

        return answer;
    }
}

크기가 5인 배열을 사용함으로서 메모리 사용량을 줄였다. 시간은 O(n2) 으로 거의 동일할 것 같다.

 

문제 2️⃣ (리트 코드_파스칼 삼각형)

https://leetcode.com/problems/pascals-triangle/description/

💡 IDEA : 규칙대로 성실하게 코드로 옮긴다.

class Solution {
    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> answer = new ArrayList<>();

        List<Integer> row;
        int sum = 0;

        for (int i=1; i<= numRows; i++) { // numRows 만큼의 줄을 생성해야함
            row = new ArrayList<>();
            
            for (int j=1; j<=i; j++) { // numRows 개 만큼의 원소 생성 필요
                if (j==1 || j==i) { // 처음과 끝은 무조건 1
                    row.add(1);
                    // System.out.printf("%d 줄에 1 추가\n", i);
                    continue;
                }

                sum = answer.get(i-2).get(j-2) + answer.get(i-2).get(j-1);
                row.add(sum);
                // System.out.printf("%d 줄에 %d 추가\n", i, sum);
            }
            answer.add(row);
            // System.out.println("종료");
        }
        return answer;
    }
}

 

➡️ 주어진 규칙성에 맞춰 리스트에 계속해서 값을 추가했다. 다만 처음과 끝은 무조건 1 이므로 해당 부분은 if 문을 통해 해결하였다.

문제 3️⃣ (프로그래머스_정수 삼각형)

https://school.programmers.co.kr/learn/courses/30/lessons/43105

프로그래머스

💡 IDEA : 앞서 푼 두 문제에서 Math.max() 의 개념을 추가할 뿐이지, 작동과정은 거의 동일.

class Solution {
    public int solution(int[][] triangle) {
        int N = triangle.length;
        
        for (int i=1; i<N; i++) {
            for (int j=0; j<=i; j++) {
                // (1) 양끝에 해당할 경우
                if (j == 0) { // (1)-1 첫번째
                    triangle[i][j] += triangle[i-1][0];
                    continue;
                }
                else if(j == i) { // (1)-2 마지막
                    triangle[i][j] += triangle[i-1][j-1];
                    continue;
                }
                
                // (2) 나머지 중간값 처리
                triangle[i][j] += Math.max(triangle[i-1][j-1], triangle[i-1][j]);
            }
        }
        
        // (3) Max 값 확인 후 반환
        int max = -1;
        
        for (int num : triangle[N-1]) {
            max = Math.max(num, max);
        }
        return max;
    }
}

 

➕ 추가로 확인해보면 좋은 문제

➡️ 이 세문제를 풀면서 과거에 풀었던 비슷한 유형의 문제이지만 좀 더 생각이 필요한 문제가 떠올라 해당 문제 링크를 올려둡니다! 혹시 이 세문제를 풀고 자신감이 생겼다면 이 문제도 풀어보는 것을 추천 ❤️

문제 1 (https://school.programmers.co.kr/learn/courses/30/lessons/12913)

프로그래머스

문제 2 (https://www.acmicpc.net/problem/1149)