[백준] 28432번: 끝말잇기 JAVA

끝말잇기의 특성을 파악하여 문제를 해결할 수 있다.

 

문제

끝말잇기는 단어를 중복하지 않고 단어의 맨 끝 글자에 이어서 말하는 놀이입니다. 끝말잇기 기록은 단어들의 나열로 이루어집니다. 올바른 끝말잇기 기록은 각 단어의 마지막 글자가 다음 단어의 첫 글자이며, 단어가 중복되어서 나타나면 안 됩니다.

끝말잇기 기록이 주어지는데, 하나의 기록은 “?”로 가려진 채로 들어옵니다. “?”에 들어갈 수 있는 문자열들의 후보가 주어질 때, 올바른 끝말잇기 기록을 만드는 “?”에 들어갈 문자열을 출력하세요.

입력

첫째 줄에 n(5 ≤ n ≤ 40)이 주어진다.

첫 줄에 끝말잇기 기록의 길이 N 이 주어집니다. (1≤N≤100) 둘째 줄부터 다음 N개의 줄에는 끝말잇기의 기록 S_1,⋯, S_N이 한 줄에 하나씩 주어집니다. 여기서, 하나의 S_i는 “?” 로 주어집니다. 나머지 S_i는 길이 2 이상 10 이하의 영어 소문자로 이루어진 문자열입니다.

다음 줄에 후보 단어의 개수 M이 주어집니다. (1≤M≤100) 다음 M개의 줄에는 후보 단어 A_1,⋯,A_M이 주어집니다. A_i는 길이 2 이상 10 이하의 영어 소문자로 이루어진 문자열입니다. A_1,⋯,A_M은 서로 다릅니다.

문제의 답이 정확히 하나인 경우만 입력으로 주어집니다.

출력

“?”에 들어갈 수 있는 문자열을 후보 단어인 A_1,⋯, A_M 중에서 하나 찾아서 출력하세요.

https://www.acmicpc.net/problem/28432

28432번: 끝말잇기

접근

조건을 정리하자면 "?" 대신에 들어간 단어는 다음과 같다.

1. 중복단어 제외 조건

 이미 나온 단어라면 제외시킨다.

2. 끝말잇기 조건

 1) 물음표 이전 단어가 존재한다면, 이전 단어의 끝 알파벳과 현재 단어의 첫 알파벳이 같아야 한다.

 2) 물음표 다음 단어가 존재한다면, 다음 단어의 첫 알파벳과 현재 단어의 마지막 알파벳이 같아야 한다.

 

구현

1. 조건 생성

 1) 중복단어 제외를 위해 Set을 이용하여 이전 등록된 단어의 집합을 생성하였다.

//중복 검사를 위한 set
Set<String> words = new HashSet<String>();

//...생략...//

//중복 검사를 위해 단어를 set에 추가
words.add(word);

//...생략...//

 2) 이전 단어의 첫 알파벳과 끝 알파벳을 다음과 같이 구성하였다.

  - 현재 단어가 ? 표인가? => 물음표 등장 표시

  - 물음표가 등장하고, 끝 알파벳이 아직 정해지지 않았는가? => 현재 단어의 첫 알파벳을 끝 알파벳으로 지정

  - 물음표가 등장하지 않았는가? => 현재 단어의 끝 알파벳을 첫 알파벳으로 지정

//시작,끝 초기화
char start = '1';
char end = '1';
//? 출현 유무
boolean isQuestion = false;

//... 단어 탐색 조건 중...//

//물음표면 표시
if("?".equals(word)) {
    isQuestion =true;
//물음표 등장하고 아직 end가 초기화 상태라면 단어 맨 첫 알파벳으로 업데이트	
}else if(isQuestion&&end=='1') {
    end = word.charAt(0);
//물음표 등장하지 않았다면 start를 단어 맨 마지막 알파멧으로 업데이트	
}else if(!isQuestion) {
    start = word.charAt(word.length()-1);
}

//... 생략 ...//

 

2. 후보군 도출

 단어의 중복여부, 첫 알파벳과 끝 알파벳를 검사한다.

 1) 이미 나온 단어 검색

  - 이전에 등장한 단어라면 패쓰한다.

//기존에 출현한 단어라면 반복문 패쓰
if(words.contains(word)) continue;

 2) 첫 알파벳 검사

  - 시작 알파벳이 초기화 (맨 처음 물음표 등장 시)라면 통과

  - 시작 알파벳과 단어의 첫 알파벳이 동일하다면 통과

//시작 알파벳이 초기화 되어있거나, 단어 시작 알파벳과 동일한지 체크
boolean isRightStart = start=='1'||word.charAt(0)==start;

 

3) 끝 알파벳 검사

 - 끝 알파벳이 초기화 (맨 마지막 물음표 등장 시)라면 통과

 - 끝 알파벳과 단어의 마지막 알파벳이 동일하다면 통과

//끝 알파벳이 초기화 되어있거나, 단어 끝 알파벳과 동일한지 체크
boolean isRightEnd = end=='1'||word.charAt(word.length()-1)==end;

 

모든 조건이 만족되면 출력한다.

//중복되는 단어인 경우 이미 continue
//맨 앞 알파벳과 끝 알파벳이 조건을 만족하면 출력 후 종료
if(isRightStart&&isRightEnd) {
    System.out.println(word);
    break;
}

 

3. 전체 코드

 전체 코드는 다음과 같다.

package 백준;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.Set;

//https://www.acmicpc.net/problem/28432
public class 끝말잇기 {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		//시작,끝 초기화
		char start = '1';
		char end = '1';
		//? 출현 유무
		boolean isQuestion = false;
		//중복 검사를 위한 set
		Set<String> words = new HashSet<String>();
		//단어 입력
		int n = Integer.parseInt(br.readLine());
		for(int i=0;i<n;i++) {
			String word = br.readLine();
			//중복 검사를 위한 set 추가
			words.add(word);
			//물음표면 표시
			if("?".equals(word)) {
				isQuestion =true;
			//물음표 등장하고 아직 end가 초기화 상태라면 단어 맨 첫 알파벳으로 업데이트	
			}else if(isQuestion&&end=='1') {
				end = word.charAt(0);
			//물음표 등장하지 않았다면 start를 단어 맨 마지막 알파멧으로 업데이트	
			}else if(!isQuestion) {
				start = word.charAt(word.length()-1);
			}
		}
		//후보군 입력
		int m = Integer.parseInt(br.readLine());
		for(int i=0;i<m;i++){
			String word = br.readLine();
			//기존에 출현한 단어라면 패쓰
			if(words.contains(word)) continue;
			//시작 알파벳이 초기화 되어있거나, 단어 시작 알파벳과 동일한지 체크
			boolean isRightStart = start=='1'||word.charAt(0)==start;
			//끝 알파벳이 초기화 되어있거나, 단어 끝 알파벳과 동일한지 체크
			boolean isRightEnd = end=='1'||word.charAt(word.length()-1)==end;
			//맨 앞 알파벳과 끝 알파벳이 조건을 만족하면 출력 후 종료
			if(isRightStart&&isRightEnd) {
				System.out.println(word);
				break;
			}
		}
		br.close();
	}
}