[BAEKJOON]7785 회사에 있는 사람

문제 요약

• 알고리즘 분류: 집합
• 난이도: Silver5
• 문제내용:
  • 사람 이름하고 "enter"나 "leave"가 주어진다.
  • "enter"인 경우는 출근, "leave"인 경우는 퇴근이다.
  • 출근 한 사람 역순으로 출력해라
• 사이트: https://www.acmicpc.net/problem/7785

 

문제풀이

 이번 문제는 간단한 집합문제이다. 각 언어마다 Set이라는 자료 구조만 활용 잘하면 된다. Set에 대한 기본 설명 하면 아래와 같다.

 

• O(1) 시간에 추가/삭제 가능
• 자동으로 중복 제거
• 빠른 검색 가능

 

구현은 아래와 같이 하면 된다.

1. enter 기록은 Set에 추가
2. leave 기록은 Set에서 제거
3. 마지막에 Set의 내용을 역순 정렬하여 출력

마무리

 위와 같이 구현 하면 시간 복잡도는 정렬 때문에 O(NlogN) 만큼 나온다.

이 문제는 Set 자료구조의 기본적인 활용법을 이해하고 있다면 쉽게 해결할 수 있다.

 

Code

Python

# 현재 회사에 있는 사람들의 이름을 저장할 Set
names = set({})

for _ in range(int(input())):
    # 각 로그를 공백으로 분리하여 이름과 상태를 파싱
    name, action = input().split()

    #"enter"면 사람을 회사에 추가, "leave"면 회사에서 제거
    if action == "enter":
        names.add(name)
    else:
        names.remove(name)

# 사전순 역순으로 정렬하여 출력
for name in sorted(names, reverse=True):
    print(name)

Java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
import java.util.stream.Collectors;


public class Main {


	public static void main(String[] args) throws IOException {


		BufferedReader br = new BufferedReader(new InputStreamReader((System.in)));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int n = Integer.parseInt(st.nextToken());

		// 현재 회사에 있는 사람들의 이름을 저장할 HashSet
		Set<String> names = new HashSet<>();

		for (int i = 0; i < n; i++) {
			// 각 로그를 읽어서 이름과 상태(enter/leave)를 파싱
			st = new StringTokenizer(br.readLine());
			String name = st.nextToken();

			// "enter"면 사람을 회사에 추가, "leave"면 회사에서 제거
			if (st.nextToken().equals("enter")) {
				names.add(name);
			}else{
				names.remove(name);
			}
		}

		// 현재 회사에 있는 사람들을 역순(사전순 역순)으로 정렬하여 출력
		names.stream()
				.collect(Collectors.toList())
				.stream()
				.sorted(Comparator.reverseOrder())
				.forEach(System.out::println);

	}

}

Javascript

var input = require('fs').readFileSync("/dev/stdin", "utf-8").toString().trim().split("\n");

const n = parseInt(input[0]);

// 현재 회사에 있는 사람들의 이름을 저장할 Set
const names = new Set();

// n개의 로그를 처리
for (let i = 1; i <= n; i++) {
    // 각 로그를 공백으로 분리하여 이름과 상태를 파싱
    const [name, action] = input[i].trim().split(' ');

    // "enter"면 사람을 회사에 추가, "leave"면 회사에서 제거
    if (action === "enter") {

        names.add(name);
    } else {
        names.delete(name);
    }
}

// 현재 회사에 있는 사람들을 배열로 변환 후
// 사전순 역순으로 정렬하여 출력
Array.from(names)
    .sort()                // 사전순 정렬
    .reverse()            // 역순으로 뒤집기
    .forEach(name => console.log(name));