매일 조금씩

문자열이 하나 주어지고 조건에 만족하는 결과를 도출하도록 하는 문제의 유형은 매우 다양하다.대충 정리해보자면 다음과 같다.슬라이딩 윈도우 최대/최소길이start, end 투 포인터 활용anagram 판별s.toCharArray() 로 char[] 변환 후Arrays.sort() 사용palindrome 판별, 최대/최소길이start, end 투 포인터 활용중심확장법Character의 스태틱 함수 사용 (숫자 or 문자 인지 확인)Character.isLetter(), Character.isLetterOrDigit()여기서 가장 어려웠던 유형은 1번의 슬라이딩 윈도우였다.문제의 난이도가 어려워질수 있는 가능성이 더 많아 보였다.HashMap과 투 포인터, 적절한 변수들을 선언하여 풀어내야한다. 다음은 슬라이..

이 또한 중간 확장법을 사용해서문자열의 문자하나를 기준점으로 찍으면서각각에 홀수, 짝수로 나눠서 팰린드롬 갯수를 카운트 했다. class Solution { private int count = 0; // 팰린드롬 수 public int countSubstrings(String s){ if(s.length() = 0 && end

이것 또한 투포인터를 사용해야하는 문제이다.다만 최대 길이의 palindrome 문자열을 찾아야한다. 난두가지 방법을 생각했다.첫번째 문자부터 마지막 문자를 가리키는 포인터를 앞당기며 찾음. (가장자리 -> 가운데 방향으로 palindrome 탐색)문자 하나씩을 기준으로 삼고 양쪽으로 확장하며 찾음. (가운데 -> 가장자리 방향으로 palindrome 탐색)1번은 시간복잡도 O(n^3), 2번은 시간복잡도 O(n^2)이다.따라서, 2번의 중심확장방식이 더 효율적이다. 팰린드롬(palindrome) 문제는 '좌우대칭'이라는 팰린드롬의 특성에 따라, 시간복잡도를 줄이기 위해 최대길이 문제는 가운데 기준점을 찍으며 찾아가는 2번 방식이 효율적이다. 1번 방식)class Solution { public S..

20. Valid Parentheses 문제를 풀때는 괄호가 선입후출로 다 닫히는지 보는문제였기 때문에 Stack을 사용했다.그러나 이문제는 Palindrome 문제로문자, 기호, 숫자 등이 포함된 문자열에서 문자와 숫자가 대칭을 이루는지 확인하는 문제이다. 따라서 Stack을 사용하기보다 투 포인터로 가장자리부터 문자와 숫자를 만나면 두 포인터가 가리키는 문자/숫자가 일치하는지 확인하는 방식으로 진행하는 것이 공간복잡도는 O(1)이고, 시간복잡도는 O(N) 으로 효율적이다. class Solution { public boolean isPalindrome(String s) { if(s.isEmpty()){ return true; } int l..

Stack 사용하면 됨! class Solution { public boolean isValid(String s) { Stack stack = new Stack(); for(int i = 0; i

anagram 문제는 char[]로 만들어서 알파벳순으로 재정렬한 후, 찾는 것이 핵심이다.여기선 HashMap을 사용해서 재정렬된 단어를 키로 해서 그단어의 anagram인 것들을 value에 넣는 방법을 사용했다.  class Solution { public List> groupAnagrams(String[] strs) { Map> map = new HashMap(); for(String word : strs){ // 단어를 알파벳순으로 재정렬 char[] chars = word.toCharArray(); Arrays.sort(chars); String sorted = new String(ch..