[백준] 앵무새 (자바 풀이 - 큐, 배열, 해시맵을 곁들인)

 

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

 

 

📌 문제

자가용 비행기를 타고 세계 일주를 하던 pps789와 cseteram은 어느 날 엔진 고장으로 인해 이름 모를 섬에 불시착하게 된다. 그들은 이 섬을 탐험하는 도중 아주 신기한 사실을 알게 되었는데, 바로 이 섬에 사는 앵무새들은 놀라울 정도로 인간의 말을 흉내 내는 데 뛰어나다는 것이다. 그들은 서로 떨어져 섬을 탐험하기로 하였으며, 필요하다면 앵무새를 이용해 서로에게 연락하기로 약속하였다.

 

1개월 후, pps789는 섬의 비밀을 밝힐 결정적인 증거를 찾게 된다. 그는 이 세기의 대발견을 cseteram에게 공유하고자 하였으나, 그의 발견은 방대하여 앵무새 한 마리가 기억하기에는 너무 많은 양이었다. 그렇기 에 pps789는 앵무새 한 마리 대신 앵무새 N마리를 이용하여 자신의 발견을 기록하였으며, 이 앵무새들을 cseteram을 향해 날렸다.

 

한편 섬의 반대편에서 탐험을 계속하던 cseteram은 앵무새 N마리가 자신에게 날아와 각자 할 말을 하는 것을 보고 당황하였다. pps789가 긴 글을 전달하고 싶었던 것은 알아차렸지만, 각각의 앵무새들이 말하는 것을 차례대로 기록하다 보니 원문이 무엇인지 알 수 없을 정도로 단어의 순서가 엉켜버린 것이다. 대신 그는 관찰을 통해 몇 가지 규칙을 발견할 수 있었다.

1. 한 앵무새는 한 문장을 기억하고 있다. 문장은 여러 단어로 이루어져 있는데, 앵무새는 이 단어들을 순서대로 말한다.
2. 한 앵무새가 단어를 말하고 그다음 단어를 말하기 전에는 약간의 간격이 있는데, 이때 다른 앵무새가 말을 가로채고 자신의 문장을 말할 수 있다.
3. 한 앵무새가 단어를 말하는 도중에는, 다른 앵무새가 말을 가로채지 않는다.
4. 어떤 단어도 앵무새가 말하는 모든 문장을 통틀어 2번 이상 등장하지 않는다.

앵무새는 자신이 기억하고 있는 문장을 끝까지 말한 다음 pps789에게 돌아가며, cseteram은 모든 앵무새가 돌아갈 때 까지 단어를 받아적는다. pps789가 각각의 앵무새들에게 전달한 문장 Si와, cseteram이 받아 적은 문장 L이 주어진다. 이때 문장 L이 위 규칙들을 이용하여 나올 수 있는 문장인지 판별하시오.

⚔ 제한 사항

 

 

입력 

 

첫 번째 줄에 앵무새의 수 N (1 ≤ N ≤ 100) 이 주어진다.

 

두 번째 줄부터 N개의 줄에 걸쳐 각 앵무새가 말한 문장 Si (1 ≤ i ≤ N) 가 주어지는데, 각 문장을 이루는 단어는 스페이스 한 칸을 구분으로 하여 주어진다. 문장 Si를 이루는 단어의 수는 1개 이상 100개 이하이며, 각 단어는 1개 이상 32개 이하의 영문 소문자로 구성되어있다.

 

N + 2 번째 줄에는 cseteram이 받아 적은 문장 L이 주어진다. 문장 L을 이루는 단어의 수는 1개 이상 10000개 이하이며, 각 단어는 1개 이상 32개 이하의 영문 소문자로 구성된다.

 

 

출력 

 

문장 L이 가능한 문장이라면 Possible을, 불가능한 문장이라면 Impossible을 출력한다.

 

 

예제 입출력

 

1. 

 

3
i want to see you
next week
good luck
i want next good luck week to see you

 

Possible

 

2. 

 

2
i found
an interesting cave
i found an cave interesting

 

Impossible

 

 

👀 문제 해석

이 문제는 앵무새들이 말한 문장의 순서를 추적하여 주어진 문장 L이 올바르게 만들어졌는지를 판단하는 문제이다. 요구사항을 먼저 생각해보면 문자열 처리가 필요할 것이고, 문자열들에 대해 적절한 탐새과 판단이 필요하므로 자료 구조를 잘 사용하면 좋을 것 같다.

 

