리트코드 - 290. Word Pattern

리트코드 - 290. Word Pattern

출처 - https://leetcode.com/problems/word-pattern/description/?envType=study-plan-v2&envId=top-interview-150

 

문제 설명

주어진 패턴과 문자열 s가 주어졌을 때, s가 동일한 패턴을 따르는지 확인합니다.

여기서 "동일한 패턴을 따른다"는 패턴의 각 문자와 s의 각 단어 간에 일대일 대응이 있는 경우를 의미합니다. 다시 말해, 패턴의 각 문자와 s의 각 단어 간에 일대일 대응 관계가 있어야 합니다.

 

의사코드

words = s를 문자열 배열로 변경 if (pattern의 길이 != words 배열길이)    false 리턴 map = new Hashmap 반복문 시작 (pattern 한글자씩 순회)     c = pattern 한글자씩 떼냄     word = words에서 한개씩 빼냄     if (map이 c를 key로 가지면)         if (이때의 value가 word랑 같지 않으면)             false 리턴     else         if (map이 value로 word를 가지면)             false 리턴         map에 key=c , value = word로 추가 반복문 종료 true 리턴

 

풀이코드

class Solution {
    public boolean wordPattern(String pattern, String s) {
        String[] words = s.split(" ");

        if (pattern.length() != words.length) {
            return false; 
        }

        Map<Character, String> map = new HashMap<>();

        for (int i = 0; i < pattern.length(); i++) {
            char c = pattern.charAt(i);
            String word = words[i];


            if (map.containsKey(c)) {
                if (!map.get(c).equals(word)) {
                    return false;
                } 
            } else {
                if (map.containsValue(word)) {
                    return false;
                }
                 map.put(c, word);
            }
        
        }
        return true; 
    }
}

코드설명

map을 사용하여 풀 수 있는 문제다.

 

pattern을 char 한글자 단위로 쪼개서 map 배열에 key값으로 넣고 value는 words의 띄어쓰기를 기준으로 나눈 배열 값을 각각 넣어준다.

 

map에 key값이 이미 있다면, value 확인해서 word와 같은지 비교해보고, 같으면 넘어가고 아니면 false를 리턴한다.

만약 key를 가지고 있지 않다면, 혹시 다른 value 중에 word를 가지는지 확인하고 있으면 false를, 없는 경우 map에 값을 넣어준다.

 

예를 들어 pattern="abba" s="dog dog dog dog" 라는 매개변수가 주어진다면 첫번째 요소인 key=a, value=dog로 map에 넣게는데 value값이 있는지 확인하지 않으면 key=b를 넣을때 dog가 또 들어갈 수 있기 때문이다.

 

이렇게 하면 패턴이 일치하는 경우에만 true를 리턴하게 된다.

 

시간복잡도 - O(n) (n은 pattern string의 크기)

공간복잡도 - O(n) (n은 words 배열의 크기)

 

문제를 풀며 생각한 흐름과 배운 점

이전문제 리팩토링 했던 코드랑 뭔가 비슷하게 풀 수 있을 것 같아서 map없이 해결해보려 했는데 실패했다.

두 개의 배열을 만들고 하나는 알파벳을, 하나는 알파벳에 대응하는 단어를 넣으려고 했는데 이 단어가 중복될때 처리하는 과정이 비효율적이었다.

 

그래서 map의 map.containsValue 메소드를 사용하기로 했는데...계속 오류가 났다.

간단한 문제 같으면 의사코드 없이 풀었는데 코드로 적다보니까 뭔가 자꾸 꼬인 것이다.

키를 안가지면  value중에 있으면 f  키를 추가 키를 가지면    ...

위와같은 의사코드부터 적어보고 다시 풀어보니 어렵지 않게 풀 수 있었다.

 

정리

문제를 보고 어떻게 풀면 효율적일지 생각하는 과정이 결국 답을 빨리 도출하는 핵심인 것 같다.