문자열

- 팰린드롬을 검사하는 간단한 문제이다.

- 단 문자열과 숫자만 비교해야한다.

 

 > Leetcode (125) - 유효한 팰린드롬

 

나의 풀이 (13ms)

  public boolean isPalindrome(String s) {
        s = s.toLowerCase();
        s = s.replaceAll("[^a-z0-9]","");


            int left = 0;
            int right = s.length()-1;

            for(int i=0; i<s.length();i++ ){
                if(left > right){
                    return true;
                }
                if(s.charAt(left) == s.charAt(right)){
                    left++;
                    right--;
                }else{
                    return false;
                }
            }
            return true;
    }

 

 

 

 

1. 문자 단위로 추출해서 처리 (2ms)

 

  public boolean isPalindrome(String s) {
       int start =0;
       int end = s.length() - 1;

	while(start < end){
		if(!Character.isLetterOrDigit(s.charAt(start))){
    		start++;
   	   }else if(!Character.isLetterOrDigit(s.charAt(end))){
    	    end--;
       }else{
    
       if(Character.toLowerCase(s.charAt(start))!=Character.toLowerCase(s.charAt(end))){
    	  return false;
       }
         start++;
         end--;
      }
  }

      return true;
    }

 

 

2. 문자바로비교 (16ms)

 

public boolean isPAlindrome(String s){

	String s_filtered = s.replaceAll("[^A-Za-z0-9]","").toLowerCase();
    String s_reversed = new StringBuilder(s_filtered).reverse().toString();
      
      
      return s_filtered.equals(s_reversed);
}

 

 

- 배운 것 

 

Chracter.isLetterOrDigit으로 숫자와 문자만 검사할 수 있다.

[^A-Za-z0-9] 정규식을 통한 제거 

left,right로 하는 것은 좋았으나, 검사를 다르게 하는게 더 빨랐을 것 같다. 

 

 

> 문자열 뒤집기 LeetCode(344) 

 

1. 나의 풀이 (0ms)

 

 public void reverseString(char[] s) {
        int len = s.length;

        for(int i=0; i<len/2;i++){
            char temp = s[i];
            s[i] = s[len-1-i];
            s[len-1-i] = temp;
        }
    }

 

 

2.  풀이 스타일이 비슷하다! 

int start = 0;
int end  = s.length - 1;

while(start < end){

		char temp = s[start];
        s[start] = s[end];
        s[end] = temp;
        
        start++;
        end--;

}

 

 

- 배열 반만 도는 것 while문으로 표현하면 start<end로 start++, end-- 생각할 수 있다. (시작과 끝에서 한칸씩 오는경우)

 

 

 

> 가장 흔한 단어 (819) 

 

1. 나의 풀이 (26)

public String mostCommonWord(String paragraph, String[] banned) {
      
      //a-z말고 다른 단어 모두 제거 
      paragraph = paragraph.toLowerCase().replaceAll("[^a-z]"," ");
		
        //띄어쓰기 두개이상인것 하나로 만들고 trim
        paragraph = paragraph.replaceAll("\\s+"," ").trim();
        
        //split로 쪼개기
        String[] arr = paragraph.split(" ");
      
        List<Integer> idxarr = new ArrayList<>();
		
        for(int i=0; i<arr.length;i++){
            int cnt =0;
            if(bannedString(arr[i],banned)){
                idxarr.add(0);
                continue;
            }else{
                for(int j=i+1; j<arr.length; j++){
                	 //공백이 아니고 같은 단어일 경우 cnt++
                    if(!arr[i].isBlank()&&arr[i].compareTo(arr[j]) ==0){
                        cnt++;
                    }
                }
                idxarr.add(++cnt);
            }

        }

        int MaxIdx = maxIdx(idxarr);

        return arr[MaxIdx];
    }
	
    //금지단어일 경우 저장안함 
    private static boolean bannedString(String ar,String[] bad) {
        for(int i =0; i<bad.length;i++){
            if(ar.equals(bad[i])){
                return true;
            }
        }
        return false;
    }
	//배열에서 가장 큰 인덱스 찾기
    public static int maxIdx(List<Integer> arr){
        int maxIdx=0;

        for(int i=0; i<arr.size();i++){
            if(arr.get(maxIdx) < arr.get(i)){
                maxIdx=i;
            }
        }
        return maxIdx;
    }

 

