[백준/Node.js] 25192번: 인사성 밝은 곰곰이 _배열과 집합 차이

목차

📝 문제

🎯 알고리즘 핵심 단계

✅ 실습 인증 파트_코드

⚡ 트러블 슈팅

🤔 이것도 한 번 생각해봐요! (참고 자료)

---

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

 

📝 문제

알고리즘 입문방 오픈 채팅방에서는 새로운 분들이 입장을 할 때마다 곰곰티콘을 사용해 인사를 한다. 이를 본 문자열 킬러 임스는 채팅방의 기록을 수집해 그 중 곰곰티콘이 사용된 횟수를 구해 보기로 했다.

ENTER는 새로운 사람이 채팅방에 입장했음을 나타낸다. 그 외는 채팅을 입력한 유저의 닉네임을 나타낸다. 닉네임은 숫자 또는 영문 대소문자로 구성되어 있다.

새로운 사람이 입장한 이후 처음 채팅을 입력하는 사람은 반드시 곰곰티콘으로 인사를 한다. 그 외의 기록은 곰곰티콘을 쓰지 않은 평범한 채팅 기록이다.

채팅 기록 중 곰곰티콘이 사용된 횟수를 구해보자!

 

입력

첫 번째 줄에는 채팅방의 기록 수를 나타내는 정수 N 이 주어진다. (1 ≤ N ≤ 100,000)

두 번째 줄부터 N 개의 줄에 걸쳐 새로운 사람의 입장을 나타내는 ENTER, 혹은 채팅을 입력한 유저의 닉네임이 문자열로 주어진다. (1 ≤ 문자열 길이 ≤ 20)

첫 번째 주어지는 문자열은 무조건 ENTER이다.

 

출력

채팅 기록 중 곰곰티콘이 사용된 횟수를 출력하시오.

 

---

🎯 알고리즘

💡 문제 이해

      ENTER가 등장할 때마다 인사 기록 초기화 -> 중복되지 않는 이름의 수를 세어 누적하기

 

💡 문제 접근

    한 줄씩 순회하면서 만약 현재 줄의 내용이 "ENTER"이면 Set 초기화

     ENTER 아닌 경우

         해당 이름이 Set에 없으면 Count 1 증가

         해당 이름이 Set에 있으면 Count 증가하지 않기

 

---

✅ 실습 인증 _코드

const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().trim().split("\n");
const n = parseInt(input[0]);
const list = input.slice(1);

let temp = new Set(); 
let count=0;

for (let i = 1; i < n; i++) {
    if(list[i] == "ENTER"){
        temp.clear();
    }else{
        if(!temp.has(list[i])){
            temp.add(list[i]);
            count++;
        }
    }
}
console.log(count);

 

---

⚡ 트러블 슈팅

       🌱 배열과 집합의 차이

         배열[ ] 은 같은 값이 여러 번 들어갈 수 있다.

         - 요소를 찾으려면 순차 탐색이 필요하기 때문에, 중복 체크를 위해 includes 메서드를 사용할 경우

           시간 복잡도는 O(n)

       

        집합( ) 은 동일한 값이 한 번만 저장될 수 있음 - 중복X

        - 해시 테이블을 기반으로 구현되어 있어서, 요소 추가나 존재 여부 확인은 평균적으로

           시간 복잡도는 O(1)

 

 

---

🤔 이것도 한 번 생각해봐요! (참고 자료)