[Day2/15] LeetCode 75

Level 1 : day 2

1일차는 스킵하고 2일차부터 작성 시작한다!
시작이 반이라 했는데, 아직까지는 쉬운 문제들이 나오는 것 같다.

https://leetcode.com/study-plan/leetcode-75

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.

205. Isomorphic Strings (문제링크)

문자열 s, t 가 주어지고 s 랑 t 가 isomorphic 인지 확인하는 문제다.

문자열 s, t 가 isomorphic 일 경우, s의 문자열이 t로 변경이 가능한 것이다 - 즉 1:1 mapping 이 가능한 것이다.

풀이과정

1. HashMap 을 이용하여 Character : Character 형태로 맵핑을 해준다.

2. 반복문을 이용하여 map 을 채워준다
   2a. 만약 이미 있는 key 라면 value 와 value 가 될 캐릭터를 비교한다.
   2b. 다르면 return false, 같으면 2번을 반복한다.

위 반복문이 다 돌렸다고 끝은 아니다...
No two characters may map to the same character, but a character may map to itself.

즉, 두 캐릭터가 같은 캐릭터를 매핑할 수가 없다.

따라서 중복되는 맵핑을 확인하기 위해 Set 도 썼다.

3. Set 에 Map 의 values 을 다 넣는다.
4. Set 의 사이즈와 Map 의 사이즈를 비교하고 같으면 true 다르면 false 을 리턴한다.

Java Solution

class Solution {
    public boolean isIsomorphic(String s, String t) {
        HashMap<Character, Character> map = new HashMap<>();
        HashSet<Character> set = new HashSet<>();
        
        for (int i = 0; i < s.length(); i++) {
            char c1 = s.charAt(i);
            char c2 = t.charAt(i);
            
            if (map.containsKey(c1)) {
                if (map.get(c1) != c2) return false;
            }
            else {
                map.put(c1, c2);
            }
            
        }
        
        for (Character key: map.keySet()) {
            set.add(map.get(key));
        }
        
        return set.size() == map.size();
    }
}

205. Is Subsequence (문제링크)

문자열 s, t 가 주어졌을 때 s 가 t 의 subsequence 면 true, 아니면 false 을 반환하는 문제다.

Subsequence 은 순서가 중요하며 연달아 이어져 있을 필요가 없다.

예시)
"ace" 은 "abcdef" 의 subsequence 다.
그러나 "aec" 은 "abcdef" 의 subsequence 가 아니다.

이 문제의 제한사항은 다음과 같다.

1. s 는 100 이하의 길이를 가진 문자열
2. t 는 10000 이하의 길이를 가진 문자열
3. s 와 t 는 의 모든 문자는 소문자

제한사항을 보면 $O(st)$ 복잡도를 사용해도 $O(st) = O(1000000)$ 로서 100만번의 수행이 된다.
따라서, 중첩반복문을 통하여 구현이 가능하다.

풀이과정

이 문제는 s 의 순서가 중요하기 때문에, 다음과 같이 s와 t가 주어졌을 때

s = "ace" , t = "abcde"

s 의 'a' 를 t 의 0번째에서 찾았기 때문에, 그 다음 s 의 'c' 은 t 의 1번 째 이후에서 찾아야한다.

s 의 'c' 를 t 의 2번째에서 찾았기 때문에, 그 다음 s 의 'e' 은 t 의 3번 째 이후에서 찾아야한다.

1. s 의 문자열 순서에 맞는지 확인하기 위해 outer for 문을 s를 중심으로 반복한다.
2. inner for 문에는 t 중심으로 하되, 직전에 찾은 index 을 시작으로 한다.
3. s 의 캐릭터와 t 의 캐릭터가 일치할 때마다 count 을 하나씩 증가시켜준다.
4. 모든 반복문이 끝난 후 count 와 s 의 길이를 비교한다.

Java Solution

class Solution {
    public boolean isSubsequence(String s, String t) {
        int prev = 0;
        int cnt = 0;
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            
            for (int j = prev; j < t.length(); j++) {
                if (c == t.charAt(j)) {
                    cnt++;
                    prev = j+1;
                    break;
                }
            }
        }
        
        if (cnt == s.length()) return true;
        else return false;
    }
}

이렇게 day 2 문제를 다 풀었다. Easy 레벨이라 아직까지는 굉장히 쉽다 생각이든다. 내일 day 3 이 기대된다~