[Java] 검색 알고리즘 - 보초법을 활용한 선형검색 과정을 출력하는 프로그램

본 포스팅은 'Do it! 자료구조와 함께 배우는 알고리즘 입문 Java편'을 스터디 한 내용입니다.

 

 

안녕하세요. 글쓰는 개발자입니다.

  자료구조 관련하여 study내용을 포스팅 하다 보니, 다소 문체가 많이 딱딱했었는데요. 글쓰는 개발자 답게, 저의 문체가 아니다보니 조금은 불편(?)하기도 하고해서 연습문제처럼 제가 스스로 생각한 프로그램들은 원래의 형식대로 포스팅하고자 합니다.

 

  배열의 선형검색 과정을 console창에 출력하는 프로그램을 만드는 것인데요. 저는 나름대로 한 번 더 생각하기 위해서 보초법을 활용하는 과정을 출력하고자 합니다. 선형검색과 관련된 내용이 숙지가 안되신 분들은 아래링크를 통해, 먼저 학습하고 오시면 이해가 빠르실거라 생각됩니다.

https://backstreet-programmer.tistory.com/64

[Java] 검색 - 선형(순차)검색 / 보초법

 

  기능 자체에 큰 차이는 없지만, 결과를 내기 위해 고민하는 시간 동안 스스로 생각한다는 점에서 예제와 연습문제는 큰 차이가 있다고 생각됩니다. 이 포스팅을 보시는 분들도 혹시 공부하는 자료가 있다면, 예제만 따라하지 마시고, 스스로 생각하는 문제를 꼭 풀어보시기 바랍니다.

실행결과

검색성공(8검색, 마지막요소는 보초)

검색 실패(9검색, 보초값 도달)

 

전체코드

import java.util.Scanner;

/**
 * @Date 2020. 1. 27.
 * @Time 오후 1:58:26
 * @author BRYANT
 * =====================
 * Writing Developer
 */
public class sentinelSeqSearchPractice {

	/**
	 * @Author : BRYANT
	 * @Date : 2020. 1. 27.
	 * @Method Name : sentinelSequenceSearch
	 * @return : int
	 * @Description : 보초법을 활용한, 선형검색 메소드(검색과정을 포함)
	 */
	static int sentinelSequenceSearch(int [] sentinelArray, int num, int key) {
		
		sentinelArray[num] = key; //배열의 맨 마지막 값에 key대입
		int searchResult = 0;
		String [] starArray = new String[num+1];
		
		System.out.print("   | ");
		for(int i=0; i<sentinelArray.length; i++) {
			System.out.print(i+" ");
		}
		System.out.println("");
		System.out.print("---+------------------------ \n");
		
		//선형검색 구현
		for(int i=0; i<sentinelArray.length; i++) {
			
			System.out.print("   | ");
			for(int j=0; j<starArray.length; j++) {
				if(i==j) {
					starArray[j] = "*";
					System.out.print(starArray[j]+" ");
					
				}else {
					
					starArray[j] = " ";
					System.out.print(starArray[j]+" ");
					
				}
				
			}
			System.out.println("");
			System.out.print("  "+i+"| ");
			for(int j=0; j<sentinelArray.length; j++) {
				System.out.print(sentinelArray[j]+" ");
			}
			System.out.println("");
			
			if(sentinelArray[i] == key) {
				
				searchResult = i;
				break;
				
			}
			
		}
		
		return searchResult;
		
	}

	/**
	 * @Author : BRYANT
	 * @Date : 2020. 1. 27.
	 * @Method Name : main
	 * @return : void
	 * @Description : 실행을 위한 main method
	 */
	public static void main(String[] args) {

		Scanner stdIn = new Scanner(System.in);
		
		System.out.println("요솟수 : ");
		int num = stdIn.nextInt();
		int [] sentinelArray = new int[num+1];
		
		for(int i=0; i<num; i++) {
		
			System.out.println("sentinelArray["+i+"] : ");
			sentinelArray[i] = stdIn.nextInt();
			
		}
		
		System.out.println("검색할 값 : ");
		int key = stdIn.nextInt();
		int searchResult = sentinelSequenceSearch(sentinelArray, num, key);//검색결과
		
		
		//최종결과
		if(searchResult == num) {
			
			System.out.println("검색결과가 없습니다.(보초값 도달)");
			
		}else {
			
			System.out.println("검색결과는 "+sentinelArray[searchResult]+"이고, 배열의 index는 "+searchResult+"입니다.");
			
		}
		
		

	}

}