2. HashMap 이용한 풀이 

 

 public String mostCommonWord(String paragraph, String[] banned) {
       
     Set<String> ban = new HashSet<>(Arrays.asList(banned));

    Map<String,Integer> counts = new HashMap<>();

    String[] words = paragraph.replaceAll("\\W+"," ").toLowerCase().split(" ");

        for(String w : words){

	        if(!ban.contains(w)){
    	        counts.put(w,counts.getOrDefault(w,0)+1);
            }
    
            }
            return Collections.max(counts.entrySet(),Map.Entry.comparingByValue()).getKey();
    }

 

- \W는 문자가 아닌 것을 의미 \W같은 것 사용하려면 replaceAll에선 \\으로 처리해야함

- set에 담은 이유는 contains사용하려고 Array를 List로 만들어서 Set에 담기 (Collection끼리 가능 생성자에 넣기 가능!)

- Map에 getOrDefault가 재밌다 value를 추출했을 때 있으면 값나오고 없으면 default 나옴!

- Collections.max는 가장 큰 값을 찾는다. (entrySet > [키=값, 키=값,키=값] -> map을 약간 배열화), 뒤에는 comp기준 담는다. Map.Entry.comparingByValue()로하면, Entry에 Value를 기준으로 값을 비교한다!  

    -> 해당메서드의 파라미터값이 객체면 가장 큰 객체 반환해준다!  

   -> Collection인 List와 Set에서만 사용 가능한듯! 

 

*Collections.max 결과 Map.Entry<String,Integer>로 map에 저장된 엔트리 중 value제일 큰 것 하나 나옴! 

 

 

=> 주말에 람다쓴 것 적어두기 

 

- 그룹 애너그램 (리트코드 49)

 

1. 내풀이 (644ms) 

 public List<List<String>> groupAnagrams(String[] strs) {
          //애너그램이란 단어를 다시 조합했을 때 만들 수 있는 단어 의미
        List<List<String>> stringList = new ArrayList<>();

        for(int i=0; i<strs.length; i++){

            if(!"-".equals(strs[i])) {
                List<String> ana = new ArrayList<>();
                ana.add(strs[i]);

                for (int j = i + 1; j < strs.length; j++) {
                    if (strs[i].length() == strs[j].length()) {
                        if (isAna(strs[i], strs[j])) {
                            ana.add(strs[j]);
                            strs[j] = "-";
                        }
                    }
                }
                stringList.add(ana);
            }
        }
        return stringList;
    }

    public static boolean isAna(String a, String b){
        StringBuilder sb = new StringBuilder(b);

        for(char c : a.toCharArray()){
            if(b.indexOf(c) == -1){
                return false;
            }else{
                char[] barr = b.toCharArray();
                barr[b.indexOf(c)]='?';
                b=new String(barr);
            }

        }

        return true;
    }

 

-> 진짜 구리다..무슨생각으로 푼건지 모르겠음 이러지말자! 

 

   public List<List<String>> groupAnagrams(String[] strs) {
       Map<String,List<String>> results = new HashMap<>();

   	   for(String s : strs){

	    char[] chars = s.toCharArray();
    
        Arrays.sort(chars);
    
        String key = String.valueOf(chars);
    
        if(!results.containsKey(key)) {
    	     results.put(key,new ArrayList<>());  
          }
    
    	   results.get(key).add(s);
   	    }

    return new ArrayList<>(results.values());
 }

 

 

- String을 CharArray로 만든 후 -> sorting해서 키로 사용 -> 해당 키를 이용해서 문자열 값을 담아두기 

- 같은 값임을 비교해서 저장해두어야 할 때 위와 같은 생각 떠올려보자. map과 List를 사용해서 저장하는 방법

 

 

- 가장 긴 팰린드롬 부분 문자열 (리트코드 5번)

 

- 내풀이 (283ms)

