Part 06 선형탐색 (Linear Search)

 

  - Collentions에 binarySearch()메서드를 제공한다.

  - API를 확인해보면 

    -> comparable 인터페이스를 구현해야한다.

    -> comparaTo 메서드를 implement해야한다.

  - indexOf()는 정확하지만 오래 걸린다.

  

  Ex) Binary Search

java

열기 줄바꿈

import java.util.Collections;
import java.util.LinkedList;
import java.util.List;
import java.util.Objects;

class MyData implements Comparable<MyData>{
	int v;
	
	public MyData(int v) {
		this.v = v;
	}
	
	public String toString() {
		return "" + v;
	}
	
	@Override
	public boolean equals(Object o) {
		if(this == o)	return true;
		if(o == null || getClass() != o.getClass())	return false;
		MyData mydata = (MyData) o;
		return v== mydata.v;
	}
	 
	@Override
	public int hashCode() {
		return Objects.hash(v);		
			// 같은 value가 들어가면 같은 해시값이 나온다.
			// 키로 사용되는 것은 해시코드를 호출해서 나온 해시값을 이용해서 인덱스로 이용한다.
	}
	 
	public int compareTo(MyData o) {
		
		return v - o.v; 	// 내 데이터 - 남의 데이터
	} 
}

public class LinearSearch {
	public static void main(String[] args) {
	
		List<MyData>list = new LinkedList<>();
	
		for(int i = 1 ; i <= 100; ++i) {
			list.add(new MyData(i));
			
		}
		System.out.println(list);
		
		int index = Collections.binarySearch(list, new MyData(63) );	// binarySearch: 인덱스를 리턴
		System.out.println(index);
		System.out.println(list.get(index));
	}
}

 

  Ex) 전화 번호 목록

  - sort와 startsWith를 이용한다.

  - phone_book[i].startsWith(phone_book[i-1]) : phone_book[i-1]가 phone_book[i]의 접두사인지 확인한다.

  - Arrays.sort(배열명): 배열을 오름차순으로 정렬한다.

java

열기 줄바꿈

import java.util.*;
class Solution {
    public boolean solution(String[] phone_book) {

        Arrays.sort(phone_book);        // sort로 정렬하면 119와 1195524421이 옆자리에 정렬된다. 
        
        for(int i = 1; i < phone_book.length; ++i){     //따라서,  바로 옆자리에 있는 수가 접두사인지 확인하면 된다.
            if(phone_book[i].startsWith(phone_book[i-1])) return false;
        }
        return true;
    }
}

 

 

  Ex) 문자열 내 p와 y의 개수

java

열기 줄바꿈

class Solution{
    boolean solution(String s){
        int p = 0;
        String s2 = s.toLowerCase();     //s의 모든 글자를 소문자로 바꾼다
        
        // s2에 y, p 있는지 한 글자씩 확인
        for(char c : s2.toCharArray()) if (c == 'p') p++;   
        for(char c : s2.toCharArray()) if (c == 'y') p--;
        
        return p == 0;
    }    
}

  - String s2 =  s.toLowerCase() : 문자열 s를 모두 소문자로 바꾼다. 

  - String s2를 한글자씩 char[]배열로 바꿔서 p 또는 y가 있으면 p는  +1, y는 -1을 해준다.

  - 나중에 결과 값이 0이면 true

 

  Ex) 스킬 트리 (skill_trees)

  - 선행 스킬 순서 skill과 유저들이 만든 스킬트리1를 담은 배열 skill_trees가 매개변수로 주어질 때, 가능한 스킬트리 개수를 return 하는 solution 만들기

  - String s2 = s.replaceAll("[^" + skill + "]" , "" ); 

    -> 문자열 s에 대해서 skill로 시작하지 않는 문자들은 모두 제거한다.

java

열기 줄바꿈

class Solution {
    public int solution(String skill, String[] skill_trees) {
        int answer = 0;
        
        for(String s : skill_trees) { 
          String s2 =  s.replaceAll("[^"+skill+"]" , "");   
            //skill_trees에 있는 모든 스트링에 대해 
            // skill에 없는 문자들을 모두 공백으로 바꾼다
            
        if( skill.startsWith(s2) ) answer++;    
            // skill에 없는 문자를 제거한 새로운 문자열 s2에대해
            // skill이 s2로 시작하는지 확인하여 카운트한다. 
        }
        return  answer;
    }
}

 ps://programmers.co.kr/learn/courses/13577