2022년 2월 11일 금요일 - 오늘은 FLEX
오늘 올려볼 문제는 567번 Permutation in String 이라는 문제이다.
사진을 클릭하면 해당 문제로 이동합니다.
오늘도 LeetCode 사이트 오늘의 문제를 가지고 왔다.
아니 왜 permutation이라고 써서 헷갈리게 하냐고!!@!!@@!!
입력
사진에서도 볼 수 있듯이 String 2개가 주어진다.
풀이 및 코드
s1의 순열 중 하나가 s2에 포함되어 있는지를 판단하는 알고리즘이다.
오늘은 문제에서 permutation이라고 써서 헷갈린 것 때문에 해맨것을 제외한다면 처음부터 정답을 생각해냈다.
기본적으로 전에 풀었던 438번 문제 Find All Anagrams in a String 문제와 거의 같은 알고리즘을 쓴다.
그렇기에 설명은 여기에서 대신하겠다.
그래서 다른 풀이를 생각해봤다.
일단 누적합마다 해쉬맵에 저장한다.
이 때 해쉬맵에 현재 누적합 - k 가 존재한다면 결과값에 해당 해쉬맵에 들어있는 값을 더한다.
이런식으로 시간복잡도 O(N)에 풀 수 있는 방법을 생각해냈다.
이제 코드를 봐보자!
풀이코드
class Solution {
int[] arr = new int[30];
public boolean checkInclusion(String s1, String s2) {
if(s2.length() < s1.length())
return false;
for(int i = 0; i < s1.length(); i++)
{
arr[s1.charAt(i) - 'a']++;
arr[s2.charAt(i) - 'a']--;
}
for(int i = s1.length(); i < s2.length(); i++)
{
if(check())
return true;
arr[s2.charAt(i) - 'a']--;
arr[s2.charAt(i - s1.length()) - 'a']++;
}
if(check())
return true;
return false;
}
public boolean check()
{
for(int i = 0; i < arr.length; i++)
{
if(arr[i] != 0)
return false;
}
return true;
}
}
제출 화면
오늘은 문제에 permutation이라는 말에 꽂혀서 빨리 못 풀었던 문제였다.
그래도 뜻을 이해하고 풀어서 다행이다.
내일도 문제를 풀어서 블로그에 글을 쓸 수 있으면 좋겠다.
'LeetCode 문제 풀이' 카테고리의 다른 글
[LeetCode] 78번 문제를 풀어보았다. (ft. java) (0) | 2022.02.13 |
---|---|
[LeetCode] 127번 문제를 풀어보았다. (ft. java) (0) | 2022.02.12 |
[LeetCode] 560번 문제를 풀어보았다. (ft. java) (0) | 2022.02.10 |
[LeetCode] 532번 문제를 풀어보았다. (ft. java) (0) | 2022.02.09 |
[LeetCode] 258번 문제를 풀어보았다. (ft. java) (2) | 2022.02.08 |