티스토리 뷰
백준 온라인 저지(BOJ) 25192번 인사성 밝은 곰곰이
https://www.acmicpc.net/problem/25192
* 사용언어 : C언어, C++
1. 문제
ENTER(새로운 사람 입장) 혹은 채팅을 입력한 유저의 닉네임이 입력으로 주어짐
새로운 사람 입장 후 각 유저의 첫 채팅은 반드시 곰곰티콘을 사용한 인사이고, 이후는 채팅은 평범한 채팅임
전체 기록 중 곰곰티콘이 사용된 횟수를 출력
2. 풀이
hash table 구조를 활용하여 각 채팅마다 O(1)의 시간복잡도를 가지도록 구현해서 풀었습니다.
우선 hash의 key는 유저의 닉네임으로, 입력으로 받을 때마다 탐색한 후 없으면 해당 자리에 기록합니다.
hash의 value는 enter가 등장한 횟수입니다.
우선 ENTER가 주어지면 enter_cnt라는 global 변수를 1 증가시킵니다.
그리고 유저 닉네임이 주어질 때 마다 해당 유저의 hash의 value가 enter_cnt와 같은지 확인합니다.
만약 같다면 이미 채팅을 한(곰곰티콘을 사용한) 유저이므로 넘어가고,
다르면 hash의 value를 enter_cnt로 변경해준 뒤 출력할 res 값을 1 증가시킵니다.
추가로 hash 충돌은 open addressing 방식을 활용하여 해결했습니다.
따라서 hash table의 크기를 주어지는 유저 수의 최대값(10만)의 1.5배로 구현했습니다.
(통상 2~3배가 일반적이나 크기를 줄이며 수차례 제출해본 결과 15만까지 코드의 최대 속도인 44ms가 나옴)
그 외 부분은 아래 코드로 설명 대체하겠습니다.
3. 코드
#ifndef _CRT_SECURE_NO_WARNINGS
#define _CRT_SECURE_NO_WARNINGS
#endif
/*
25192_인사성 밝은 곰곰이
6584KB 44ms // HLM = 200000
5126KB 44ms // HLM = 150000 <-
3848KB 112ms // HLM = 100000
*/
#include <cstdio>
const int HLM = 150000;
const int CLM = 21;
int N, enter_cnt, res;
char input[CLM], enter[CLM] = "ENTER";
int strcmp(const char *a, const char *b) {
while (*a && *b && *a == *b) *a++, *b++;
return *a - *b;
}
void strcpy(const char *src, char *des) {
while (*src) *des++ = *src++;
*des = 0;
}
struct _hash {
char key[CLM];
int value;
} HASH[HLM];
int hash(char *key) {
unsigned long long hash = 5381;
int c;
while (c = *key++) hash = (((hash << 5) + hash) + c) % HLM;
return hash;
}
int h_find(char *key) {
int h = hash(key);
int cnt = HLM;
while (HASH[h].key[0] && cnt--) {
if (!strcmp(key, HASH[h].key)) return h;
h = (h + 1) % HLM;
}
return h;
}
int main() {
#ifdef _WIN32
freopen("input.txt", "r", stdin);
#endif // _WIN32
scanf("%d", &N);
while (N--) {
scanf("%s", input);
if (!strcmp(input, enter)) ++enter_cnt;
else {
int h = h_find(input);
if (!HASH[h].key[0]) strcpy(input, HASH[h].key);
if (HASH[h].value != enter_cnt) {
HASH[h].value = enter_cnt;
++res;
}
}
}
printf("%d\n", res);
return 0;
}
'개발자 > 문제풀이 (C언어)' 카테고리의 다른 글
[백준/BOJ] 2108번 통계학 (C/C++) (0) | 2024.01.02 |
---|---|
[백준/BOJ] 26069번 붙임성 좋은 총총이 (C/C++) (0) | 2024.01.01 |
[백준/BOJ] 1037번 약수 (C/C++) (0) | 2023.12.26 |
[백준/BOJ] 1010번 다리 놓기 (C/C++) (0) | 2023.12.25 |
[백준/BOJ] 11050번 이항 계수 1 (C/C++) (0) | 2023.12.25 |
- Total
- Today
- Yesterday
- 나의첫죽음학수업
- 지루함의심리학
- 삼성전자
- 세상을 읽는 새로운 언어 빅데이터
- 호암의마지막꿈
- 문현공
- 긴 자리 덧셈 뺄셈
- 독서 감상평
- 자동차보험
- 자이언트임팩트
- 내가틀릴수도있습니다
- 동탄에듀센터
- 인간본성불패의법칙
- 나는늘잘해야한다고생각한다
- 원서잡아먹는영작문
- 독서감상평
- 당신도느리게나이들수있습니다
- 정세현의통찰
- 영화감상평
- 여가포인트
- JUNGOL
- 정올
- 안전운전특약
- 동탄에듀센터2
- 역사의쓸모
- 긴 자리 곱셈
- 최재천의공부
- 센터독서클럽
- AdSendse
- 쿠프마케팅
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | |||
5 | 6 | 7 | 8 | 9 | 10 | 11 |
12 | 13 | 14 | 15 | 16 | 17 | 18 |
19 | 20 | 21 | 22 | 23 | 24 | 25 |
26 | 27 | 28 | 29 | 30 | 31 |