DEV Community

loading...

[DataStructure&Algorithm] 1. Greedy

Nina Hwang
πŸ‘©πŸ»β€πŸ’» ν™©μ±„μ˜ 🐣 Junior Backend Developer
・Updated on ・3 min read

1. Greedy Algorithms

Greedy algorithm is an algorithm that makes the optimal choice at each step. Since it only makes decisions based on the information it has at each step and does not care about the overall information, it may not produce an optimal solution.

2. Problem Solutions

Good or Bad string

# python

class Solution:
    def isGoodorBad(self, S):
        vowels = ['a', 'e', 'i', 'o', 'u']
        vowel_cnt, consonant_cnt = 0, 0

        for char in S:
            if char == '?':
                vowel_cnt += 1
                consonant_cnt += 1
            elif char in vowels:
                vowel_cnt += 1
                consonant_cnt = 0
            else:
                vowel_cnt = 0
                consonant_cnt += 1

            if vowel_cnt > 5 or consonant_cnt > 3:
                return 0
        return 1

# Execution Time:0.03
Enter fullscreen mode Exit fullscreen mode
//java

class Solution {
    static int isGoodorBad(String S) {
        char[] vowels = {'a', 'e', 'i', 'o', 'u'};
        int vowel_cnt = 0;
        int consonant_cnt = 0;

        for (char ch: S.toCharArray()) {
            boolean is_vowel = false;
            if (ch == '?'){
                vowel_cnt++;
                consonant_cnt++;
            }else{
                for (char vowel: vowels) {
                    if (vowel == ch) {
                        is_vowel = true;
                        break;
                    }
                }
                if (is_vowel==true) {
                    vowel_cnt++;
                    consonant_cnt = 0;
                }else{
                    vowel_cnt = 0;
                    consonant_cnt++;
                }
            }
            if (vowel_cnt > 5 || consonant_cnt > 3){
                return 0;
            }
        }
        return 1;
    }
};

// Execution Time:0.23
Enter fullscreen mode Exit fullscreen mode

Majority Element

# python

class Solution:
    def majorityElement(self, A, N):
        half = len(A) / 2
        A.sort()
        n = 0
        for i in A:
            if n != i:
                n = i
                majority = 1
            else:
                majority += 1
            if majority > half:
                return i
        return -1

# Execution Time:1.17
Enter fullscreen mode Exit fullscreen mode
//java

class Solution
{
    static int majorityElement(int a[], int size)
    {
        Arrays.sort(a);
        int n = 0;
        int half = a.length / 2;
        int majority = 0;
        for (int i: a){
            if (i != n) {
                n = i;
                majority = 1;
            } else {
                majority++;
            }

            if (majority > half) {
                return i;
            }
        }
        return -1;
    }
}

// Execution Time:3.14
Enter fullscreen mode Exit fullscreen mode

Maximize Toys

# python

class Solution:
    def toyCount(self, N, K, arr):
        arr.sort()
        total, answer = 0, 0
        for cost in arr:
            if cost + total <= K:
                total += cost
                answer += 1
            else:
                break
        return answer

# Execution Time:0.61
Enter fullscreen mode Exit fullscreen mode
// java

class Solution{
    static int toyCount(int N, int K, int arr[])
    {
        // code here
        Arrays.sort(arr);
        int total = 0;
        int answer = 0;

        for (int cost: arr) {
            if (cost + total <= K) {
                total += cost;
                answer++;
            } else {
                break;
            }
        }
        return answer;
    }
}

// Execution Time:1.00
Enter fullscreen mode Exit fullscreen mode

N Meetings in One Room

# python

class Solution:
    def maximumMeetings(self,n,start,end):
        if n == 1:
            return 1

        li = []
        for i in range(n):
            li.append((start[i], end[i]))

        li.sort(key=lambda tup: (tup[1], tup[0]))

        cnt = 1
        current_meeting = li[0]
        for next_meeting in li[1:]:
            if current_meeting[1] >= next_meeting[0]:
                continue
            current_meeting = next_meeting
            cnt += 1

        return cnt

# Execution Time:1.13
Enter fullscreen mode Exit fullscreen mode
//java

class Solution 
{
    public static int maxMeetings(int start[], int end[], int n)
    {
        int[][] schedules = new int[n][2];

        for(int i = 0; i < n; i++){
            schedules[i][0] = start[i];
            schedules[i][1] = end[i];
        }
        Arrays.sort(schedules, Comparator.comparing(arr -> arr[1]));

        int cnt = 1;
        int[] current_meeting = schedules[0];
        int[][] li = Arrays.copyOfRange(schedules, 1, n);
        for (int[] next_meeting: li){
            if (current_meeting[1] >= next_meeting[0]) {
                continue;
            }else {
                current_meeting = next_meeting;
                cnt++;
            }
        }
        return cnt;
    }
}

// Execution Time:2.96
Enter fullscreen mode Exit fullscreen mode

I am a beginner in Java, so I just wrote code in Python and translated it into Java. Maybe that's why the execution times of the Java codes are so long. I should refactor these once I get more familiar with Java.

Discussion (0)