[항해99 취업 리부트 코스 학습일지] 알고리즘 문제풀이

HEUKWU·2024년 3월 30일

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

문제

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

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

입력

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

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

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

출력

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

풀이

?에 해당하는 문자를 후보 단어 중에 고르면 되는데 단순하게 생각하면 ?이전 단어의 가장 마지막 문자, ?이후 단어의 가장 첫 번째 문자가 각 ?의 첫 번째 문자와 마지막 문자가 될 것이다.
이렇게 단순하면 정말 좋겠지만 문제에서 M의 범위는 1부터 주어지고 ?가 맨 처음에 주어질 수도, 맨 마지막에 주어질 수도 있다.
그리고 끝말잇기 기록에 이미 있는 단어는 정답이 될 수 없다.
조건 사항이 많아서 생각보다 까다로웠다.

먼저 처음 주어지는 단어들은 중복 체크를 해줘야 하므로 contains()메서드를 사용하기 위해 List에 넣어줬다. 그리고 ?의 인덱스 값을 unknownIndex변수에 할당해줬다.

List<String> words = new ArrayList<>();
int unknownIndex = 0;
for (int i = 0; i < n; i++) {
	String word = br.readLine();
	if (word.equals("?")) {
		unknownIndex = i;
	}
	words.add(word);
}

그리고 후보 단어들을 하나씩 받으면서 조건문을 통과시킨다. 여기서 주의해야 할 점이 있는데 N의 범위가 1부터 시작되기 때문에 N이 1일 때의 상황도 고려해야 한다. N이 1이라면 끝말잇기 기록으로 ? 하나만 주어진다는 의미로써 처음으로 들어오는 후보 단어를 출력해줘야 한다.

String candidate = br.readLine();

// ?만 주어졌을 때
if (n == 1) {
	System.out.println(candidate);
	break;
}

그리고 끝말잇기 기록이 담긴 List의 단어들에 해당 후보 단어가 이미 있는지 확인하는 조건문을 추가한다.

// 후보 단어가 기존 단어들과 중복될 때
if (words.contains(candidate)) {
	continue;
}

그리고 unkownIndex의 값이, 즉 ?가 주어진 위치가 처음인지 마지막인지 중간인지를 고려해서 조건문을 추가해준다.

구현 문제가 그렇듯 주어진 조건들을 충실하게 고려해준다면 어렵지 않게 풀 수 있는 문제였다.

최종 코드

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());

        List<String> words = new ArrayList<>();
        int unknownIndex = 0;
        for (int i = 0; i < n; i++) {
            String word = br.readLine();
            if (word.equals("?")) {
                unknownIndex = i;
            }
            words.add(word);
        }

        int m = Integer.parseInt(br.readLine());
        for (int i = 0; i < m; i++) {
            String candidate = br.readLine();

            // ?만 주어졌을 때
            if (n == 1) {
                System.out.println(candidate);
                break;
            }

            // 후보 단어가 기존 단어들과 중복될 때
            if (words.contains(candidate)) {
                continue;
            }

            // ?가 처음 주어졌을 때
            if (unknownIndex == 0) {
                String next = words.get(unknownIndex + 1);
                // ?의 마지막 문자 = 그 다음 단어의 첫번째 문자
                char lastChar = next.charAt(0);

                // 마지막 문자가 ?의 마지막 문자와 같을 때
                if (candidate.charAt(candidate.length() - 1) == lastChar) {
                    System.out.println(candidate);
                    break;
                }
            } // ?가 마지막에 주어졌을 때
            else if (unknownIndex == n - 1) {
                String prev = words.get(unknownIndex - 1);
                // ?의 첫번째 문자 = 그 전 단어의 마지막 문자
                char firstChar = prev.charAt(prev.length() - 1);

                // 첫번째 문자가 ?의 첫번째 문자와 같을 때
                if (candidate.charAt(0) == firstChar) {
                    System.out.println(candidate);
                    break;
                }
            } else {
                String prev = words.get(unknownIndex - 1);
                String next = words.get(unknownIndex + 1);
                char firstChar = prev.charAt(prev.length() - 1);
                char lastChar = next.charAt(0);

                if (candidate.charAt(0) == firstChar && candidate.charAt(candidate.length() - 1) == lastChar) {
                    System.out.println(candidate);
                    break;
                }
            }
        }
    }
}

항해99 취업 리부트 코스를 수강하고 작성한 콘텐츠 입니다.

HEUKWU

이전 포스트