주어진 조건을 살펴보면, 각 앵무새가 기억한 문장이 있다. 각 문장은 여러 단어로 이루어져 있으며, 앵무새는 자신의 문장을 순서대로 말한다. 하지만 한 앵무새가 단어를 말하는 도중 다른 앵무새가 말을 가로채어 자신의 문장을 이어서 말할 수 있다. 이때 어떤 단어도 중복되지 않으며, 문장의 순서가 유지되어야 한다는 점을 주목해보자.

 

이 문제는 단순히 주어진 문장 L과 앵무새들의 문장을 하나하나 비교하는 것이 아니라, 여러 앵무새의 문장들이 엉켜서 나왔을 수 있는지를 판별하는 문제이다. 각 앵무새가 말할 수 있는 단어의 순서를 지키면서 문장 L을 만들 수 있느냐를 묻고 있기 때문에, 문제의 본질은 자료 구조(큐 또는 리스트)를 활용하여 각 앵무새가 말한 문장의 순서를 처리하고, 주어진 검증 문장 L과 매칭해 나가는 과정을 요구하고 있다.

 

시간 복잡도를 생각해보면, 주어지는 데이터의 크기가 앵무새의 수 N이 최대 100이고, 검증해야 하는 문장 L의 단어 수가 최대 10,000개라고 했을 때, 최악의 경우 모든 단어에 대해 각각의 앵무새가 말할 수 있는지 확인한다면, 단순히 O(L * N)이 되며, 이는 최대 100만 번의 연산을 의미한다.

 

100만 번의 연산은 일반적인 시간 제한(1초에서 2초) 내에서 충분히 처리할 수 있는 수준이기 때문에, 이러한 시간 복잡도로도 문제는 적절하게 해결될 수 있을 것으로 보인다.

🔎 접근

이 문제를 풀기 위해 가장 먼저 떠오르는 방법은 큐(Queue) 자료구조를 활용하는 것이다. 큐는 FIFO(First In First Out)의 특성을 가지고 있어, 각 앵무새가 말한 문장을 순차적으로 처리하는 데 적합하지 않을까? 앵무새가 말할 수 있는 단어들을 큐에 넣어두고, 검증해야 하는 문장의 단어와 일치하는지 차례대로 확인하는 방식이다.

 

주어진 문장 L은 여러 앵무새의 발언이 섞여 나온 것인데, 이는 마치 여러 개의 줄을 병렬적으로 처리하는 상황과 비슷하다. 각 앵무새는 자신의 줄에 있는 단어를 순서대로 말하고 있으므로, 각 앵무새의 발언을 큐로 관리하면 어떨까.

 

각 앵무새가 말한 문장을 큐로 변환하고, 각 앵무새가 말할 수 있는 단어를 순차적으로 확인한 후 주어진 문장 L에서 그 단어가 일치하는지 체크하는 것이다. 만약 단어가 일치하면 큐에서 그 단어를 제거하고, 그렇지 않으면 다른 앵무새의 큐를 확인한다.

 

이때, 중요한 것은 단어의 순서이다. 앵무새가 말하는 순서가 섞여 있을 수 있지만, 각 앵무새 내부에서는 자신이 기억한 문장의 순서를 지켜야 한다. 따라서, 큐에 저장된 단어의 순서가 유지되면서 문장 L과 매칭되는지 확인하는 것이 필요하다.

 

이제, 조금 더 구체적으로 큐를 어떻게 사용할지 생각해보자.

1. 앵무새가 말한 문장들을 큐로 변환한다. 각 앵무새가 말한 문장을 단어 단위로 나누고, 그 단어들을 큐에 넣는다. 이로써 각 앵무새가 말할 수 있는 단어들이 차례로 대기하게 된다.
2. 검증 문장 L의 각 단어를 처리한다. 문장 L의 각 단어를 하나씩 확인하면서, 각 앵무새 큐에서 꺼낸 단어와 비교한다. 만약 일치하는 단어가 있으면 그 단어를 큐에서 제거하고, 다음 단어를 확인한다.
3. 일치하는 단어가 없는 경우: 만약 어떤 앵무새도 현재 단어를 말하지 않았다면, 이는 불가능한 문장이므로 바로 "Impossible"을 반환한다.
4. 모든 단어가 일치하는 경우: 문장 L의 모든 단어가 앵무새들이 말한 순서대로 처리되었다면, 이는 가능한 문장이므로 "Possible"을 반환한다.

시간 복잡도는 어떨까? 각 단어를 처리하는 데 각 앵무새의 큐를 확인하는 연산을 반복하므로, 시간 복잡도는 O(L * N)이 될 것이다. 즉, 100만 번의 연산으로 주어진 제약 사항 내에서 충분히 처리할 수 있는 범위이다.

💡 풀이 코드

이제 풀이 코드를 작성해보자.

 

