백준 7785번 Pseudo code

문제 링크

https://www.acmicpc.net/problem/7785

7785번: 회사에 있는 사람

 

시간 제한 / 메모리 제한

1 초

256 MB

 

문제

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

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

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

 

입력

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

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

출력

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

예제 입력

4
Baha enter
Askar enter
Baha leave
Artem enter

예제 출력

Askar
Artem

 

문제 풀이를 위해 생각한 것

1. 현재 회사에 있는 모든 사람을 알아내는 방법은 무엇일까?
2. 각 로그는 공백을 기준으로 이름 - enter/leave 가 매핑 되어 있다.
3. 입력의 크기는 최대 10^6개 = 1,000,000 이다.
4. 시간 제한은 1초이기에 O(n^2)으로는 시간 제한 내에 답을 도출할 수 없다.
5. 출력은 사전 순의 역순이다. 즉 정렬이 필요하다.

 

사용한 자료구조

Map 자료구조와 배열.

 

이유는?

이름이라는 key의 value가 각각 계열적이지 않고, 독립적으로 관리되어야 하며, value의 조회, 삽입, 삭제가 빈번하게 일어남

Map으로 현재 회사에 있는 사람을 정의한 뒤, 이를 배열에 추가하여 사전의 역순으로 정렬해야 한다.

 

풀이 코드

n = 첫 입렧값을 정수로
map = 맵 선언
arr = 배열 선언

n번 동안:
	name, action = 공백을 기준으로 입력값 split (이름 행동)
	if action == 'enter':
		map[name] = True
	if action == 'leave':
		map[name] = False

map의 key k에 대하여:
	if map[k] == True:
		arr 배열에 삽입
	else:
		continue

arr배열을 사전 역순으로 정렬

arr의 원소 i에 대하여:
	print i

 

시간 복잡도 분석

O(N).

2N(map에 데이터 추가 및 조회) + NlogN(정렬)이나, 최고차항만 표기하고, 계수를 제외하여, O(N)의 시간 복잡도를 가진다.

 

문제에서 중요한 부분

n <= 10^6 으로 n의 최대 크기가 크다는 것을 고려해야 한다.