BOJ_10840_구간 성분 (Java)

[Gold I] 구간 성분 - 10840

문제 링크

성능 요약

메모리: 226464 KB, 시간: 936 ms

분류

해싱

제출 일자

2024년 8월 4일 21:34:43

문제 설명

매 초마다 신호를 발생시키는 두 장치 A, B가 있다. 이 신호는 알파벳 소문자의 서열로 표현된다. A, B로부터 발생한 신호를 서열로 표시한 S_A, S_B의 예는 다음과 같다.

• S_A = [a, f, c, d, r, d, e, s, d, c, f, w, s, z, r]
• S_B = [g, e, d, s, r, d, d, e, m, z, r]

신호 서열의 어떤 구간에 포함된 문자의 종류와 개수가 순서에 상관없이 동일하면 이 두 ‘구간의 성분’은 같다고 한다. 아래에서 박스로 표시된 부분은 두 신호 S_A, S_B에서 성분이 같은 구간을 나타내고 있다.

즉 위의 예와 같이 성분이 같은 구간의 길이는 두 서열에서 반드시 같아야 한다. 그리고 같은 성분 의 구간은 하나 이상 존재할 수 있다. 우리는 두 신호 서열에 각각 존재하는 같은 성분 구간 중에 서 가장 긴 것을 찾으려고 한다.

입력

첫 두 줄에 신호 서열이 공백 없는 하나의 문자열로 각각 주어진다. 이 문자열은 영문 소문자로만 구성되어 있다. 두 입력 문자열의 크기 N, M의 범위는 1 ≤ N, M ≤ 1,500 이다.

출력

두 서열에서 같은 성분을 가진 구간 중에서 가장 긴 구간을 찾아, 그 구간의 길이를 출력해야 한다.

문제 풀이

코드

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

public class BOJ_10840_구간성분 {
	static BufferedReader br;
	static BufferedWriter bw;
	static String A, B;
	static boolean isExist = false; // A랑 B에 같은게 있는지 없는지 찾기 위한 변
	static long[] hashTable = new long[26]; // a~z를 31의 거듭제곱으로 표현
	public static void main(String[] args) throws IOException {
//		br = new BufferedReader(new InputStreamReader(System.in));
		br = new BufferedReader(new InputStreamReader(new FileInputStream("input.txt")));
		bw = new  BufferedWriter(new OutputStreamWriter(System.out));
		
		String s1 = br.readLine(); String s2 = br.readLine();
		if(s1.length() > s2.length()) {
			String tmp = s1;
			s1 = s2;
			s2 = tmp;
		}
		A = s1; B = s2; // A 가 B보다 항상 짧거나 같도록만듬.
		
		for(int i=0; i<26; i++) {
			if(i==0) hashTable[0] = 1;
			else hashTable[i] = 31 * hashTable[i-1];
		}
//		System.out.println(Arrays.toString(hashTable));
		
		int maxLen = 0;
		for(int i=1; i<=A.length(); i++) { // 작은문자열 기준 길이 1부터 그길이 자체까지 비교해봐야함 
			Set<Long> set_A = new HashSet<Long>();
			Set<Long> set_B = new HashSet<Long>();
			
			long hashVal_A = 0; long hashVal_B = 0;
			for(int j = 0; j<= B.length() - i; j++) {
				/**
				 * i 길이에 해당하는 만큼 hashVal 구하기
				 * 처음에 hash값 구하고 한칸씩 왼쪽 -1 오른쪽 +1 시키면서 중복부분 기억하여 계산 최적화 
				 * 
				 */
				if(j== 0) {
					hashVal_A = hash(A, i); 
					hashVal_B = hash(B, i);	
				} else {
					/**
					 * i길이만큼 자른것이 끝에 도달했는지 체크( unit의 끝 인덱스 j +i - 1, 원래 A의 인덱스 A.length() - 1
					 * A
					 * 빼줄 left = A.charAt(j-1) - 'a'
					 * 더해줄 right = A.charAt(j + (i - 1)) - 'a'
					 * 
					 * B
					 * 빼줄 left = B.charAt(j-1) - 'a'
					 * 더해줄 right = B.charAt(j + (i - 1)) - 'a' 
					 */
					if(j+(i-1) <= A.length() -1) { // 경계조건 check
						hashVal_A = hashVal_A - hashTable[A.charAt(j-1) - 'a'] + hashTable[A.charAt(j + (i - 1))-'a'];
					}
					
					hashVal_B =hashVal_B - hashTable[B.charAt(j-1) - 'a'] + hashTable[B.charAt(j + (i - 1))-'a'];
				}
				// 나온 hash값을 각 set_A와 set_B에 추가
				set_A.add(hashVal_A);
				set_B.add(hashVal_B);
			
			} // 길이별 해시값 추가 종료 
			
			// 이제 set_A길이 + set_B 길이가 A와 B 중복체크한 의 set과 원소 개수 같은지 check
			Set<Long> newSet = new HashSet<Long>();
			newSet.addAll(set_A);
			newSet.addAll(set_B);
			
			isExist = set_A.size() + set_B.size() == newSet.size() ? false : true;
			if(isExist) maxLen = i;
			
		} //  특정 길이별 계산 종료 
		
		bw.write(String.valueOf(maxLen));
		bw.flush();
		bw.close();
		br.close();

	}
	
	/**
	 * 해시값 만들기 - 카운팅 배열로 알파벳 개수 세고 그거 토대로 hash값을 hashTable값 곱해서 만들기
	 * 
	 * @param s
	 * @param l
	 * @return
	 */
	private static long hash(String s, int l) {
		long hash = 0;
		int[] count = new int[26];
		for(int i=0; i<l; i++) {
			count[s.charAt(i)- 'a']++;
		}
		for(int i=0; i< 26; i++) {
			hash += count[i] * hashTable[i];
		}
		return hash;
	}
}