먼저, 큐(Queue)를 이용해 각 앵무새가 말하는 단어들을 순서대로 처리하는 방법이다.

1. 입력 처리 및 큐 초기화

int 앵무새개수 = Integer.parseInt(br.readLine());
ArrayList<String> 앵무새가말한문장들 = new ArrayList<>();
while (앵무새개수-->0){
    앵무새가말한문장들.add(br.readLine());
}

 

우선, 백준 문제 특성에 따라 입력을 잘 받아서 정제해주어야 한다. 첫 번째 줄에서 앵무새의 수를 입력받고, 각 앵무새가 말한 문장을 ArrayList<String>에 저장하자. 이후, 각 앵무새의 문장을 나중에 큐로 변환할 것이다.

2. 앵무새별 큐 생성

ArrayDeque<String>[] 앵무새별큐 = new ArrayDeque[앵무새가말한문장들.size()];
for (int i = 0; i < 앵무새별큐.length; i++) {
    앵무새별큐[i] = new ArrayDeque<>();
}

앵무새들의 문장을 각각 큐로 관리하기 위해 ArrayDeque<String>[] 배열을 생성한다. 이 배열의 각 요소는 하나의 앵무새가 말할 단어를 저장하는 큐가 된다. 이후 각 앵무새의 문장을 큐에 추가한다.

 

이렇게 병렬 큐를 사용하는 방식이 꽤 자주 사용된다.

3. 큐에 각 앵무새 문장 저장

for (int i = 0; i < 앵무새가말한문장들.size(); i++) {
    StringTokenizer stringTokenizer = new StringTokenizer(앵무새가말한문장들.get(i));
    while (stringTokenizer.hasMoreTokens()) {
        앵무새별큐[i].add(stringTokenizer.nextToken());
    }
}

 

StringTokenizer를 사용해 각 앵무새의 문장을 단어로 나누고, 해당 단어들을 큐에 넣는다. 예를 들어, 입력된 앵무새 문장이 "i want to see you"라면, 앵무새별큐[0]은 다음과 같이 저장된다.

 

앵무새별큐[0]: ["i", "want", "to", "see", "you"]

 

이 과정을 각 앵무새에 대해 반복하여, 모든 앵무새의 큐가 초기화된다.

 

앵무새별큐[0]: ["i", "want", "to", "see", "you"]
앵무새별큐[1]: ["next", "week"]
앵무새별큐[2]: ["good", "luck"]

4. 검증 문장 처리

StringTokenizer stringTokenizer = new StringTokenizer(검증해야하는문장);
while (stringTokenizer.hasMoreTokens()) {
    String 단어 = stringTokenizer.nextToken();

    boolean 단어match = false;
    for (int i = 0; i < 앵무새별큐.length; i++) {
        if (단어.equals(앵무새별큐[i].peek())) {
            앵무새별큐[i].pop();
            단어match = true;
            break;
        }
    }

    if (!단어match) {
        return "Impossible";
    }
}

 

이제 검증해야 하는 문장 L의 각 단어를 순서대로 확인하는 단계이다. 각 단어에 대해 순회하면서, 모든 앵무새의 큐 중 현재 peek()한 단어와 일치하는지 확인한다. 일치하면 해당 단어를 큐에서 제거(pop())하고, 다음 단어로 넘어간다.

 

이 부분이 알고리즘의 핵심이다. 큐의 선입선출(FIFO) 구조를 활용해 각 앵무새가 말한 순서를 유지하면서, 검증 문장 L에서 각 단어를 순차적으로 확인한다.

 

이 부분이 알고리즘의 핵심이다. 다음과 같은 예시를 살펴보자.

 

검증해야 하는 다음과 같은 문장에 대해서,

"i want next good luck week to see you"

 

각 앵무새의 초기화된 큐 상태는 다음과 같다.

앵무새별큐[0]: ["i", "want", "to", "see", "you"]
앵무새별큐[1]: ["next", "week"]
앵무새별큐[2]: ["good", "luck"]

 

이제 문장 L의 단어를 순차적으로 확인하고, 각 큐에서 해당 단어를 처리하는 과정을 단계별로 살펴보면,

1. 첫 번째 단어: "i"
   • "i"는 앵무새 0의 큐의 첫 번째 단어이므로, 앵무새별큐[0].peek()가 "i"와 일치한다.
   • 따라서 "i"는 앵무새 0에서 pop()되고, 큐는 다음과 같이 변한다.

     앵무새별큐[0]: ["want", "to", "see", "you"]

2. 두 번째 단어: "want"
   • "want" 역시 앵무새 0의 큐에서 찾을 수 있다(앵무새별큐[0].peek() = "want").
   • "want"는 pop()되고, 앵무새 0의 큐 상태는

     앵무새별큐[0]: ["to", "see", "you"]

