📋 개요
데브크루 2주 코딩 챌린지의 2일 차이다. 2일 차의 첫 번째 문제는 금고털이, 그리디 알고리즘을 활요하는 문제였다.
2024.01.29 - [Algorithm/Problem] - [Softeer] 금고털이(Lv.2) - Day2
그다지 그렇게 어려운 문제는 아니였다. 오름차순이나 내림차순으로 정렬해서 최적의 해를 찾으면 되는 거니깐... 하지만 이번 문제인 회의록은 빡구현 문제였다. 하지만 IDE를 사용하지 않고 디버깅 없이 빡구현하려니깐 6시간은 아주 삽질을 한 거 같다....
C++로 푼 리뷰도 없어서 조곰 풀어나가는데 난감했었지만, 그래도 풀었고 문제를 해결한 과정을 리뷰한다.
https://softeer.ai/practice/6266
🧩 문제
회사에는 N개의 회의실이 있다. 수많은 팀이 모여 토론하고 업무를 처리하기 위해서는 회의실이 필수적이다.
내부망에 아주 간단한 회의실 예약 시스템이 있지만 편의성이 매우 떨어진다. 단순히 예약된 회의의 목록만 표시되기 때문에, 방 별로 비어 있는 시간이 언제인지를 확인하기가 힘든 것이다. 당신은 이를 직접 해결해 보기로 마음먹었다.
회의실 이용 규칙은 다음과 같다:
- 회의실은 9시부터 18시까지만 사용 가능하다. 모든 회의의 시간은 이 안에 완전히 포함되어야 한다.
- 회의는 정확히 한 회의실을 연속한 일정 시간 동안만 점유한다. 즉 각 회의는 (회의실, 시작 시각, 종료 시각)의 정보로 나타낼 수 있다.
- 회의의 시작과 종료 시각은 시(時, hour) 단위로만 설정 가능하다. 같은 회의실을 사용하는 회의 시간은 서로 겹칠 수 없다. 여기서 겹친다는 것은, 두 회의 모두에 포함되는 시간이 1시간 이상 존재한다는 것을 의미한다. 예를 들어, 10시-12시의 회의와 11시-13시의 회의는 겹치는데, 11시-12시의 시간이 두 회의 모두에 포함되기 때문이다.
- 한 회의가 끝나는 시각에, 같은 회의실에서 다른 회의가 시작하는 것은 허용된다. 이 경우 두 회의가 겹치지 않기 때문이다.
- 길이가 0인 회의, 즉 시작 시각과 종료 시각이 동일한 회의는 예약된 바 없으며, 새롭게 잡을 수도 없다.
이미 예약된 M개의 회의에 대한 정보가 주어지면, 회의실별로 비어 있는 시간대를 정리해 출력하는 프로그램을 작성해 보자. 구체적인 형식은 아래를 참고하시오.
⛔ 제약조건
1 ≤ N ≤ 50
1 ≤ M ≤ 100
회의실의 이름은 영문 알파벳 소문자로만 이루어져 있으며 길이는 1 이상 10 이하이다.
주어지는 모든 시각은 9 이상 18 이하이다.
회의의 시작 시각은 회의의 종료 시각을 1시간 이상 앞선다.
📝 형식
📥 입력 | 📤 출력 |
1 ≤ N ≤ 50 1 ≤ M ≤ 100 회의실의 이름은 영문 알파벳 소문자로만 이루어져 있으며 길이는 1 이상 10 이하이다. 주어지는 모든 시각은 9 이상 18 이하이다. 회의의 시작 시각은 회의의 종료 시각을 1시간 이상 앞선다. |
각 회의실에 대한 정보를 회의실 이름의 오름차순으로 출력한다. 각 회의실에 대한 정보는 다음과 같다. 첫째 줄에는 { Room 회의실이름: } (중괄호 제외)을 출력한다. 둘째 줄에는 예약가능 시간을 출력한다. - 예약 가능한 시간대의 개수를 n이라고 할 때, { n available: } (중괄호 제외)을 출력하고, 뒤따른 n개의 줄에 예약 가능한 시간대를 { 09-18 } (하이픈 한개, 중괄호 제외)형태로 출력해야 한다. 한 자리 수의 경우 앞에 0을 붙여 두 자리 수로 만들어야 함에 유의하라. - 예약 가능한 시간이 없다면, Not available을 출력한다. 각 회의실에 대한 정보 사이에는 ----- (하이픈 다섯 개)로 구분선이 출력되어야 한다. |
💡 예제
🔢 번호 | 📥 입력 | 📤 출력 |
1 |
|
|
2 |
|
🖥️ 내 코드
📖 해설 및 느낀 점
# C++ 문법 - 함수
일단, C++를 쓰면서 function을 사용해서 main 함수에 들어가는 코드 줄을 줄이려고 했다. 근데 C++은 main위에 코드를 작성해야 컴파일 에러가 발생하지 않았다.... 돌리면서 왜 안되는 건지... 계속 헤매다가 이유를 찾아 나섰다.
내가 자주 사용하던 언어 JAVA는 Class기반의 구조를 갖고 있다. 아래의 그림을 보면 알겠지만 먼저 클래스를 분석하고 런타임 환경에 들어갈 수 있도록 class 파일을 만든다. 그리고 JVM에 넣기 위해 클래서 로더가 클래스를 호출하게 된다. 여기까지가 자바의 구조다.
2022.05.29 - [Language/Java] - [JAVA] 컴파일 원리
그렇다면 C++을 살펴보자. 클래스 기반 동작이 아니라 위에서 아래로 읽으면서 컴파일을 진행하게 된다. 그렇기 때문에 함수는 미리 선언되어 정의되어있어야지 동작을 컴파일과정에서 에러가 발생하지 않는다.
2024.01.13 - [Language/C++] - [C++] C++ 동작 원리
다시 말해, JAVA는 런타임환경에 들어가기 이전에 클래스로 변환하는 과정을 거쳐 JVM에 들어갈 수 있도록 코드가 변환한 후에 컴파일을 진행한다. 이렇게 되면 사실상 먼저 함수 선언을 진행하지 않아도 되는데, C++은 바로 컴파일을 진행하게 된다. 그렇기 때문에 함수 호출 전 미리 함수가 생성되어있어야 한다.
이번 코테에는 그렇게 활용하지 않았지만 대게 아래와 같은 방식으로 미리 함수를 정의해 놓고 아래에 함수를 다시 작성해서 추가적으로 코드를 작성하는 방법도 있다.(다음번에는 그렇게 해야지... main위에 함수를 적는게 익숙하지 않다)
#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
#include <iomanip>
#include <sstream>
using namespace std;
struct Reservation {
string roomName; // 회의실 이름
int startTime, endTime; // 회의 시작 시간과 종료ㅁ 시간
};
//미리 정의
vector<string> splitString(string str, char delimiter);
//미리 정의
void findAvailableTimes(const map<string, vector<pair<int, int>>>& reservations);
int main() {
// 입력 로직
findAvailableTimes(reservations); // 사용 가능한 시간 찾기
return 0;
}
vector<string> splitString(string str, char delimiter) {
//로직
}
// 예약되지 않은 시간을 찾아 출력하는 함수
void findAvailableTimes(const map<string, vector<pair<int, int>>>& reservations) {
//로직
}
# C++ 문법 - 문자열
c++은 안타깝게도 문자열을 구분자로 쪼개는 spilt함수가 없다. 그래서 구분자로 문자열을 나누는 함수를 구분하기 위해서는 split 함수를 구현해줘야 한다. 코테에서 많이 쓰일 거 같아서 따로 정리해 두었다. stringstream은 문자열에서 내가 원하는 자료형의 데이터를 추출할 수 있게 만들어졌다.
#include <sstream>
// 문자열을 구분자로 분할하는 함수
vector<string> splitString(string str, char delimiter) {
vector<string> result;
string token;
stringstream ss(str);
while (getline(ss, token, delimiter)) {
result.push_back(token);
}
return result;
}
그 이외에도 마찬가지 setw, setfill처럼 조정자 함수도 사용했다. #include <iomanip> 헤더를 끌고 와서 사용하면 된다.
#include <iomanip>
for (const auto& time : availableTimes) {
cout << setfill('0') << setw(2) << time.first << "-"
<< setw(2) << time.second << endl;
}
setw(숫자) ➡️ 출력시 길이를 지정
setfill(채울 데이터) ➡️ 빈공간을 데이터를 채움
항상 코테풀때는 문자열이 제일 어렵다. 논외이긴 하지만 문자열을 잘 풀려면 정규식을 통해서 원하는 결과를 잘 얻어낼 수 있다....! 어느 정도 코드가 익숙해지면 공부를 해봐야겠다.
# 풀이 및 해설 - 빡구현
문제나 코드 줄을 보면 알겠지만, 정확히 구현문제이다. 출력되는 것도 그렇고 오름차순 정렬도 그렇고 항상 이런 문제를 접근할 때는 위에서 말한 방법대로 함수로 다 쪼개서 문제를 푸는 게 제일 베스트이다. 난 아래와 같이 순서를 정했다.
- 입력
- 예약정보를 시간순으로 정렬
- 09 - 18까지 순회를 하면서 예약된 시간을 제외하고 나머지 가능한 시간을 찾는다.
- 출력
또한, 많은 자료구조를 사용했는데 map, pair, vector처럼 적재적소에 맞게 자료구조를 사용해서 구현하였다.
회의실 이름 별로 회의 시작, 회의 끝 시간을 map에 저장하게 되었다. 아래와 같다.
- 회의실 이름: avante ➡️ map의 key
- 11-12 ➡️map의 values의 vector 값 중 하나 pair로 first에 시작 시간, second로 끝 시간
- 13-15 ➡️map의 values의 vector 값 중 하나 pair로 first에 시작 시간, second로 끝 시간
- 16-17 ➡️map의 values의 vector 값 중 하나 pair로 first에 시작 시간, second로 끝 시간
사실 이 구조를 짜면서 머릿속으로 엄청난 고민들을 했다. 눈에 보이 지를 않으니.... 다 stl로 해서 캡슐화가 되어있는 상태였고 또 구조체로도 묶여있는 자료구조였다. 디버깅 자체가... 너무 힘들었다. for 문이나 iterator로 묶여있는걸 다시 다 벗겨내어 연산도 진행해야 했다. 무튼 풀기는 했지만 구현 문제는 항상 풀고 나면 진이 다 빠져나가는 기분이다.
'Algorithm > Problem' 카테고리의 다른 글
[Softeer] 우물 안 개구리(Lv.3) - Day3 (0) | 2024.01.29 |
---|---|
[Softeer] GBC(Lv.2) - Day3 (0) | 2024.01.29 |
[Softeer] 금고털이(Lv.2) - Day2 (0) | 2024.01.29 |
[Softeer] 근무 시간(Lv.1) - Day1 (0) | 2024.01.26 |
[Softeer] A+B(Lv.1) - Day1 (0) | 2024.01.26 |