916. Word Subsets

https://leetcode.com/problems/word-subsets/description/

 

이번 문제는 꽤 난이도가 있었다.

분명 중간 난이도인데 나한테는 정말 어려웠다.

 

먼저 문제를 보자

두 개의 문자열 배열 words1과 words2가 주어졌습니다.
문자열 b는 b의 모든 문자가 다중도를 포함하여 a에 나타나면 문자열 a의 하위 집합입니다.
예를 들어, "wrr"은 "warrior"의 하위 집합이지만 "world"의 하위 집합은 아닙니다.
words1의 문자열 a는 words2의 모든 문자열 b에 대해 b가 a의 하위 집합이면 범용입니다.
words1의 모든 범용 문자열의 배열을 반환합니다.
답은 어떤 순서로든 반환할 수 있습니다.
 
예제 1 :
Input : words1 = [ "amazon", "apple", "facebook", "google", "leetcode"],
            words2 = [ "e", "o"]
Output : ["facebook", "google", "leetcode"]

예제 2 :
Input : words1 = [ "amazon", "apple", "facebook", "google", "leetcode"],
            words2 = [ "l", "e"]
Output : [ "apple", "google", "leetcode"]
 
제약 조건:
- 1 <= words1.length, words2.length <= 10⁴
- 1 <= words1[i].length, words2[i].length <= 10
- words1[i]와 words2[i]는 소문자 영어 문자로만 구성됩니다.
- words1의 모든 문자열은 고유합니다.

 

이 문제를 보고 내가 이해한건 2개의 문자열 배열이 주어지면,

words2의 문자가 words1에 포함되어있는지 확인하는 문제인 줄 알았다

 

그래서 아래와 같이 작성하여 제출했다.

class Solution {
    public List<String> wordSubsets(String[] words1, String[] words2) {
        List<String> result = new ArrayList<>();
		
        // 문자열 반복
        for(String t : words1){
            for(int i = 0; i < words2.length;i++){
            	// words2에 있는 문자가 없으면 중지
                if(!t.contains(words2[i])){
                    break;
                }
                // 마지막까지 해당 문자가 존재한다면
                else if(i == words2.length-1 && t.contains(words2[i])){
                    result.add(t);
                }
            }
        }
        return result;
    }
}

간단하게 저번에 배운 contains 함수를 사용해서 문자열에 해당 문자가 포함되는지 확인하는 코드이다.

 

그런데 바로 틀려버렸다..

예제 3 : 
Input : words1 =["amazon","apple","facebook","google","leetcode"]
            words2 =["lo","eo"]
내 출력 : [ ]
답안 : ["google","leetcode"]

 

여기서 첫번째 문제는 나는 한개의 문자가 들어있는지 비교하도록 짰는데, 문자열의 길이가 2이상이란 것과

두번째 가장 큰 문제는 "lo", "eo" 에 보면 "o"가 2번씩 들어가는데 "leetcode"에 보면 "o"가 하나밖에 안들어간다..

이중에서 두번째 문제때문에 정말 머리아팠다.

 

그래서 이번에는 그 부분을 수정해서 새롭게 코드를 짰다.

class Solution {
    public List<String> wordSubsets(String[] words1, String[] words2) {
        List<String> result = new ArrayList<>();
        // 해시맵 생성
        HashMap<Character,Integer> h1 = new HashMap<Character,Integer>();
        HashMap<Character,Integer> h2 = new HashMap<Character,Integer>();
        // 문자의 빈도수를 계산해서 풀어야함
        // 먼저 words2의 문자 빈도수를 계산해놔야함
        char a;
        for(String temp : words2){
            for(int i = 0; i < temp.length(); i++){
                a = temp.charAt(i);
                // 일치하는 키 값이 있다면 값 증가
                if(h1.containsKey(a)){
                    h1.replace(a,h1.get(a) + 1);
                } else{ // 없으면 생성
                    h1.put(a,1);
                }
            }
        }
        
        // 만들어진 해시맵을 기준으로 입력받은 문자열에서 개수를 세서 확인
        for(String temp : words1){
            for(int i = 0; i < temp.length(); i++){
                // 분리한 문자열에서 같은 문자가 있는지 확인
                a = temp.charAt(i);
                // 찾는 단어와 일치하는지 검색
                if(h1.containsKey(a)){
                    // 이미 존재한다면 값 증가
                    if(h2.containsKey(a)){
                        h2.replace(a,h2.get(a) + 1);
                    }else{ // 없으면 생성
                        h2.put(a,1);
                    }
                }
            }
            // 값을 넣는 동작이 모두 끝남 
            if(h1.size() == h2.size()){
                for(Character key : h1.keySet()){
                    if(h1.get(key) >= h2.get(key) && !result.contains(temp)){
                        result.add(temp);
                    }
                }
            }
            // 초기화
            h2.clear();
        }

        
        return result;
    }
}

 

이번에는 해시맵을 써서 빈도수를 체크하고 비교하게 짰는데

일단 3번째 예제는 맞았는데 새로운 문제가 나타났다.

예제 4.
Input : words1 =["amazon","apple","facebook","google","leetcode"]
           words2 =["e","oo"]
내 출력 : ["facebook","google","leetcode"]
답안     : ["facebook","google"]

 

입력으로 같은 문자열이 두개 이상 들어오는건 예상하지 못했다..

그래서 오랜 시간을 고민하다가 결국 솔루션을 찾아봤고 덕분에 해결했다.

 

솔루션 출처

class Solution {
    public List<String> wordSubsets(String[] words1, String[] words2) {
        List<String> result = new ArrayList<>();
		
        // 최대 빈도수
        int[] maxIndex = new int[26];
        int[] tempIndex = new int[26];
        // 문자의 빈도수를 계산해서 풀어야함
        // 먼저 words2의 문자 빈도수를 계산해놔야함
        for(String w2 : words2){
            Arrays.fill(tempIndex,0);
            // .toCharArray는 문자열을 문자단위로 쪼개줌
            for(char ch : w2.toCharArray()){
                tempIndex[ch - 'a']++;
            }
            // 서로 비교해서 더 큰값을 저장
            for (int i = 0; i < 26; ++i){
                maxIndex[i] = Math.max(maxIndex[i], tempIndex[i]);
            }
        }
        // 최대 빈도수를 구했으니 하나씩 해당하는 값을 올려서 최대 빈도수랑 비교해야함
        // words1의 값을 분리
        for(String w1 : words1){
            int[] index = new int[26];
            boolean tag = true;

            for(char ch : w1.toCharArray()){
                index[ch - 'a']++;
            }
			
            // maxIndex보다 작다면 false
            for(int i = 0;i<26;i++){
                if(maxIndex[i] > index[i]){
                    tag = false;
                    break;
                }
            }

            if(tag){
                result.add(w1);
            }
        }

        return result;
    }
}

 

정말 막힐때는 솔루션을 보고 내 원래 코드랑 비교하면서 배우는것도 하나의 방법인 것 같다.