3. 세 번째 단어: "next"
   • "next"는 앵무새 0의 큐에는 없지만, 앵무새 1의 큐에서 찾을 수 있다(앵무새별큐[1].peek() = "next").
   • "next"는 앵무새 1의 큐에서 pop()되고, 큐는 다음과 같이 변한다.

     앵무새별큐[1]: ["week"]

4. 네 번째 단어: "good"
   • "good"은 앵무새 2의 큐에서 찾을 수 있다(앵무새별큐[2].peek() = "good").
   • "good"은 pop()되고, 큐는 다음과 같이 변한다.

     앵무새별큐[2]: ["luck"]

5. 다섯 번째 단어: "luck"
   • "luck"은 앵무새 2의 큐에서 pop()된다.

     앵무새별큐[2]: []

6. 여섯 번째 단어: "week"
   • "week"은 앵무새 1의 큐에서 pop()된다.

     앵무새별큐[1]: []

7. 일곱 번째 단어: "to"
   • "to"는 다시 앵무새 0의 큐에서 찾을 수 있다.

     앵무새별큐[0]: ["see", "you"]

8. 여덟 번째 단어: "see"
   • "see"는 앵무새 0의 큐에서 찾을 수 있다.

     앵무새별큐[0]: ["you"]

9. 아홉 번째 단어: "you"
   • 마지막으로 "you"도 앵무새 0의 큐에서 pop()된다.

     앵무새별큐[0]: []

 

이렇게 검증 문장 L의 모든 단어를 처리할 수 있다. 이 과정에서 각 단어가 적절한 큐에서 매칭되었고, 큐에서 pop()되었다. 모든 단어가 앵무새들이 말한 순서대로 나왔으므로 최종적으로 "Possible"을 반환한다.

 

여기서 또 한가지 핵심은 단어에 대한 matching 여부를 판단하는 로직이다.

 

만약 특정 단어에서 어느 앵무새의 큐에서도 찾을 수 없었다면, 단어match는 false로 유지되고, 이때 즉시 "Impossible"을 반환한다. 예를 들어, 검증 문장에 "pineapple"이라는 단어가 있었다면, 어느 앵무새의 큐에도 없기 때문에 Impossible을 반환한다.

 

단어가 matching에 실패하는 경우인 "i want to see pineapple"인 경우도 생각해 보자.

• "i", "want", "to", "see"까지는 정상적으로 매칭되지만, "pineapple"은 어느 큐에도 존재하지 않기 때문에 단어match = false가 되고, 즉시 "Impossible"을 반환한다.

즉, 문장 L에서 일치하지 않는 단어가 나오면 그 즉시 종료된다.

 

5. 모든 단어 처리 후 추가 확인

마지막으로 확인해주어야 하는 로직은 큐에 남아 있는지 여부이다.

for (ArrayDeque<String> 큐 : 앵무새별큐) {
    if (!큐.isEmpty()) {
        return "Impossible";
    }
}

만약 앵무새 큐에 남은 단어가 있다면, 이는 문장 L이 올바르게 만들어지지 않은 것이다. 왜일까? 문제의 요구 사항에 따르면 모든 앵무새는 자신이 기억하고 있는 문장을 끝까지 말한 후 pps789에게 돌아간다고 명시되어 있다. 이 말은 즉, 모든 앵무새는 자신이 기억하는 문장을 빠짐없이 다 말해야 하며, 문장 L에 등장하지 않은 단어가 앵무새의 큐에 남아 있다면 그 문장은 올바른 문장이 될 수 없다는 의미다.

 

따라서 마지막 단계에서 각 큐가 비어 있는지 확인함으로써, 문장 L이 앵무새들이 말한 모든 문장을 제대로 포함하고 있는지 최종적으로 검증하게 된다.

6. 최종 결과 반환

모든 조건을 만족하면 "Possible", 그렇지 않으면 "Impossible"을 반환한다.

return "Possible";

 

🤔 음, 그런데 다른 방법은 없을까?

위와 같은 큐를 이용한 풀이로 통과할 수 있는데, 좀 더 개선할 방법이 없을까?

 

문제의 제한에 따라서 O(L * N) 시간복잡도로 충분히 풀리지만 조금 더 최적화할 수 있는지 생각해보자.

 

첫 번째로 생각해볼 다른 방식은 배열의 인덱스를 관리하는 방식이다.

 

문제에서 중요한 것은 각 앵무새가 말하는 순서를 유지하면서 주어진 문장 L과 매칭하는 것이므로, 큐 대신 배열과 인덱스를 이용하여 각 앵무새가 말한 단어의 현재 위치를 추적하는 방법을 생각해볼 수 있을 것이다.

