[Programmers, C++]#Level2_ 호텔 대실, substr, sort 알고리즘, 우선순위 큐, 최소 힙 우선순위 큐

2024. 10. 3. 16:11· 문제 풀이/Programmers 문제 풀이
목차
  1. #1. 문제
  2. #2. 풀이
  3. 1. sort
  4. 2. 우선순위 큐
  5. 3. 현재 예약 건의 대실 시작 시간과 우선순위 큐의 종료 시간 비교!
  6. #3. 코드

#1. 문제

 

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

 

 


 

#2. 풀이

 

1. sort

 

[Basic C++] #32-3_STL 정렬 알고리즘

[Basic C++] #32-3_STL 정렬 알고리즘 C++ 개발에서 표준 라이브러리(STL)에 대해 알아보겠습니다. "전문가를 위한 C"의 15 항목, "C++ 표준 라이브러리 살펴보기"에 해당하는 내용입니다. Overview 개념 partiti

webddevys.tistory.com

sort 알고리즘은 C++의 STL에서 제공하는 정렬 알고리즘으로, 컨테이너의 begin()과 end()를 전달하고, 정렬 기준을 설정하여 컨테이너 내부 항목들을 기준에 맞춰 정렬하는 알고리즘입니다. sort 알고리즘의 default 정렬 기준은 오름차순입니다.

 

2. 우선순위 큐

 

[Basic C++] #69_priority_queue

[Basic C++] #69_priority_queue C++의 STL에서 제공하는 priority_queue컨테이너에 대해 알아보겠습니다. Overview 개념 선언 멤버 함수 예제 #0. 개념 1. 우선순위 큐? [자료구조]#7_우선순위 큐 [자료구조]#7_우선

webddevys.tistory.com

우선순위 큐는 각 항목에 우선순위를 부여하고, 우선순위가 가장 높은 항목에 대해서 삽입/접근/삭제 작업을 허용하는 자료구조입니다. 일반적으로, 우선순위 큐는 최소/최대 힙을 통해 구현가능합니다. 

 

3. 현재 예약 건의 대실 시작 시간과 우선순위 큐의 종료 시간 비교!

  1. 먼저, 입력으로 주어진 시작 시간과 종료 시간을 파싱 하고, 분 단위로 값을 변경해 주어 pair 형식으로 목록을 구성합니다.
  2. 만들어진 목록을 first(시작 시간)을 기준으로 오름차순 정렬해 줍니다.
  3. 다음으로, 우선순위 큐(최소 힙)를 활용하여, 우선순위 큐에서 시작 시간이 가장 빠른 항목의 종료 시간 + 10과 현재 순회 중인 항목의 시작 시간을 비교하고, 새로운 방이 필요 없는지 확인해 줍니다.

 


 

#3. 코드

@@ -0,0 +1,61 @@
/*
    @링크: https://school.programmers.co.kr/learn/courses/30/lessons/155651
    @문제: 호텔 대실
    @설명
        1. 정렬: 예악 시작 시간 기준 오름차순 정렬
        2. 우선순위 큐(최소 힙): 호텔 각 방의 예약 종료 시간을 기준으로 최소 힙 구성
*/

#include <string>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

typedef pair<int,int> p;

int solution(vector<vector<string>> book_time) {
    int answer = 0;

    //@ {시작 시간, 종료 시간}
    vector<p> books;

    //@':' 기준 왼쪽을 first, 오른쪽을 second로 파싱
    for(int i=0; i<book_time.size(); ++i)
    {
        int startHour = stoi(book_time[i][0].substr(0, 2));
        int startTimeInMin = startHour * 60 + stoi(book_time[i][0].substr(3,2));

        int endHour = stoi(book_time[i][1].substr(0, 2));
        int endTimeInMin = endHour * 60 + stoi(book_time[i][1].substr(3,2));

        books.push_back({startTimeInMin, endTimeInMin});
    }

    //@시작 시간 기준 오름차순 정렬
    sort(begin(books), end(books), [](const p& a, const p& b)
    {
        return a.first < b.first;
    });

    //@종료 시간 기준 '최소 힙' 구성
    priority_queue<int, vector<int>, greater<int>> pq;
 
    //@우선순위 큐 활용
    for(int i=0; i<(int)books.size(); ++i)
    {
        //@최소 종료 시간 + 10 과 현재 예약 시작 시간 비교
        if(!pq.empty() && pq.top()+10 <= books[i].first)
        {
            pq.pop();
        }
        else
        {
            answer++;
        }
        
        pq.push(books[i].second);
    }

    return answer;
}

 


 

 

 

