오답노트 #2866 : 문자열 잘라내기

풀이방법 및 문제점

2022.02.05 (1)

예제 입력에 대한 출력값은 올바르게 나오지만 채점 결과는 틀렸다고 나오는 상황이 또 발생했다.

큰일이다...

문제점이 무엇인지 모르겠다. 채점 시 6%에서 틀렸습니다 가 나온다.

잠이 부족한 상태에서 풀다 보니 놓친 반례가 생긴 것일까? 단계별로 다시 차근차근 검토해보아야겠다.

 

사용한 풀이방법은 다음과 같다.

 

가장 위 한 줄을 잘라내면,

이번 차례에 비교대상이 되는 단어들은 모두

앞전에 비교대상이었던 단어들의 가장 앞 한 글자만 떼어낸 접미사이다.

 

Polynomial Hashing 기법을 사용하면 접미사를 빠르게 해싱할 수 있으므로,

Polynomial Hashing으로 모든 접미사들의 해싱을 미리 끝내둔 뒤,

그 해시값을 비교하며 count 값을 구하였다.

 

예를 들면 다음과 같다.

 

3 4
alfa
beta
zeta

위와 같은 입력이 주어졌다고 하자.

 

그럼 나는 다음과 같은 해시값 테이블을 만들면 된다.

※아래 표에서의 각 알파벳은 알파벳의 순서라고 정의한다. ex) a = 1, b = 2, ... , z = 26
※아래 표에서의 $x$는 해싱에 필요한 정수로, 코드에서는 27을 사용하였다.

a$x^2$ + b$x$ + z	l$x^2$ + e$x$ + e	f$x^2$ + t$x$ + t	a$x^2$ + a$x$ + a
b$x$ + z	e$x$ + e	t$x$ + t	a$x$ + a
z	e	t	a

 

그 후, 해시값 테이블의 행별로 중복값 유무를 판별하면서 count의 값을 알아내면 된다.

정수 count의 초기값은 0이다.

초기 테이블에는 무조건 중복값이 없다고 하였으므로 첫째 행은 비교할 필요가 없다.

(생각해보니 다음 코드 수정 시에는 아예 첫째 행의 해싱을 하지 않는 방향으로 바꾸어야겠다)

해시값 테이블의 둘째 행부터 시작해 아래 방향으로 진행한다.

해당 행에 중복값이 없다면 count를 1 증가시킨 뒤 다음 행으로 넘어간다.

해당 행에 중복값이 있다면 count를 증가시키지 않고 즉시 화면에 출력한 뒤 프로그램을 종료한다.

 

예시의 경우 진행과정은 다음과 같다.

 

먼저, 해시값 테이블의 둘째 행의 값들을 비교한다.

b$x$ + z

e$x$ + e

t$x$ + t

a$x$ + a

중복되는 값이 없으므로, count를 1 증가시킨다. 현재 count는 1이다.

 

그 다음 셋째 행의 값들을 비교한다.

z

e

t

a

중복되는 값이 없으므로 count를 1 증가시킨다. 현재 count는 2이다.

 

해시값 테이블의 마지막 행까지 비교가 끝났으므로, count 값인 2를 화면에 출력하고 프로그램을 종료한다.

 

코드

Java(2022.02.05(1))

import java.util.HashSet;
import java.util.Scanner;

public class Main {

	public static void main(String[] args){
		// TODO Auto-generated method stub
		
		Scanner sc = new Scanner(System.in);
		
		int r = sc.nextInt();	//행
		int c = sc.nextInt();	//열
		String[] input = new String[r];	//입력받은 데이터를 저장할 배열
		int[][] h = new int[r][c];	//해시값을 저장할 배열
		HashSet<Integer> hs = new HashSet<Integer>();	//count 값 도출 시 중복값 비교를 위한 해시셋
		
		//input에 길이가 c인 r개의 문자열을 저장.		
		for(int i = 0; i<r; i++) {
			input[i] = sc.next();
		}
		
		//해시값 테이블 채우기
		int x = 27;
		int pow = 0;
		int hashed = 0;
		for(int i = 0; i<c; i++) {
			for(int j = r-1; j>=0; j--) {
				hashed += (input[j].charAt(i) - 'a' + 1) * Math.pow(x, pow);
				h[j][i] = hashed;
				pow++;
			}
			hashed = 0;
			pow = 0;
		}
		
		//해시값을 비교하여 count값 도출하기(해시셋 이용)
		int count = 0;
		for(int i = 1; i<r; i++) {
			for(int j = 0; j<c; j++) {
				if(hs.contains(h[i][j])) {
					System.out.print(count);
					System.exit(0);
				}else {
					hs.add(h[i][j]);
				}
			}
			count++;
		}
		
		System.out.print(count);
		
		sc.close();
	}

}