1) 배열을 이용한 접근 방식

배열을 이용한 방식은 각 앵무새의 문장을 배열에 저장하고, 해당 배열의 인덱스를 추적하여 앵무새가 말할 수 있는 다음 단어를 확인하는 방식이다. 이 방법은 큐를 사용하는 것과 동일한 논리를 따른다. 왜냐면 큐의 내부 동작을 살펴보면, 결국 배열의 인덱스를 조정하는 것으로 ADT를 구현한 것이기 때문이다. 따라서 직접 배열과 인덱스를 사용하여 문제를 해결하는 방법이 큐보다 간단할 수 있다.

 

아이디어는 간단하다.

1. 각 앵무새의 문장을 리스트로 저장하고, 각 앵무새에 대한 현재 단어 위치를 추적할 수 있는 인덱스 배열을 사용한다. 이 인덱스 배열은 각 앵무새가 다음으로 말할 단어의 위치를 나타낸다.
2. 검증해야 하는 문장의 각 단어에 대해, 모든 앵무새의 현재 위치에 있는 단어와 비교한다. 단어가 일치하면 해당 앵무새의 인덱스를 증가시켜 다음 단어로 이동한다.
3. 일치하는 단어가 없으면 "IMPOSSIBLE"을 반환하고, 모든 단어가 일치하는 경우 "POSSIBLE"을 반환한다.

마찬가지로 위에서 사용한 예시를 그대로 사용해서 살펴보자.

• 앵무새 문장들:
  1. "i want to see you"
  2. "next week"
  3. "good luck"
• 검증해야 하는 문장: "i want next good luck week to see you"

먼저 앵무새 문장들을 리스트로 저장한다.

 앵무새문장[0] = ["i", "want", "to", "see", "you"]
 앵무새문장[1] = ["next", "week"]
 앵무새문장[2] = ["good", "luck"]

 

이때 인덱스 배열을 초기화는 [0, 0, 0] 으로 각 앵무새의 현재 단어 위치를 나타낸다.

 

그 다음, **검증 문장의 각 단어를 처리하는 과정을 살펴보자.

• 첫 번째 단어 "i"를 확인:
  • 앵무새 0의 현재 단어 "i"와 일치 (인덱스 0), 그래서 인덱스를 1로 증가 ([1, 0, 0])
• 두 번째 단어 "want"를 확인:
  • 앵무새 0의 현재 단어 "want"와 일치 (인덱스 1), 인덱스를 2로 증가 ([2, 0, 0])
• 세 번째 단어 "next"를 확인:
  • 앵무새 1의 현재 단어 "next"와 일치 (인덱스 0), 인덱스를 1로 증가 ([2, 1, 0])
• 네 번째 단어 "good"을 확인:
  • 앵무새 2의 현재 단어 "good"과 일치 (인덱스 0), 인덱스를 1로 증가 ([2, 1, 1])
• 다섯 번째 단어 "luck"을 확인:
  • 앵무새 2의 현재 단어 "luck"과 일치 (인덱스 1), 인덱스를 2로 증가 ([2, 1, 2])
• 여섯 번째 단어 "week"을 확인:
  • 앵무새 1의 현재 단어 "week"과 일치 (인덱스 1), 인덱스를 2로 증가 ([2, 2, 2])
• 일곱 번째 단어 "to"를 확인:
  • 앵무새 0의 현재 단어 "to"와 일치 (인덱스 2), 인덱스를 3으로 증가 ([3, 2, 2])
• 여덟 번째 단어 "see"를 확인:
  • 앵무새 0의 현재 단어 "see"와 일치 (인덱스 3), 인덱스를 4로 증가 ([4, 2, 2])
• 아홉 번째 단어 "you"를 확인:
  • 앵무새 0의 현재 단어 "you"와 일치 (인덱스 4), 인덱스를 5로 증가 ([5, 2, 2])

그리고 모든 단어를 검증 완료 후 "POSSIBLE" 반환한다.

 

시간 복잡도는 어떨까? 문장 초기화 단계는 모든 단어 수에 대해 순회하므로 O(M)으로 큐 방식과 동일하다. 그렇다면 검증 단계는? 마찬가지로 각 단어에 대해 최대 N개의 앵무새를 확인하므로 O(L * N) 이다. 결국 큐와 동일하다.

 

하지만 장점이라고 한다면 큐 대신 배열과 인덱스만으로 해결하므로 큐 자료구조를 사용하지 않아도 되고, 메모리 사용량이 줄어들 수 있을 것이다.

 