class Solution {
    public String longestPalindrome(String s) {
        
     
        char[] charArr = s.toCharArray();

         TreeMap<Integer,String> paMap = new TreeMap(new Comparator<Integer>(){
             @Override
             public int compare(Integer o1, Integer o2) {
                 return o2-o1;
             }
         });


        int left = 0;
        int right;
        String target="";
        int len = charArr.length;
        for(; left<len;left++){
            right = len-1;

            while(left < right){
                if(charArr[left] == charArr[right]){
                    target = s.substring(left,right+1);
                    if(isPalindro(target)){

                        if(target.length() == len || len - target.length() < target.length()){
                            return target;
                        }
                        paMap.put(target.length(),target);
                    }

                }
                right--;
            }

        }

        if(paMap.isEmpty()){
            return String.valueOf(charArr[0]);
        }

        return paMap.get(paMap.firstKey());

    }

    public static boolean isPalindro(String target){

        int end  = target.length()-1;

        for(int i=0; i<(end+1)/2;i++){
            if(target.charAt(i) != target.charAt(end-i)){
                return false;
            }
        }

        return true;
    }
}

 

- 팰린드롬이 무조건 처음과 끝 글자가 같아야하고, 배열은 반만 돌아도 된다는 점

- 맨 왼쪽 단어와 맨 오른쪽 단어 계속 비교해가는 과정으로 작성했음 (left,right) 

- 만약 맨 오른쪽 단어와 왼쪽단어가 팰린드롬일 때 두 길이의 합이 전체 길이이거나, 전체 길이에서 팰린드롬을 뺀 길이가 

   팰린드롬 문자열 길이보다 작다면, 더 긴 필랜드롬이 나올 수 없음으로 return했다.

 

2. 투포인터 사용하기 (13ms..뮈친)

 

-> 최장 공통 부분 문자열 (DP)로 푸는 전형적인 문제이지만, 속도가 안나온다! 따라서 투포인터를 사용하셨다한다

 

int left;
int maxLen;

public String longestPalindrome(String s){


	int len = s.length();
    
    if(len < 2) return s;
    

	for(int i = 0; i < len -1; i++){
    	//0,1-> 1,2 2칸씩 확장하는 투포인터
        extendPalindrome(s,i,i+1);
        //3칸씩 확장하는 투포인터
    	extendPalindrome(s,i,i+2);
    
    }

	return s.substring(left,left + maxLen);
}

public void extendPalindrome(String s, int j, int k){

	while(j >= 0 && k <s.length() && s.charAt(j) == s.charAt(k)){
    	j--;
        k++;
    }
    
    if(maxLen < k-j-1){
    	left = j +1;
        maxLen = k - j -1;
    }
    
}

 

 

> 팰린드롬을 발견하면, 확장하는 형태의 풀이 

> 처음에 주어진 값에 따라 팰린드롬으로 판별된다면, 왼쪽, 오른쪽으로 퍼지면서 중앙에서부터 판별! 

> 두개의 포인터가 2칸 3칸으로 (2>4>6),(1>3>5)형태로 확장된다.

ex) dcbabcdd 

> 2개의 투 포인터가 우측으로 이동하다 3칸짜리 투포인터는 bab에서 팰린드롬으로 매칭되어, 양옆으로 확장하면서 

   가장 긴값을 가진다. 두개짜리 투포인터는 dd가 매칭되지만 더 확장을 못함! 

> 마지막에 k-j-1을 해주는 이유는 조건식에 따라 마지막으로 검사하면서 k는 팰린도룸보다 1커질 수 있음! 

 scbabkl 길이 3,start는 2,end 4  > 이때 k는 5,j는 1 길이는 5로 측정됨 

따라서 left는 j+1, maxlen은 k-j-1해주어야함!  (위치뺀거랑 길이 다르다~)

 

- 투포인터 알고리즘 

 

> 두개의 포인터를 사용해서 리스트나 1차원 배열을 탐색하는 알고리즘을 의미한다. 

> 순차적으로 접근하며, 위치를 기록해두어야할 때 좋다. 또한 정렬되어있을 때 성능이 좋다.

> 연속된 배열 혹은 리스트에서 부분을 찾아야할 때 많이 사용되는 것 같다! 

 

> 보통 left,right 혹은 start, end를 사용한다. 

> 보통 left(start) <= right(end) 조건을 많이 사용한다.

> 시작과 끝을 가리키는 경우가 많다. (위의 팰린드롬 문제는 그렇게 하지않긴함)