글 읽기 - 시간초과 나는 이유

(追記) (追記ここまで)

시간초과 나는 이유

7785번 - 회사에 있는 사람

ksjb2897 7달 전 0

각 사람마다 구조체를 만들고, 구체안에 이름(name[6])과 회사안에 있는지 없는지(in)를 나타내었습니다.

in이 1이면 있는 것이고, in이 0이면 없는 것입니다.

코드를 다 읽으실 필요 없이, 제가 구현한 시간복잡도가 NlogN인 것같은데, 왜 시간초과가 나는지 모르겠습니다...

메인 코드만 보시면,

for문으로 일단 N번 돌렸고,

각 enter()와 leave()는 안에서 이진탐색으로 이름이 있는지 없는지 확인한 후 in을 1로 바꾸거나 0으로 바꾸었습니다. 그래서 logN의 시간복잡도가 나오고,

qsort는 시간복잡도 logN으로 알고 있습니다.

각 enter, leave, qsort는 병렬적(?)이므로

전체 시간복잡도가 NlogN이 나오는 것 아닌가요??(대충 3NlogN이니깐... O(3NlogN)=NlogN)

근데 왜 시간초과가 뜨는지 모르겠습니다..

다들 해쉬를 사용하라고 하는데, 왜 해쉬를 쓰면 더 빨라지는지, 그러면 NlogN보다 더 빨라지는 것인지 궁금합니다. 다음에 이런 유사한 문제를 풀 때, 해쉬를 쓸지 다른 탐색방법을 쓸지 결정하고 싶거든요...

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
typedef struct person {
 char name[6];
 int in;
} person;
person people[1000000];
int ptr;
void enter(char* n);
void leave(char* n);
int compare();
int binary_Search(int left, int right, char* key);
void enter(char* n) {
 if (ptr != 0) {
 int index = binary_Search(0, ptr - 1, n);
 //printf("index : %d\n", index);
 if (index >= 0) people[index].in = 1;
 else {
 strcpy(people[ptr].name, n);
 people[ptr].in = 1;
 ptr ++;
 }
 } else {
 strcpy(people[ptr].name, n);
 people[ptr].in = 1;
 ptr ++;
 }
}
void leave(char* n) {
 int index = binary_Search(0, ptr-1, n);
 people[index].in = 0;
}
int compare(const void* a, const void* b) {
 return strcmp((char*)b, (char*)a);
}
int binary_Search(int left, int right, char* key) {
 int mid = (left + right)/2;
 if (left == right) {
 if (strcmp(key, people[left].name) == 0) return left;
 else return -1;
 } else if (left + 1 == right) {
 if (strcmp(key, people[left].name) == 0) return left;
 else if (strcmp(key, people[right].name) == 0) return right;
 else return -1;
 } else {
 if (strcmp(key, people[mid].name) > 0) return binary_Search(left, mid, key);
 else if (strcmp(key, people[mid].name) < 0) return binary_Search(mid, right, key);
 else return mid;
 }
}
int main() {
 int N;
 scanf("%d", &N);
 ptr = 0;
 for (int i = 0; i < N; i ++) {
 char n[6], e[6];
 scanf("%s %s", n, e);
 if (e[0] == 101) enter(n);
 else leave(n);
 qsort(people, ptr, sizeof(person), compare);
 }
 for (int i = 0; i < ptr; i ++) {
 if (people[i].in == 1) printf("%s\n", people[i].name);
 }
}

rocket2357 7달 전 0

qsort의 시간복잡도가 평균적으로는 NlogN일 겁니다.

ksjb2897 7달 전 1

아 맞다 그러네요... 이런 오만한 실수를... 감사합니다!

댓글을 작성하려면 로그인해야 합니다.

(追記) (追記ここまで)

Baekjoon Online Judge

채점 현황

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말

© 2026 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO

사업자 등록 번호: 541-88-00682
대표자명: 최백준
주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
전화번호: 02-521-0487 (이메일로 연락 주세요)
이메일: contacts@startlink.io
통신판매신고번호: 제 2017-서울서초-2193 호

한국어 | English (Beta)