[Day5/15] LeetCode 75

Level 1 : day 5

오늘은 LeetCode 75 Level 1 을 시작한지 5일차다.

오늘의 주제는 Greedy 이다.

This study plan is for those who want to prepare for technical interviews but are uncertain which problems they should focus on. The problems have been carefully curated so that levels 1 and 2 will guide beginner and intermediate users through problems that cover the data structures and algorithms necessary to succeed in interviews with most mid-tier companies. While level 3 provides material to help users whose targets are top-tier companies.

121. Best Time to Buy and Sell Stock (문제링크)

주어진 정수형 배열 prices 은 주식 가격을 나타내고, 최저가에서 구매해 최고가에 판매했을 때의 수익을 반환하는 문제이다. 만약 수익을 낼 수 없다면 0을 반환해야한다.

제한사항

$1$ $<=$ prices.length $<=$ $10^5$

풀이과정

제한사항에서 확인 할 수 있다싶이 $O(n^2)$ 로 푼다면 TLE 가 뜬다.
따라서, 한 번의 iterative 을 통하여 최저가를 갱신해 나가면서 maxProfit 을 계산해주면 된다.

이렇게 할 경우 시간복잡도는 $O(n)$ 이 된다.

Java Solution

class Solution {
    public int maxProfit(int[] prices) {
        int n = prices.length;
        
        if (n == 1) return 0;
        
        int min = prices[0];
        int maxProfit = 0;
        for (int i = 1; i < n; i++) {
            min = Math.min(min, prices[i]);
            
            maxProfit = Math.max(maxProfit, prices[i] - min);
        }
        
        return maxProfit;
    }
}

409. Longest Palindrome (문제링크)

주어진 문자열 s을 이용하여 만들 수 있는 가장 긴 palindrome의 길이를 반환하는 문제다.

예시)
s = "aabbbccccd"
paldinrome = "abccdccba" or "abccbccba" 으로서 9 이다

풀이과정

우리는 palindrome 의 길이만 알면 되기 때문에, palindrome 의 성질만 알면 쉽게 풀 수 있다.

1. 해당 알파벳이 짝수개 있으면 다 쓸 수 있다.

2. 해당 알파벳이 소수개 있으면 하나를 빼고 쓸 수 있다. (소수 - 1 = 짝수)

3. Palindrome 의 정중앙은 1개 알파벳을 쓸 수 있다.
   a. 단, 주어진 문자열을 1,2 번에서 모두 사용했을 경우 불가능.

Java Solution

class Solution {
    public int longestPalindrome(String s) {
        int n = s.length();
        
        if (n == 1) return 1;

        HashMap<Character, Integer> map = new HashMap<>();
        
        for (int i = 0; i < n; i++) {
            if (map.containsKey(s.charAt(i))) map.put(s.charAt(i), map.get(s.charAt(i)) + 1);
            else map.put(s.charAt(i), 1);
        }
        
        int cnt = 0;
        
        for (Integer value : map.values()) {
            if (value % 2 == 0) cnt += value;
            else cnt += (value-1);
        }
        
        return (cnt < n) ? cnt + 1 : cnt;
    } 
}

Greedy 은 아무리 많이 풀어도 잘 안 풀리는 분야라서 (그리디보다 그래프를 훨씬 좋아함) Easy 여도 조금 헤맸던 것 같다 ㅠㅠ.