[BOJ 25192] 인사성 밝은 곰돌이

문제 분석 및 풀이 방법

• 시간 제한 1초 Big-O 기준 약 1억 연산
• 채팅방의 기록 수 100,000개
• <set>을 사용한다.(O(logn)기대)
• 새로운 사람이 들어오면 곰곰티콘을 사용한다. ⇒ 곰곰티콘을 사용한 사람의 이름을 set에 추가한다.
• 기존의 이름이 또 들어오면 무시한다.
• "Enter"가 들어오면 <set>을 초기화 한다.

set<string> people;
int n, cnt;
string name;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    while (n--) {
        cin >> name;
        if (name == "ENTER") {
            people.clear();//"ENTER"가 입력되면 set초기화
        } else {
            if (people.count(name) == 0) {//set에 없는 이름이면
                people.insert(name);//set에 추가
                cnt++;//곰곰티콘 사용횟수 추가
            } else continue;//일반 채팅
        }
    }
    cout << cnt;
    return 0;
}

느낀 점

• 실력이 는 건지 문제가 쉬운건지 모르겠지만 금방 풀었다.
• 시간 제한과 조건을 보고 시간 복잡도를 얼추 계산해 <set>을 사용해야 겠다는 생각을 했는데 잘 생각한거 같다.

시간 복잡도

• while문 n번 반복-> O(n)
• set에서 접근 -> O(logn)
• set에서 삭제 -> O(logn)(기대)
  ➣O(nlogn)