하지만 결국 시간 복잡도는 동일하므로 개선이라고 하기는 힘들 것이다. 다른 방법을 고려해보자.

2) 해시맵을 사용해서 추적하고 탐색하는 방법

탐색을 최적화하기 위해 해시맵(HashMap) 자료구조를 사용해보면 어떨까?

 

아이디어는 다음과 같다.

1. 해시맵을 사용하여 각 단어가 위치할 수 있는 앵무새들을 저장한다. 해시맵의 키는 단어이고, 값은 해당 단어를 현재 위치에서 말할 수 있는 앵무새의 인덱스 리스트이다.
2. 각 앵무새의 문장을 리스트로 유지하고, 현재 위치를 인덱스로 추적한다. 각 앵무새가 말할 수 있는 단어가 변경될 때마다 해시맵을 업데이트하여, 현재 단어를 키로 하고 가능한 앵무새의 인덱스를 값으로 저장한다.
3. 검증해야 하는 문장의 단어를 순서대로 해시맵에서 탐색한다. 해시맵에 해당 단어가 있는 경우, 그 단어를 말할 수 있는 앵무새들 중 하나를 선택하여 현재 단어 위치를 업데이트한다. 단어를 처리한 후 해시맵에서 해당 단어를 말할 수 있는 앵무새를 제거하고, 다음 단어를 말할 수 있는 상태로 해시맵을 갱신한다.

동일한 예제 입력으로 데이터 흐름을 살펴보자.

1. 초기화 단계

각 앵무새의 문장을 리스트로 저장한 뒤, 해시맵에 첫 번째 단어를 말할 수 있는 앵무새의 인덱스를 저장한다.

Map<String, Integer> 단어별앵무새맵 = new HashMap<>();
for (int i = 0; i < N; i++) {
    if (앵무새문장[i].size() > 0) {
        String word = 앵무새문장[i].get(0);
        단어별앵무새맵.put(word, i);  // 첫 번째 단어와 그 단어를 말할 수 있는 앵무새 인덱스 저장
    }
}

 

예를 들어, 앵무새들의 문장이 다음과 같다고 할 때,

앵무새문장[0] = ["i", "want", "to", "see", "you"]
앵무새문장[1] = ["next", "week"]
앵무새문장[2] = ["good", "luck"]

 

초기화된 해시맵은 다음과 같다.

해시맵: {
  "i": 0,
  "next": 1,
  "good": 2
}

 

여기서 배열과 큐와 다른 점은 여기서 배열과 큐와 다른 점은, 해시맵을 사용해 각 단어가 어느 앵무새에서 말할 수 있는지를 즉시 탐색할 수 있다는 점이다. 배열이나 큐를 사용하는 방법에서는 각 단어를 찾기 위해 순차적으로 모든 앵무새의 현재 위치를 확인해야 했다. 하지만 해시맵을 사용하면, 단어를 해시맵에서 O(1) 시간 복잡도로 빠르게 찾을 수 있다.

 

2. 단어 매칭 과정

검증 문장의 각 단어를 해시맵에서 찾고, 해당 단어를 말할 수 있는 앵무새를 확인한 뒤 처리한다. 처리된 단어는 해시맵에서 제거하고, 해당 앵무새가 말할 수 있는 다음 단어를 해시맵에 추가한다.

while (st.hasMoreTokens()) {
    String 단어 = st.nextToken();
    if (단어별앵무새맵.containsKey(단어)) {
        int 앵무새번호 = 단어별앵무새맵.get(단어);  // 해당 단어를 말할 수 있는 앵무새의 번호 가져오기
        앵무새인덱스[앵무새번호]++;  // 앵무새의 인덱스 증가

        단어별앵무새맵.remove(단어);  // 현재 단어는 처리되었으므로 해시맵에서 제거

        // 다음 단어를 해시맵에 추가
        if (앵무새인덱스[앵무새번호] < 앵무새문장[앵무새번호].size()) {
            String 다음단어 = 앵무새문장[앵무새번호].get(앵무새인덱스[앵무새번호]);
            단어별앵무새맵.put(다음단어, 앵무새번호);
        }
    } else {
        return "Impossible";  // 단어를 말할 수 있는 앵무새가 없으면 불가능
    }
}

 

데이터 흐름을 살펴보면 다음과 같다.

 

먼저 첫 번째 단어 "i"를 해시맵에서 찾는다.

• "i"는 앵무새 0이 말할 수 있으므로, 앵무새 0의 인덱스를 1로 업데이트하고, 해시맵에서 "i"를 제거한다.
• 다음 단어 "want"를 해시맵에 추가한다.

       해시맵: {
         "want": [0],
         "next": [1],
         "good": [2]
       }

