[백준] 단계별로 풀어보기(단계:21,이분 탐색,JAVA)12015번, 가장 긴 증가하는 부분 수열 2

문제 링크

12015번: 가장 긴 증가하는 부분 수열 2

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

이분 탐색이란 오름차순으로 정렬된 값들에서 특정한 값을 찾는 과정입니다.

중간 값을 임의의 값으로 설정하여 찾는 값과 비교하여 동일하면 찾는 값이 되고 크면 시작값이 임의의 값이 되고 작으면 최대값이 임의의 값이 되어 그 과정을 반복하여 찾는 값이 정렬된 값에 존재하는지 확인하는 방법입니다.

이분탐색에 자세한 내용은 링크를 남기겠습니다.

이진 검색 알고리즘 - 위키백과, 우리 모두의 백과사전

예를들어(시작값 = 1, 최대값 = 9)

찾는 값 = 3, 중간값 = 5

1. 찾는 값이 중간 값보다 작으므로 최대값은 4가 된다.

1

2

3

4

5

6

7

8

9

시작값 = 1, 최대값 = 4 찾는값 = 3 중간값 = 2

2. 찾는 값이 중간 값보다 크므로 시작값은 = 3

1

2

3

4

5

6

7

8

9

시작값 = 3, 최대값 = 4 찾는값 = 3 중간값 = 33. 찾는 값과 중간값이 같으므로 3은 정렬된 숫자에 존재합니다.

1

2

3

4

5

6

7

8

9

이 문제에서는 리스트를 이용해서 증가하는 수열을 만드는 방법을 사용하였으며 마지막에 리스트의 크기가 수열의 길이가 됩니다.

입력값 첫 값은 리스트에 기본적으로 추가하며 다음 입력값부터 증가하는 수열에 형태인지 확인한 뒤 수를 추가한다.

10

1. 입력값 20일 때

10

20

리스트의 마지막 값 10보다 20이 크므로 증가하는 수열에 포함되어 리스트에 추가하였습니다.

2. 입력값 10일 때

10

20

리스트의 마지막 값 20보다 입력값 10이 작습니다. 그래서 증가하는 수열 마지막 값으로 추가할 수 없습니다.

하지만 10을 빨간색으로 표시한 이유는 입력값 10이 증가하는 시작수열로 변경될 수 있기 때문에 바뀌지 않은 것처럼 보이지만 실제로는 바뀐것으로 이해하고 있어야 합니다.

3. 입력값 30일 때

10

20

30

리스트의 마지막 값 20보다 30이 크므로 증가하는 수열에 포함되어 리스트에 추가하였습니다.

4. 입력값 20일 때

10

20

30

리스트의 마지막 값 30보다 입력값 20이 작습니다. 그래서 증가하는 수열 마지막 값으로 추가할 수 없습니다.

20을 빨간색으로 표시한 이유는 입력값 20이 증가하는 수열에서 먼저 입력된 20값이 아닌 두 번째로 입력된 값이 수열에 포함될 수 있기 때문에 바뀌지 않은 것처럼 보이지만 실제로는 바뀐것으로 이해하고 있어야 합니다.

5. 입력값 50일 때

10

20

30

50

리스트의 마지막 값 30보다 50이 크므로 증가하는 수열에 포함되어 리스트에 추가하였습니다.

증가하는 수열의 길이는 리스트의 크기인 4를 결과로 출력하면 됩니다.

 

10과 20이 동일하게 들어갔을 때 바뀐것으로 이해해야 한다는 것을 예시로 설명하겠습니다.

만약 입력값이 100 200 3 을 받았을때 200까지는 아래와 같은 리스트일 것입니다.

100

200

여기서 3을 입력 받았을 때 리스트가 변경됩니다.

3

200

100, 200, 3에서 가장 긴 증가하는 수열은 {100, 200} 입니다. 하지만 위에 리스트를 보면 {3, 200}처럼 보이는데요.

리스트에서는 원래의 값이 있었기 때문에 3보다 크고 200보다 작은 값이 원래 하나 존재한다고 생각하시고 있으시면 될 것 같습니다.

3 ≤ 100 ＜200 으로 리스트에 3의 값에는 100까지 존재한다고 생각하시고 계시면 됩니다.

그래서 리스트의 값을 변경할 때 저희는 브루트포스로 저장된 리스트의 값을 비교하는 것이 아닌 이분탐색으로 인덱스를 구하여 리스트의 값을 변경해주도록 할 것입니다.

 

문제를 해결한 알고리즘의 과정입니다.

1. 입력값 첫 값을 리스트에 저장합니다.

2. 리스트 마지막 값보다 입력값이 크면 리스트에 저장, 작거나 같으면 리스트에 값을 변경

3. 2번의 과정을 입력값에 들어올 때마다 반복합니다.

4. 수열의 길이인 리스트의 크기를 결과로 출력합니다.

 

• BufferedReader를 사용하여 입력 값을 받았습니다.
• StringTokenizer를 이용해서 입력값들을 띄어쓰기 기준 나누었습니다.
• 이분탐색으로 리스트 값 변경하는 binarySearch함수를 만들었습니다.
• 리스트 마지막값과 입력값을 비교하여 리스트에 추가하거나 변경하도록 하였습니다.
• BufferedWriter에 증가하는 수열의 길이를 저장하였습니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

• binarySearch함수에서 이분탐색을 이용하여 리스트의 값들을 변경해주었습니다.

 

결과 코드

import java.io.*;
import java.util.*;
public class Main{
	static int size;		//입력값 개수
	static List<Integer> list = new ArrayList<Integer>();	//수열 표현하는 리스트
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //입력값 처리하는 BufferedReader
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        //결과값 출력하는 BufferedWriter
        //-----입력값 저장-------
        size = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        list.add(Integer.parseInt(st.nextToken()));
        //------수열 리스트 형성------
        for(int i=1;i<size;i++) {
        	int num = Integer.parseInt(st.nextToken());
        	if(list.get(list.size()-1)<num)
        		list.add(num);	//마지막 값보다 클 경우 수열 추가
        	else {
        		binarySearch(num);	//작거나 같을 경우 값 변경
        	}
        }
	//--------결과 저장 및 출력--------
        bw.write(list.size() + "\n");
        bw.flush();
        bw.close();
        br.close();
    }
    //-------이분 탐색으로 리스트 값 변경----
    public static void binarySearch(int num) {
    	int start = 0;
    	int end = list.size()-1;
    	while(start<=end) {
    		int median = (start + end)/2;
    		if(list.get(median)>num)
    			end = median - 1;
    		else if(list.get(median)==num)	//같은 값 있을 때
    			return;
    		else
    			start = median + 1;
    	}
    	list.set(start, num);	//리스트 값 변경
    }

}