[알고리즘, 자료구조] 보초법(sentinel method)

보초법이란? 검색하기 전에 배열 마지막에 값을 저장하는 방법

 

응용 프로그램 : 배열 앞에서 순서대로 입력된 값을 검색하여 찾는 프로그램 

종료 조건 : 
1) 검색할 값과 같은 요소를 발견한 경우

*선형검색과 달리 for문이 하나로 줄어들어 비용이 50%로 줄어들었다. 

 

구현 방법:
1. 요솟값을 입력받는다. 
2. 각 배열에 저장될 값을 랜덤으로 입력한다. (for문, random rand = new Random() 이용) 
3. 검색할 값을 입력받는다. 
4. 검색할 값을 배열 마지막에 저장한다 ==추가==
5. 배열, 요솟값, 검색값을 매개 변수로 하는 클래스 메서드 구현
6. 클래스 메서드 실행

 

출력 예시:
------------
요솟수: 7
x[0] : 6
x[1] : 4
x[2] : 3
x[3] : 2
x[4] : 1
x[5] : 8
검색할 값: 2
x[6] : 2
그 값은 4번째 위치에 있습니다. 
-------------

 

 

---

기존의 코드

package Algorithm;

import java.util.Random;
import java.util.Scanner;

public class SeqSearch {
  static int seqSearch(int[] x, int n, int key){
    int i = 0;
    //key값을 찾는 무한반복문
    while(true){
      if(i == n) return -1; // 종료 조건 1
      if(x[i] == key) return i; //종료 조건 2
      i++;
    }
  }

  public static void main(String[] args) {
    //요솟값을 입력받는다.
    Scanner sc = new Scanner(System.in);
    System.out.print("요솟수 : ");
    int n = sc.nextInt();

    //요솟수만큼의 길이를 가진 배열 형성
    int[] x = new int[n];

    //각 배열에 값 넣기
    for(int i = 0; i < x.length; i++){
      Random rand = new Random();
      x[i] = rand.nextInt(8) + 1; //rand는 0에서 8사이의 값 -> 1에서 9사이의 값
      System.out.printf("x[%d] = %d\n", i, x[i]);
    }

    System.out.print("검색할 값: ");
    int key = sc.nextInt();

    //검색 시작
    int idx = seqSearch(x, n, key);

    if(idx == -1)
      System.out.println("값이 존재하지 않습니다.");
    else
      System.out.printf("그 값은 x[%d]의 위치에 있습니다.", idx);
  }
}

 

 

보초법을 적용한 코드

int[] x = new int[n + 1];

 

배열의 길이를 입력값보다 하나를 더 늘렸다. 

for(int i = 0; i < x.length-1; i++){
  Random rand = new Random();
  x[i] = rand.nextInt(8) + 1; //rand는 0에서 8사이의 값 -> 1에서 9사이의 값
  System.out.printf("x[%d] = %d\n", i, x[i]);
}

 

배열에 값을 넣는 for문에서 마지막 배열을 비우기 위해 x.length-1을 하였다. 

 

static int seqSearchSen(int[] x, int n, int key){
  int i = 0;
  x[n] = key;
  //key값을 찾는 무한반복문
  while(true){
    if(x[i] == key) break;//종료 조건 1
    i++;
  }
  return i == n ? -1 : i;
} //end of seqSearch

 

그리고 마지막 배열에는 검색할 값(key)를 넣는다. 

배열을 벗어나는지 여부를 확인하는 if문이 없어져서 if문이 하나로 줄어들었다. 

하지만, 배열의 마지막 값은 임의로 부여한 것이기 때문에 이를 확인할 필요가 있다. 

그래서 찾아낸 값이 보초인지 판단하는 return i == n ? -1 : i을 넣었다. 

 

package Algorithm;

import java.util.Random;
import java.util.Scanner;

public class SeqSearchSen {
  static int seqSearchSen(int[] x, int n, int key){
    int i = 0;
    x[n] = key;
    //key값을 찾는 무한반복문
    while(true){
      if(x[i] == key) break;//종료 조건 1
      i++;
    }
    return i == n ? -1 : i;
  } //end of seqSearch

  public static void main(String[] args) {
    //요솟값을 입력받는다.
    Scanner sc = new Scanner(System.in);
    System.out.print("요솟수 : ");
    int n = sc.nextInt();

    //요솟수만큼의 길이를 가진 배열 형성
    int[] x = new int[n + 1];

    //각 배열에 값 넣기
    for(int i = 0; i < x.length-1; i++){
      Random rand = new Random();
      x[i] = rand.nextInt(8) + 1; //rand는 0에서 8사이의 값 -> 1에서 9사이의 값
      System.out.printf("x[%d] = %d\n", i, x[i]);
    }

    System.out.print("검색할 값: ");
    int key = sc.nextInt();
    x[x.length-1] = key;

    //검색 시작
    int idx = seqSearchSen(x, n, key);

    if(idx == n-1)
      System.out.println("값이 존재하지 않습니다.");
    else
      System.out.printf("그 값은 x[%d]의 위치에 있습니다.", idx);
  } //end of main
}