그 다음, 두 번째 단어 "want"를 해시맵에서 찾는다.

• "want"는 앵무새 0이 말할 수 있으므로, 앵무새 0의 인덱스를 2로 업데이트하고, "want"를 해시맵에서 제거한다.
• 다음 단어 "to"를 해시맵에 추가한다.

   ```
   해시맵: {
     "to": [0],
     "next": [1],
     "good": [2]
   }
   ```

이와 같은 방식으로 나머지 단어들도 처리한다.

 

모든 단어가 처리된 후 해시맵이 비어있고, 각 앵무새의 인덱스가 자신이 말한 문장의 끝에 도달한 경우라면, 주어진 문장 L은 가능한 문장이므로 "Possible"을 반환한다. 만약 어느 앵무새라도 처리하지 않은 단어가 남아 있으면 "Impossible"을 반환한다.

 

이렇게 했을 때의 전체 시간 복잡도는 어떻게 될까?

1. 해시맵에서 단어를 찾고 업데이트하는 작업은 각각 O(1) 시간 복잡도이다.
2. 검증 문장 L의 각 단어를 처리하는 데 L개의 단어가 있고, N개의 앵무새가 말한 문장을 관리하는 상황이다. 따라서 검증 문장의 단어 하나당 해시맵에서 해당 단어를 처리하는 연산이 발생하며, 각 연산은 O(1) 시간에 수행된다.

결론적으로, 전체 알고리즘의 시간 복잡도는 O(L) 로, 기존의 배열이나 큐를 사용한 방식보다 더 개선된다. 백준에서 제출해보면 다음과 같이 미세하게 좀 더 빠르게 확인이 된다. 데이터셋이 많지 않아 크게 드라마틱한 차이는 나지 않는 것 같다. 

 

 

 

 

☘️ 전체 코드 

 

package template.Boj;

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.StringTokenizer;

import org.junit.jupiter.api.Assertions;
import org.junit.jupiter.api.Test;

public class Main {

