biweekly-contest-41

leetcode.com/contest/biweekly-contest-41

1684. Count the Number of Consistent Strings

https://leetcode.com/problems/count-the-number-of-consistent-strings/

굳이 set 까지 쓸 필요 있을까?

class Solution {
    public int countConsistentStrings(String allowed, String[] words) {
        boolean[] flag = new boolean[26];
        int cnt = 0;
        
        for(char ch : allowed.toCharArray())
            flag[ch-'a'] = true;
        
        for(String word : words) {
            boolean isConsistent = true;
            for(char ch: word.toCharArray()) {
                if(flag[ch-'a'] == false) {
                    isConsistent = false;
                    break;
                }                    
            }
            if(isConsistent == true)
                cnt++;
        }
        
        return cnt;
    }
}

이건 비트연산자 사용

class Solution {
public int countConsistentStrings(String allowed, String[] words) {
        int alphabet = 0, cnt = 0;
        for (int i = 0; i < allowed.length(); ++i) {
            int shift = allowed.charAt(i) - 'a';
            alphabet |= 1 << shift;
        } 
        outer:
        for (String w : words) {
            for (int i = 0; i < w.length(); ++i) {
                if ((alphabet & (1 << w.charAt(i) - 'a')) == 0) {
                    continue outer;
                }
            }
            ++cnt;
        }
        return cnt;
    }
}

1685. Sum of Absolute Differences in a Sorted Array

https://leetcode.com/problems/sum-of-absolute-differences-in-a-sorted-array/

for문 두번 도는 순간 tle

A+B+C+D+E-A

B+C+D+E+A-A-B

이런식으로 분석해서 점화식을 잘만들어야한다.

class Solution {
    public int[] getSumAbsoluteDifferences(int[] nums) {
        int n = nums.length;
        int left = 0;
        int right = 0;
        
        for (int num : nums) {
            right += num;
        }
        
        int[] result = new int[n];
        
        for (int i = 0; i < n; i++) {
            right -= nums[i];
            
            int fromLeft = nums[i] * i - left;
            int fromRight = right - (n - i - 1) * nums[i];
            result[i] = fromLeft + fromRight;
            
            left += nums[i];
        }
        
        return result;
    }
}