★ solved.ac 난이도 : S5
(2021년 12월 29일 기준)
[문제 바로가기]
7785번: 회사에 있는 사람
첫째 줄에 로그에 기록된 출입 기록의 수 n이 주어진다. (2 ≤ n ≤ 106) 다음 n개의 줄에는 출입 기록이 순서대로 주어지며, 각 사람의 이름이 주어지고 "enter"나 "leave"가 주어진다. "enter"인 경우는
www.acmicpc.net
[풀이]
알파벳 대소문자로 이루어진 이름과 출입 기록(enter 또는 leave)이 주어질 때, 최종적으로 남아있는 사람들의 목록을 사전 역순으로 출력하는 문제입니다.
여기에서 출입 기록의 수 N의 값이 최대 100만개(!!)라는 점과 이름의 최대 길이는 5자라는 점이 있었습니다.
처음에는 C++ STL의 map을 사용해서 문제를 해결하려고 했습니다. (Key : 사람 이름(string), Value : 현재 남아있는 지 여부(bool))
하지만, 제가 실제로 100만개의 입력을 넣었더니 Ubuntu 기준 약 1.6초가 걸렸습니다.
제한 시간은 1초인데 비해 시간 초과의 위험도 크다는 것이죠.
이 문제를 해결하기 위해서 고민을 하던 도중, 저에게 기발한(?) 생각이 떠올랐어요...
'혹시 알파벳으로 이루어진 이름을 정수로 표현해보면 어떨까?'
물론, 이를 위해서는 전체 경우의 수를 알아야 하고, 표현 가능한 범위를 넘지 않아야 하는데요,
이 문제에서 알파벳 대소문자(52개)와 혹시나 모를 공백까지 해서 총 53개의 문자로 이루어진 최대 5자의 이름에 대한 경우의 수를 구한 결과...
(53^5)+(53^4)+(53^3)+(53^2)+(53^1) = 약 4.26억 가지의 경우가 나오게 되고,
이는 C언어의 int 자료형이 표현할 수 있는 (2^31-1) 보다 작기 때문에 모든 경우에 대해 일대일 대응이 가능하다는 점을 알게 되었어요~!
하지만, 문제는 지금부터... 이름을 숫자로 바꾸는 과정과 이를 다시 해석하는 과정을 구현해야 했는데요,
문제에서 사전 역순으로 출력하라고 되어 있었고, 이를 다시 말하면, 아스키 코드 값의 내림차 순으로 정렬을 해서 출력을 하라는 뜻...
이 기능을 함수로 구현하는 과정에서, 알파벳 대문자가 소문자보다 아스키 코드가 빠르다는 점을 이용해서,
공백(이미 이름이 끝난 경우) : 0
알파벳 대문자 : 1~26
알파벳 소문자 : 27~52의 값을 각각 대응 시켰고, 이를 진법 변환 처럼 자릿수에 따라 적절히 53을 곱해주었죠...
그리고, 출근 기록이 주어지면 +1, 퇴근 기록이 주어지면 -1을 enter에 저장했죠...
이 과정에서 생성된 정수로 표현된 이름, enter 변수를 하나의 비트 필드 구조체에 저장한 다음, (이름 : 30bit, enter : 2bit) 정렬을 하고!
내림차 순으로 정렬된 사람 이름 별 출퇴근 이력을 분석합니다.
여기에서 출근은 +1, 퇴근은 -1로 연산을 해서, 최종적으로 0보다 크면,
숫자로 표현된 이름을 다시 문자열로 해석해서 출력을 하게 되는 알고리즘을 구현했습니다.
(그리고, 마지막 데이터에 대한 처리도 잊지 않았습니다.)