    public static void main(String[] args) throws IOException {
        System.setIn(new FileInputStream("fundamentals/src/test/java/template/Boj/input.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int 앵무새개수 = Integer.parseInt(br.readLine());

        ArrayList<String> 앵무새가말한문장들 = new ArrayList<>();
        while (앵무새개수-->0){
            앵무새가말한문장들.add(br.readLine());
        }

        String 검증해야하는문장 = br.readLine();

        System.out.println(가능여부판단하기(앵무새가말한문장들, 검증해야하는문장));
    }



    // private static String 가능여부판단하기(ArrayList<String> 앵무새가말한문장들, String 검증해야하는문장) {
    //
    //      ArrayDeque<String>[] 앵무새별큐 = new ArrayDeque[앵무새가말한문장들.size()];
    //      for(int i = 0; i<앵무새별큐.length; i++){
    //          앵무새별큐[i]=new ArrayDeque<>();
    //      }
    //
    //     for (int i = 0; i < 앵무새가말한문장들.size(); i++ ){
    //         StringTokenizer stringTokenizer = new StringTokenizer(앵무새가말한문장들.get(i));
    //
    //         while(stringTokenizer.hasMoreTokens()){
    //             앵무새별큐[i].add(stringTokenizer.nextToken());
    //         }
    //     }
    //
    //     StringTokenizer stringTokenizer = new StringTokenizer(검증해야하는문장);
    //
    //     while (stringTokenizer.hasMoreTokens()) {
    //         String 단어 = stringTokenizer.nextToken();
    //
    //         boolean 단어match = false;
    //         for (int i = 0; i < 앵무새별큐.length; i++) {
    //             if (단어.equals(앵무새별큐[i].peek())) {
    //                 앵무새별큐[i].pop();
    //                 단어match = true;
    //                 break;
    //             }
    //         }
    //
    //         if (!단어match) {
    //             return "Impossible";
    //         }
    //     }
    //
    //     // 모든 앵무새의 큐가 비었는지 확인
    //     for (ArrayDeque<String> 큐 : 앵무새별큐) {
    //         if (!큐.isEmpty()) {
    //             return "Impossible";
    //         }
    //     }
    //
    //
    //     return "Possible";
    // }

    private static String 가능여부판단하기(ArrayList<String> 앵무새가말한문장들, String 검증해야하는문장) {

        int N = 앵무새가말한문장들.size();

        List<String>[] 앵무새문장 = new List[N];
        int[] 앵무새인덱스 = new int[N];

        for (int i = 0; i < N; i++) {
            String[] words = 앵무새가말한문장들.get(i).split("\\s+");
            앵무새문장[i] = new ArrayList<>(Arrays.asList(words));
            앵무새인덱스[i] = 0;
        }

        // 현재 각 앵무새가 말할 수 있는 단어를 해시맵에 저장하기
        Map<String, Integer> 단어별앵무새맵 = new HashMap<>();

        for (int i = 0; i < N; i++) {
            if (앵무새문장[i].size() > 0) {
                String word = 앵무새문장[i].get(0);
                단어별앵무새맵.put(word, i);
            }
        }

        StringTokenizer st = new StringTokenizer(검증해야하는문장);

        while (st.hasMoreTokens()) {
            String 단어 = st.nextToken();

            if (단어별앵무새맵.containsKey(단어)) {
                int 앵무새번호 = 단어별앵무새맵.get(단어);

                앵무새인덱스[앵무새번호]++;

                단어별앵무새맵.remove(단어);

                // 앵무새가 말할 다음 단어가 있다면 해시맵에 추가
                if (앵무새인덱스[앵무새번호] < 앵무새문장[앵무새번호].size()) {
                    String 다음단어 = 앵무새문장[앵무새번호].get(앵무새인덱스[앵무새번호]);
                    단어별앵무새맵.put(다음단어, 앵무새번호);
                }
            } else {
                return "Impossible";
            }
        }

        for (int i = 0; i < N; i++) {
            if (앵무새인덱스[i] != 앵무새문장[i].size()) {
                return "Impossible";
            }
        }

        return "Possible";
    }



    @Test
    public void testEdgeCases() {
        // 예제 입력 1: 가능한 경우
        ArrayList<String> 앵무새문장1 = new ArrayList<>();
        앵무새문장1.add("i want to see you");
        앵무새문장1.add("next week");
        앵무새문장1.add("good luck");
        String 검증문장1 = "i want next good luck week to see you";
        Assertions.assertEquals("Possible", 가능여부판단하기(앵무새문장1, 검증문장1));

        // 예제 입력 2: 불가능한 경우
        ArrayList<String> 앵무새문장2 = new ArrayList<>();
        앵무새문장2.add("i found");
        앵무새문장2.add("an interesting cave");
        String 검증문장2 = "i found an cave interesting";
        Assertions.assertEquals("Impossible", 가능여부판단하기(앵무새문장2, 검증문장2));

        // 예제 입력 3: 불가능한 경우
        ArrayList<String> 앵무새문장3 = new ArrayList<>();
        앵무새문장3.add("please");
        앵무새문장3.add("be careful");
        String 검증문장3 = "pen pineapple apple pen";
        Assertions.assertEquals("Impossible", 가능여부판단하기(앵무새문장3, 검증문장3));

        // 추가 테스트 케이스 1: 가능한 경우
        ArrayList<String> 앵무새문장4 = new ArrayList<>();
        앵무새문장4.add("hello world");
        앵무새문장4.add("java programming");
        String 검증문장4 = "hello java world programming";
        Assertions.assertEquals("Possible", 가능여부판단하기(앵무새문장4, 검증문장4));

        // 추가 테스트 케이스 2: 불가능한 경우 (순서가 다름)
        ArrayList<String> 앵무새문장5 = new ArrayList<>();
        앵무새문장5.add("start");
        앵무새문장5.add("coding now");
        String 검증문장5 = "start now coding";
        Assertions.assertEquals("Impossible", 가능여부판단하기(앵무새문장5, 검증문장5));

        // 추가 테스트 케이스 3: 가능한 경우 (단어가 정확히 일치)
        ArrayList<String> 앵무새문장6 = new ArrayList<>();
        앵무새문장6.add("go");
        앵무새문장6.add("to the");
        앵무새문장6.add("store");
        String 검증문장6 = "go to the store";
        Assertions.assertEquals("Possible", 가능여부판단하기(앵무새문장6, 검증문장6));

        // 추가 테스트 케이스 4: 불가능한 경우 (단어가 하나 누락)
        ArrayList<String> 앵무새문장7 = new ArrayList<>();
        앵무새문장7.add("find");
        앵무새문장7.add("the missing link");
        String 검증문장7 = "find missing link";
        Assertions.assertEquals("Impossible", 가능여부판단하기(앵무새문장7, 검증문장7));

        // 추가 테스트 케이스 5: 불가능한 경우 (앵무새가 말한 단어를 모두 사용하지 않음)
        ArrayList<String> 앵무새문장8 = new ArrayList<>();
        앵무새문장8.add("hello world this is");
        앵무새문장8.add("a test");
        String 검증문장8 = "hello world a test";
        Assertions.assertEquals("Impossible", 가능여부판단하기(앵무새문장8, 검증문장8));
    }


}