[C] 백준 7785번 : 회사에 있는 사람

문제

 

상근이는 세계적인 소프트웨어 회사 기글에서 일한다. 이 회사의 가장 큰 특징은 자유로운 출퇴근 시간이다. 따라서, 직원들은 반드시 9시부터 6시까지 회사에 있지 않아도 된다.

각 직원은 자기가 원할 때 출근할 수 있고, 아무때나 퇴근할 수 있다.

상근이는 모든 사람의 출입카드 시스템의 로그를 가지고 있다. 이 로그는 어떤 사람이 회사에 들어왔는지, 나갔는지가 기록되어져 있다. 로그가 주어졌을 때, 현재 회사에 있는 모든 사람을 구하는 프로그램을 작성하시오.

 

입력

 

첫째 줄에 로그에 기록된 출입 기록의 수 n이 주어진다. (2 ≤ n ≤ 10^6) 다음 n개의 줄에는 출입 기록이 순서대로 주어지며, 각 사람의 이름이 주어지고 "enter"나 "leave"가 주어진다. "enter"인 경우는 출근, "leave"인 경우는 퇴근이다.

회사에는 동명이인이 없으며, 대소문자가 다른 경우에는 다른 이름이다. 사람들의 이름은 알파벳 대소문자로 구성된 5글자 이하의 문자열이다.

 

출력

 

현재 회사에 있는 사람의 이름을 사전 순의 역순으로 한 줄에 한 명씩 출력한다.

 

풀이

 

#include <stdio.h>
 
unsigned char arr[52500000];
int max = 0;
 
int main(){
    int N,i;
    scanf("%d",&N);
    while(N--){
        char name[6] = "\0";
        char inNout[6] = "\0";
        scanf("%s %s",name,inNout);
        long long int idx = 0,mul=1;
        for(i=4;i>=0;i--){
            if(name[i]>='a'&&name[i]<='z') idx += (name[i]-'a'+27)*mul;
            else if(name[i]>='A'&&name[i]<='Z')idx += (name[i]-'A'+1)*mul;
            mul *= 53;
        }
        if(idx>max) max = idx;
        if(inNout[0]=='e'){
            arr[idx/8] |= 1 << (idx%8);
        }
        else arr[idx/8] &= ~(1 << (idx%8));
    }
    for(i=max;i>=0;i--){
        if(arr[i/8] & (1 << i%8)){
            int idx = i;
            char out[6];
            int cur=0;
            while(idx>0){
                if(idx%53<27 && idx%53 >0) out[cur++]=idx%53+'A'-1;
                else if(idx%53>=27) out[cur++] = idx%53+'a'-27;
                idx /= 53;
            }
            for(int t = cur-1 ; t >= 0 ; t--) printf("%c",out[t]);
            printf("\n");
        }
    }
}

 

삼성 코테 b형 준비한다고 라이브러리 안쓰고 풀어보느라 고생했다

set 썼으면 정말 쉬웠을텐데ㅜㅜ

 

먼저 사람 이름이 5글자 이내라고 해서 direct addressing으로 풀어보고 싶은 생각이 들었다

대부분 들어오는 입력값이 5글자가 훨씬 넘어 long long을 사용하여도 direct addressing을 사용할 수 없지만 유난히 입력이 짧은 문제였다

대문자, 소문자, 공백까지 해서 53의 5제곱까지 hashTable로 사용하려면 가장 작은 자료형인 char로 선언해도 메모리 초과가 났다

C에 비트 단위의 자료형이 없어서 결국 char 배열을 bit 단위로 끊어서 사용하였다

이름을 index로 바꾸어 char 배열에 해당하는 index의 bit가 1이면 회사에 그 사람이 있는 것이고 0이면 회사에 그 사람이 없는 것이다

 

이름을 index로 바꿀때에는 사전순을 고려해주었다

가장 첫자리인 이름의 0번지가 우선순위가 가장 높아야하므로 이름은 제일 마지막자리인 4번지부터 index에 더해주었다

이 때 공백은 없는 것과 마찬가지이므로 사전순에서 가장 앞서야하니 0으로 지정해주었고 대문자와 소문자도 우선순위를 지정해주었다

처음에 대문자와 소문자 중 우선순위를 잘못잡아서 틀렸다ㅠㅠ

strcmp만 썼어서 아스키코드값 비교가 빨리빨리 안된다

index를 구해 주었으면 enter 인 경우는 bit를 1로 leave인 경우는 bit를 0으로 지정해주었다

 

입력이 끝났으면 이제 모든 배열을 돌면서 배열의 index를 다시 사람의 이름으로 바꾸어주어야한다

배열의 index만 알면 해당 배열의 사람의 이름을 알 수 있으므로 입력 중 가장 컸던 index부터 0번지까지 차례로 돌면서

해당 bit가 0인 index의 사람 이름을 구해 출력해주었다

 

비트 단위의 계산을 많이 쓰는 프로젝트를 하고 있었고 해싱 문제를 몇개 풀고 난 뒤라 나름 새로운 풀이를 시도해보아서 뿌듯했다