[백준 BOJ] 7785번 회사에 있는 사람 (C++/cpp)

문제 설명

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

 

 

접근 방법 - 맵을 활용한 기초 연산 문제

백준의 7785번 문제는 맵 자료구조를 활용하여 간단하게 해결할 수 있는 문제이다.

해당 문제는, 입력으로 주어지는 직원의 출입 기록을 기반으로 회사에 남아있는 직원의 이름을 구하여 사전 순의 역순으로 출력하면 되는 문제이다.

이때 문제 상 회사에는 동명이인이 없다고 명시되어 있으니, 중복으로 회사에 오거나 나가는 경우가 기록되는 경우는 없다고 해석할 수 있겠다.

 

필자는 처음에는 벡터로 문제 해결을 시도해 보다가 시간 초과가 났는데, 아마 직원 이름을 find()로 일일이 찾는 과정에서 시간이 많이 걸렸던 것 같다.

그래서 다른 방법으로 생각한 것이 맵을 활용하는 것이었으며, 맵을 활용 하니 간단하게 해결이 되었다.

문제에서 정답으로 출력할 이름들을 사전 역순으로 출력하라는 점도 있어서, 맵에 정렬을 적용해보기도 하였다.

자세한 설명은 아래에 기재해 놓으니, 혹여나 해당 문제를 해결하는 데에 어려움을 겪고 있다면 아래의 설명과 코드를 참고해 보길 바란다.

필자는 아래의 순서대로 코드를 작성하여 문제를 해결하였다.

 

코드의 실행 순서

1) 회사 출입 여부를 저장할 맵(m)을 미리 선언해 둔다.

<직원 이름, 출입 여부(0, 1)> 형태로 값을 저장하기 위해 <string, int> 타입으로 맵을 선언 하였다.

그리고 맵의 key값인 직원 이름을 기준으로 내림차순 정렬(사전순 역순)을 미리 하기 위해 greater<>를 추가로 설정해 두었다.

map<string, int, greater<>> m;

 

2) 출입 로그의 개수(n)를 입력받는다.

 

3) n의 크기만큼 반복문을 수행하여, 아래의 연산을 수행한다.

- 직원의 이름(name)과 출입 여부(command)를 입력받는다.

- command의 값이 "enter"라면 이는 해당 직원이 회사에 들어왔음을 의미하기 때문에, 이 경우엔 m[name] 값을 1로 설정한다.

다만, command의 값이 "leave"라면 이는 해당 직원이 회사를 나갔음을 의미하기 때문에, 이 경우엔 m[name] 값을 0으로 설정한다.

 

4) 출입 여부 입력과 연산이 모두 끝났다면, 다른 반복문을 통하여 m의 요소들을 탐색한다. 

it를 통하여 m의 요소들에 하나씩 접근하는데, 이때 it.first는 요소의 key값인 직원의 이름을 뜻하고 it.second는 요소의 value값인 출입 여부를 뜻한다.

이때, 출입 여부 값(it.second)이 1이라면 이에 해당하는 직원은 회사에 남아있음을 뜻하기 때문에, 해당 직원의 이름(it.first)을 출력하도록 한다.

 

5) 4)를 통하여 정답을 모두 출력하였다면, 실행 종료한다.

반응형

 

성공한 코드

#define _CRT_SECURE_NO_WARNINGS
#pragma warning(disable: 4996)
#include <iostream>
#include <algorithm>
#include <map>
#define endl '\n'
using namespace std;

//백준 7785번 코드
int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);	cout.tie(NULL);

	map<string, int, greater<>> m;
	int n;
	cin >> n;
	for (int i = 0; i < n; i++) {
		string name, command;
		cin >> name >> command;

		if (command == "enter") {
			m[name] = 1;
		}
		else {
			m[name] = 0;
		}
	}

	for (auto it : m) {    // it:: auto 선언 가능
		if (it.second == 1) {
			cout << it.first << endl;
		}
	}
}

 

제출 결과

(2023.03.15 백준 7785번 문제 제출 결과)