저작자표시 (새창열림)

'문제 풀이 > Programmers 문제 풀이' 카테고리의 다른 글

[Programmers, C++]#Level2_전력 망을 둘로 나누기, DFS, 깊이 우선 탐색, 재귀 DFS, 트리, 트리의 DFS  (0) 2024.10.08
[Programmers, C++]#Level2_마법의 엘리베이터, 올림, 내림, 반올림, 10진수 자릿수 구분  (0) 2024.09.24
[Programmers, C++]#Level3_스티커 모으기(2), 동적 계획법, DP, Dynamic Programming, 점화식  (0) 2024.09.20
[Programmers, C++]#Level2_최솟값 만들기, 우선순위 큐, 최소 힙, 최대 힙, 완전 이진 트리  (0) 2024.09.20
[Programmers, C++]#Level2_올바른 괄호, 스택, stack  (0) 2024.09.12
  1. #1. 문제
  2. #2. 풀이
  3. 1. sort
  4. 2. 우선순위 큐
  5. 3. 현재 예약 건의 대실 시작 시간과 우선순위 큐의 종료 시간 비교!
  6. #3. 코드
'문제 풀이/Programmers 문제 풀이' 카테고리의 다른 글
  • [Programmers, C++]#Level2_전력 망을 둘로 나누기, DFS, 깊이 우선 탐색, 재귀 DFS, 트리, 트리의 DFS
  • [Programmers, C++]#Level2_마법의 엘리베이터, 올림, 내림, 반올림, 10진수 자릿수 구분
  • [Programmers, C++]#Level3_스티커 모으기(2), 동적 계획법, DP, Dynamic Programming, 점화식
  • [Programmers, C++]#Level2_최솟값 만들기, 우선순위 큐, 최소 힙, 최대 힙, 완전 이진 트리
Hardii2
Hardii2
Hardii2
개발 블로그
Hardii2
전체
오늘
어제
  • 분류 전체보기
    • 알고리즘
    • 웹 개발
      • Node.js
      • React
    • 게임개발
      • DirectX12
      • 관련 지식
      • Unreal C++
      • Unreal 블루프린트
    • 언어
      • Effective C++
      • Basic C++
      • 디자인 패턴
      • 자료구조
      • 기술 질문
    • 문제 풀이
      • BOJ 문제 풀이
      • Programmers 문제 풀이
      • geeksForgeeks 문제 풀이
    • 수학
      • 확률과 통계
      • 게임수학
    • 개인프로젝트
    • 그룹프로젝트
      • PM
      • Dev
    • Github

블로그 메뉴

  • 홈
  • 글쓰기

공지사항

인기 글

태그

  • programmers
  • Unreal Blueprint
  • 우선순위 큐
  • 알고리즘
  • 정렬
  • 디자인 패턴
  • BOJ
  • 트리
  • set
  • stl
  • 기술 질문
  • 그래프
  • 개발
  • dfs
  • DP
  • C++
  • unreal
  • Effective C++
  • 최단 경로
  • BFS

최근 댓글

최근 글

hELLO · Designed By 정상우.v4.2.2
Hardii2
[Programmers, C++]#Level2_ 호텔 대실, substr, sort 알고리즘, 우선순위 큐, 최소 힙 우선순위 큐
상단으로

티스토리툴바

개인정보

  • 티스토리 홈
  • 포럼
  • 로그인

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.