[백준 25192] 인사성 밝은 곰곰이 [Java]

백준 25192 - 문제

백준 25192 - 입/출력

---

풀이

새로운 사람이 오픈 채팅방에 입장하면 "ENTER" 이라는 문자열이 입력된다.
그 이후로 곰곰티콘을 사용한 사람이 총 몇명인지를 구하면 되는 문제이다.

백준 25192 - 문제

즉, 새로운 사람이 들어온 후 곰곰티콘을 사용한 사람의 수를 구하면 된다.

일반적으로 채팅한 모든 사람들에 대해 몇 번 채팅했는지 살펴보는 방법은 O(N^2), N이 100,000이기에 시간초과가 발생할 것이다.

 

따라서 O(1) 만에 이미 채팅이력이 있는지 확인을 해주어야 한다.

map과, set을 사용한 풀이들을 소개한다.

 

HashMap

먼저 이름을 저장할 HashMap으로 nameList를 선언해주자.

누가 몇 번을 채팅했든 상관없이, 1번이라도 채팅했다면 곰곰티콘을 사용한 채팅이 아닌 평범한 채팅 기록이기 때문에 횟수를 계산할 필요가 없다.

때문에 HashMap의 value를 Void로 주었다.

 

그 이후에는 한 줄 씩 입력받으면서, 새로운 사람이 오픈채팅방에 들어왔다면(ENTER) 기존에 곰곰티콘을 사용한 사람들에 대한 기록을 지우고 새로 계산해야 하므로 nameList를 비워주자.

나머지의 채팅에 대해서는 새로운 사람이 들어온 후 처음 채팅을 했다면(nameList에 등록되지 않은 Key라면) nameList에 이름을 등록해주고, 곰곰티콘 사용 횟수를 누적해주면 된다.

 

 

HashSet

이번에는 HashMap 대신 HashSet을 사용해보자.

앞서 HashMap을 사용할 때는 Value가 필요없어서 Void로 지정해 주었다.

이처럼 O(1) 시간의 탐색이 필요하면서, Value를 사용하지 않는다면 HashSet의 사용 또한 좋은 선택이 될 수 있다.

 

다만, HashSet은 내부적으로 HashMap을 사용하며, Value에는 내부 상수 PRESENT라는 더미값을 넘겨줌으로써 위에서 HashMap을 사용한 방법과 동일한 형식으로 이용할 수 있다.

때문에 이에 따른 약간의 오버헤드가 발생할 수 있지만 큰 차이는 없다.

 

add 메서드를 이용해 동일한 Key가 있는지 없는지 확인 후 없으면 자동으로 추가가 되며 true를 반환한다.

만약 없다면 false를 반환하기 때문에 cnt의 값은 증가하지 않을 것이다.

---

소스코드

소스코드 보기

---

출처

25192번: 인사성 밝은 곰곰이