[백준, Java] 2866번, 문자열 잘라내기(이분 탐색)

문제 링크

2866번: 문자열 잘라내기

---

주의사항

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

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

---

문제 설명

---

 

접근 방법

이 문제에 핵심

 

1. R × C 행렬에는 알파벳 소문자 원소가 존재합니다.

2. 문자열을 만들 때에는 가장 위의 행부터 아래로 내려가면서 문자열을 만듭니다.

3. 모든 열을 읽었을 때 중복되는 문자열이 없으면 가장 위의 행을 지우고 Count + 1을 진행합니다.

4. 중복되는 열이 존재하거나, 모든 행이 지워진 경우 Count의 값을 결과로 출력합니다.

5. 가장 처음에는 동일한 문자열을 가지는 행렬은 주어지지 않습니다.

 

알고리즘 진행 순서.

 

1. 입력된 정보를 저장합니다.

 

2. 이분탐색을 통해서 Count의 값을 탐색합니다.

 

3. 탐색한 Count의 값을 결과로 출력합니다.

 

이분탐색(Count 개수 구하기)

 

이분 탐색을 통해서 몇번째 행까지 지울 수 있는지 탐색합니다.

 

이분 탐색을 진행할 때에는 2가지 경우로 나뉘게 됩니다.

 

1. mid번째 행을 지울 때 중복되는 문자열이 존재할 때

 

더 작은 행을 지워야 한다.

 

end = mid - 1

 

 

2. mid번째 행을 지울 때 중복되는 문자열이 존재하지 않을 때

 

더 큰 행을 지울 수 있는지 확인해야 한다.

 

start = mid + 1

 

 

문자열이 중복되는지 확인할 때에는

 

mid가 지우는 행이기 때문에 mid + 1행부터 문자열을 만들어서 확인을 진행하시면 됩니다.

 

 

※예제 입력 과정을 살펴보시면 이해하시기 편하실 것입니다.

 

예제입력 3.

 

1. 입력된 정보를 저장합니다.

 

R : 4

 

C : 6

 

행렬

m	r	v	i	c	a
m	r	v	i	c	a
m	a	r	i	c	a
m	a	t	e	j	a

 

2. 이분탐색을 통해서 Count의 값을 탐색합니다.

 

이분탐색 진행

 

start = 0

 

end = 3(R-1)

 

mid = (0 + 3) ÷ 2 : 1

 

1번째 행까지 지울 경우.

 

m	r	v	i	c	a
m	r	v	i	c	a
m	a	r	i	c	a
m	a	t	e	j	a

문자열 : { mm, aa, rt, ie, cj, aa}

 

"aa"와"aa" 중복되기 때문에 1번째 열까지 지울 수 없습니다.

 

end = mid - 1 : 0

 

다음 이분 탐색 진행

 

start = 0

 

end = 0

 

mid = (0 + 0) ÷ 2 : 0

 

0번째 행까지 지울 경우.

 

m	r	v	i	c	a
m	r	v	i	c	a
m	a	r	i	c	a
m	a	t	e	j	a

문자열 : {mmm, raa, vrt, iie, ccj, aaa}

 

중복되는 문자열이 존재하지 않습니다.

 

start = mid + 1 : 1

 

start ≤ end으로써 이분탐색 종료!

 

3. 탐색한 Count의 값을 결과로 출력합니다.

 

이분탐색으로 얻은 Count : 1(start)

 

2을 결과로 출력합니다.

 

• BufferedReader를 사용하여 입력되는 정보를 저장합니다.
• StringTokenizer를 이용하여  행렬의 크기 정보를 띄어쓰기 기준 저장합니다.
• search함수를 Count의 값을 탐색합니다.
• 탐색을 통해 얻은 Count의 값을 BufferedWriter 저장합니다.
• BufferedWriter에 저장된 결과를 출력합니다.

• search함수는 이분탐색을 통해서 몇 번째 행까지 지울 수 있는지 탐색합니다.
• check함수는 mid만큼 지웠을 때 중복되는 문자열이 존재하는지 확인합니다.

결과코드

import java.io.*;
import java.util.*;

public class Main {
    //R × C 행렬
    static char[][] table;
    public static void main(String[] args) throws IOException {
        //입력값 처리하는 BufferedReader
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //결과값 출력하는 BufferedWriter
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        int R = Integer.parseInt(st.nextToken());
        int C = Integer.parseInt(st.nextToken());
        table = new char[R][C];
        //입력되는 행렬 값 저장
        for(int i=0;i<R;i++){
            String str = br.readLine();
            for(int j=0;j<C;j++){
                table[i][j] = str.charAt(j);
            }
        }
        //이분탐색을 통해서 Count 계산
        int result = search(R, C);
        //Count 값 BufferedWriter 저장
        bw.write(String.valueOf(result));
        bw.flush();		//결과 출력
        bw.close();
        br.close();
    }
    //이분 탐색을 통해서 몇 번째 행까지 지울 수 있는지 확인하는 함수
    static int search(int R, int C){
        int start = 0;
        int end = R - 1;
        //이분 탐색 진행
        while(start <= end){
            int mid = (start + end) / 2;
            //mid행까지 지울 수 있을 때
            if(check(mid, R, C)){
                start = mid + 1;
            }else{	//mid행까지 지울 수 없을 때
                end = mid - 1;
            }
        }
        return start;	//Count 값
    }
    //mid행까지 지웠을 때 중복되는 문자열이 존재하는지 확인하는 함수
    static boolean check(int mid, int R, int C){
        //중복을 확인하기 위한 Set
        HashSet<String> set = new HashSet<>();
        //mid + 1 행부터 문자열 만들기 진행
        for(int i=0;i<C;i++){
            StringBuilder str = new StringBuilder();
            //문자열 만들기
            for(int j=mid+1;j<R;j++){
                str.append(table[j][i]);
            }
            //중복되는 문자열이 있을 때
            if(set.contains(str.toString())){
                return false;
            }
            //문자열 추가
            set.add(str.toString());
        }
        return true;
    }
}