동적 프로그래밍 - 예제

1번째 문제 

https://leetcode.com/problems/unique-morse-code-words/

 

알파벳에 해당되는 모스 부호가 있고,

특정 단어가 인풋으로 들어오면 해당 단어를 모스부호로 변경을 한 후 ,

중복되지 않은 문자가 몇개인지 return 시키는 문제다.

 

    public int uniqueMorseRepresentations(String[] words) {
        List<String> morse = List.of(".-","-...","-.-.","-..",".","..-.","--.","....","..",".---","-.-",".-..","--","-.","---",".--.","--.-",".-.","...","-","..-","...-",".--","-..-","-.--","--..");
        List<String> alphabet = List.of("a","b","c","d","e","f","g","h","i","j","k","l","m","n","o","p","q","r","s","t","u","v","w","x","y","z");
        List<String> results = new ArrayList<>();
        
        for (String word : words) {
            String convert = "";
            
            for (int i = 0; i < word.length(); i++) {
                int position = 0;
                
                for (int j = 0; j < alphabet.size(); j++) {
                    if (alphabet.get(j).charAt(0) == word.charAt(i)) {
                        position = j;
                    }
                }
                
                convert += morse.get(position);
            }
            
            boolean flag = false;
            
            for (String result : results) {
                if (result.equals(convert)) {
                    flag = true;
                }
            }
            
            if (!flag) {
                results.add(convert);
            }
        }
        

        return results.size();
    }

 

처음 문제 푼 논리

 

DP 의 바텀업 방식으로 푼 거라 볼 수 있다.

단어의 가장 처음 단어부터 끝까지 for 문을 돌면서,

알파벳의 순서를 position 으로 저장을 하고 (ex, a=0, b=1...)

해당되는 모스 부호를 얻어서 단어에 해당하는 모스부호를 얻고,

 

List 에 중복이 없는지 확인 후 결과를 저장해서 size 를 확인했는데, 너무 불필요한 로직들이 많았다.

 

다른 사람 코드

내가 불필요하게 for문을 돌면서 position 을 찾은걸 - 'a' 로 찾아줬고,

쓸데없는 중복 체크를 HashSet 을 사용해서 중복을 없애고 저장을 했다.

 

class Solution {
    public int uniqueMorseRepresentations(String[] words) {
        String[] MORSE = new String[]{".-","-...","-.-.","-..",".","..-.","--.",
                         "....","..",".---","-.-",".-..","--","-.",
                         "---",".--.","--.-",".-.","...","-","..-",
                         "...-",".--","-..-","-.--","--.."};

        Set<String> seen = new HashSet();
        for (String word: words) {
            StringBuilder code = new StringBuilder();
            for (char c: word.toCharArray())
                code.append(MORSE[c - 'a']);
            seen.add(code.toString());
        }

        return seen.size();
    }
}

 

사용된 자료구조

 

HashSet

HashSet 의 특징. 순서가 보장되지 않고 중복을 허용하지 않는다. null도 포함시킴.

 

객체를 저장하기 전에 hashCode 를 얻어서 안에 있는 객체를 비교해서 true 가 나오면 동일한 객체로 판단 후 중복 저장을 하지 않는다.

String 클래스는 equals(),hashCode() 메소드가 값이 같은 문자열의 경우 true 가 나오게 설정이 되어있기 때문에 

String 비교가 가능했다.

 

 

2번째 문제 

https://leetcode.com/problems/climbing-stairs/

 

계단오르기 문제

1칸 또는 2칸을 갈 수 있다.

n 번째 계단까지 갈때 갈수있는 경우의 수는?

 

    public int climbStairs(int n) {
        int result = 0;
        int [][]te = new int[n + 1][2];
        // n-1 에서 +1 가는 방법 수 + n-2 에서 가는 방법 수

        
        for (int i = 1; i <= n; i++) {
            
            if (i == 1) {
                te[i][0] = 1;
            }
            
            if (i == 2) {
                te[i][1] = 1;
            }
            
            if (i > 1) {
                System.out.println("1");
                te[i][0] = te[i-1][0] + te[i-1][1];        
            } 
            
            
            if (i > 2) {
                 System.out.println("2");
               te[i][1] = te[i-2][0] + te[i-2][1];
            } 
        
            
            result = (te[i][0]) + (te[i][1]);
        }
        
        
    
        return result;
    }

 

처음 푼 논리

2차 배열을 이용했음

n번째에 도착했을때 1발자국 움직여서 갔는지 2발자국 움직여서 갔는지를 나눠서 저장했다.

 

다른 사람 코드

    public int climbStairs(int n) {
        if (n <= 1) {
            return 1;
        }
        
        int[] dp = new int[n + 1];
        dp[1] = 1;
        dp[2] = 2;

        for (int i = 3; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }

        return dp[n];
    }

 

1차 배열만으로도 충분했는듯.

recursion 으로도 가능한거같은데 난 바텀업 방식으로 푸는게 편한거같다.

 

3번째 문제

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

 

파스칼 트라이앵글 문제,

이렇게 더한 문제

    public List<List<Integer>> generate(int numRows) {
        
        int [][]triangle = new int[numRows + 1][numRows + 1]; 
        List<List<Integer>> result = new ArrayList<>();
        
        for (int i = 1; i <= numRows; i++) {
            List<Integer> rowResult = new ArrayList<>();
            
            for (int j = 1; j <= i; j++) {
                if (j == 1 || j == i) {
                    triangle[i][j] = 1;
                    rowResult.add(1);
                } else {
                    int temp = 0;
                    
                    if (i >= 3) {
                        temp = triangle[i - 1][j - 1] + triangle[i - 1][j];
  
                        triangle[i][j] = temp;
                        rowResult.add(temp);
                    } 
                }
            }
            result.add(rowResult);
        }
        
        return result;
    }

int 배열을 따로 뒀었는데 이건 별로같음

result 에서 get() 하는게 좋았다.

 

 

 

4번째 문제

맥시멈 프로핏 문제

가장 낮은곳에서 사서 가장 비싼곳에서 판다.

https://leetcode.com/problems/best-time-to-buy-and-sell-stock/

 

 

        int result = 0;
        
        for (int i = 0; i < prices.length; i++) {
            
            for (int j = 0; j < i; j++) {
                
                if (prices[j] < prices[i]) {
                    int diff = prices[i] - prices[j];

                    if (result < diff) {
                        result = diff;
                    }
                }
            }
        }
        return result;

처음 푼 논리

비교했을때 가장 낮은걸 찾아야 하니까 2중 포문을 생각했었는데,

타임아웃.

 

        int result = 0;
        int min =prices[0];

        
        for (int i = 0; i < prices.length; i++) {
            if (prices[i] < min) {
                min = prices[i];
            }
            
            int diff = prices[i] - min;
            
            if (result < diff) {
                result = diff;
            }
            
        }
        return result;

돌면서 가장 낮은 값만 찾으면 되니까

포문을 한번만 돌면서 가장 낮은 값을 저장해주고 diff 를 비교 후 result 가 큰것만 저장해주면 됐다.

최적화 문제.