글 읽기 - enter/leave 상태인지 미확인시 틀리는데 이유가 뭘까요

nacl0691 1년 전 0

아래 코드 62번 라인에서

1) 번처럼 하면 15%쯤에서 틀렸습니다가 나오고

2)번처럼 하면 통과가 됩니다.

어차피 leave 처리 하는것은 기존 상태에 상관없이 하면 될 것 같은데 결과가 달라지는 이유가 뭘까요?

동명이인이 없고, 대소문자도 다른 경우에는 해당 조건문에 진입하지 않을텐데 이유를 모르겠네요..

1) if (hashtable[h][i]->name == name)

2) if (hashtable[h][i]->name == name && hashtable[h][i]->in)

//틀린 코드

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
using namespace std;

#define MAX_SIZE 1000010
typedef unsigned long long ull;

struct DB {
	string name;
	int in;
};
DB pool[MAX_SIZE];
DB finList[MAX_SIZE];

vector<DB *> hashtable[MAX_SIZE];
ull getHash(const char* name) {
	ull hash = 5381;
	int c = 0;
	while (c = *name++) {
		hash = ((hash << 5) + hash + c) % MAX_SIZE;
	}
	return hash % MAX_SIZE;
}
bool cmp(DB a, DB b) {
	if (a.name > b.name) return true;
	return false;
}
int main() {
	/*입력
첫째 줄에 로그에 기록된 출입 기록의 수 n이 주어진다. (2 ≤ n ≤ 1000000) 
다음 n개의 줄에는 출입 기록이 순서대로 주어지며, 각 사람의 이름이 주어지고 "enter"나 "leave"가 주어진다. "enter"인 경우는 출근, "leave"인 경우는 퇴근이다.
*/
	int N;
	cin >> N;
	string name, cmd;
    int poolcnt = 0;
	for (int i = 0; i < N; ++i) {
		cin >> name >> cmd;
		ull h = getHash(name.c_str());
		if (cmd == "enter") {
			pool[poolcnt].name = name;
			pool[poolcnt].in = 1;
			
            hashtable[h].push_back(&pool[poolcnt++]);
		}
		else {
            int size = hashtable[h].size();
			for (int i = 0; i < size; ++i) {
				if (hashtable[h][i]->name == name) {
					hashtable[h][i]->in = 0;
					break;
				}
			}
		}
	}
	int cnt = 0;
	for (int i = 0; i < poolcnt; ++i) {
		if (pool[i].in)
		{
			finList[cnt++].name = pool[i].name;
		}
	}
	sort(finList, finList + cnt, cmp);
    /*출력
현재 회사에 있는 사람의 이름을 사전 순의 역순으로 한 줄에 한 명씩 출력한다..*/
	for (int i = 0; i <= cnt; ++i) {
		printf("%s\n", finList[i].name.c_str());
	}
	return 0;
}

nacl0691 1년 전 0

(질문자입니다)

동명이인은 없지만 같은 사람이 여러번 enter/leave를 할 수 있기 때문인걸까요?

그렇다고 하면 위 코드에서 leave시 hashtable에서 삭제작업을 함께 수행하거나, 본문에 써둔 것 처럼 in 상태를 확인해야 하겠네요.

혹시나 다른 의견 있으신분 알려주시면 감사하겠습니다.

일주일 후 완료처리 하겠습니다 ^^

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

문제

문제

출처

ICPC

enter/leave 상태인지 미확인시 틀리는데 이유가 뭘까요

nacl0691 1년 전 0

nacl0691 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말