[백준(BOJ)] 25192번 인사성 밝은 곰곰이 C++

2022. 7. 25. 22:23· 백준 문제풀이(BOJ PS)
목차
  1. 어떤 문제인가?
  2. 접근 방법
  3. 무엇이 어려웠는가?
  4. 시간 복잡도

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

 

25192번: 인사성 밝은 곰곰이

첫번째 새로운 사람이 들어온 뒤  pjshwa, chansol, chogahui05은 모두 곰곰티콘으로 인사했다. 두번째 새로운 사람이 들어온 뒤  pjshwa와 chansol은 다시 곰곰티콘으로 인사했다.

www.acmicpc.net

 

 

어떤 문제인가?

채팅방에 새로운 사람이 들어왔을 때 유저의 닉네임의 첫 번째 등장만이 신입에게 인사를 한 채팅이다.

그 외의 나머지는 잡답이다.

따라서 ENTER가 입력된 후에 처음 등장한 닉네임의 숫자만 세주면 된다.

 

 

접근 방법

문제를 읽자마자 map을 써야겠다고 생각했다.

map<string, bool> user;

유저의 이름을 key로 인사 여부를 value로 저장하는 map을 선언했다.

 

int N;
string s;
int cnt = 0;

cin >> N;

문제에서 주어진 변수들을 선언하고 입력받는다.

 

 

for (int i = 0; i < N; i++) {
    cin >> s;
    if (s == "ENTER") {
        user.erase(user.begin(), user.end());
    } else {
        if (!user[s]) {
            cnt++;
            user[s] = true;
        }
    }
}

만약 입력이 ENTER라면 기존에 map에 존재하는 원소들을 다 지워버린다.

 

그 외에 유저의 닉네임이 입력됐을 때는 key(유저의 닉네임)에 대한 value(인사 여부)를 확인한다.

value가 false라면 아직 인사를 하지 않은 유저이니 cnt를 증가시켜주고, value를 true로 바꿔준다.

 

cout << cnt;

for문을 끝낸 후 cnt를 출력해주면 끝!!

 

 

무엇이 어려웠는가?

map을 사용할 줄 안다면 아주 쉽게 풀리는 문제라 어려운 부분이 없었다.

 

 

시간 복잡도

내 풀이 같은 경우에는 먼저 for문을 n번만큼 반복한다.

그 안에서 vector의 삭제 연산이 발생하는 경우가 존재한다.

최악의 경우 -> 첫 입력과 마지막 입력을 제외한 모든 입력 동안 새로운 유저의 닉네임만 입력된다.

그렇다면 첫 입력과 마지막 입력인 ENTER를 제외하고 n-2크기 만큼의 map이 된다.

이 map을 지우는데 O(n)시간이 걸린다.

 

따라서 시간복잡도는 O(n^2)이 된다.

'백준 문제풀이(BOJ PS)' 카테고리의 다른 글

[백준(BOJ)] 19638번 센티와 마법의 뿅망치 C++  (0) 2022.07.27
[백준(BOJ)] 14713번 앵무새 C++  (0) 2022.07.27
[백준(BOJ)] 17952번 과제는 끝나지 않아! C++  (0) 2022.07.25
[백준(BOJ)] 12789번 도키도키 간식드리미 C++  (0) 2022.07.25
[백준(BOJ)] 5430번 AC C++  (0) 2022.07.25
  1. 어떤 문제인가?
  2. 접근 방법
  3. 무엇이 어려웠는가?
  4. 시간 복잡도
'백준 문제풀이(BOJ PS)' 카테고리의 다른 글
  • [백준(BOJ)] 19638번 센티와 마법의 뿅망치 C++
  • [백준(BOJ)] 14713번 앵무새 C++
  • [백준(BOJ)] 17952번 과제는 끝나지 않아! C++
  • [백준(BOJ)] 12789번 도키도키 간식드리미 C++
팜준
팜준
코드가 자라나는 텃밭팜준 님의 블로그입니다.
팜준
코드가 자라나는 텃밭
팜준
전체
오늘
어제
  • 분류 전체보기
    • 회고
    • 자료구조(Data Structure)
    • 백준 문제풀이(BOJ PS)
    • 대외활동(Activity)
    • 알고리즘(Algorithm)
    • 운영체제(OS, Operating System)
    • AWS
    • 취업준비
    • 일기

블로그 메뉴

  • 홈
  • 태그
  • 방명록

공지사항

인기 글

태그

  • 다이나믹 프로그래밍
  • 일기
  • 깃허브
  • deque
  • 자료구조
  • 그리디알고리즘
  • 깃
  • DP
  • 덱
  • 큐
  • 완전탐색
  • BFS
  • 알고리즘
  • 백준
  • DFS
  • 백트랙킹
  • 깊이우선탐색
  • 자바
  • 그래프탐색
  • java

최근 댓글

최근 글

hELLO · Designed By 정상우.v4.2.0
팜준
[백준(BOJ)] 25192번 인사성 밝은 곰곰이 C++
상단으로

티스토리툴바

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.