오늘의 문제
호텔 대실
무인도 여행
뒤에 있는 큰 수 찾기

호텔 대실

문제 설명
호텔을 운영 중인 코니는 최소한의 객실만을 사용하여 예약 손님들을 받으려고 합니다. 한 번 사용한 객실은 퇴실 시간을 기준으로 10분간 청소를 하고 다음 손님들이 사용할 수 있습니다.
예약 시각이 문자열 형태로 담긴 2차원 배열 book_time이 매개변수로 주어질 때, 코니에게 필요한 최소 객실의 수를 return 하는 solution 함수를 완성해주세요.

제한사항

• 1 ≤ book_time의 길이 ≤ 1,000
  • book_time[i]는 ["HH:MM", "HH:MM"]의 형태로 이루어진 배열입니다
    • [대실 시작 시각, 대실 종료 시각] 형태입니다.
  • 시각은 HH:MM 형태로 24시간 표기법을 따르며, "00:00" 부터 "23:59" 까지로 주어집니다.
    • 예약 시각이 자정을 넘어가는 경우는 없습니다.
    • 시작 시각은 항상 종료 시각보다 빠릅니다.

코드

#include <bits/stdc++.h>
using namespace std;

bool cmp (vector<string> t1, vector<string> t2) {
    if(t1[1].substr(0, 2) == t2[1].substr(0, 2)) {
        return t1[1].substr(3) < t2[1].substr(3); 
    }
    return t1[1].substr(0, 2) < t2[1].substr(0, 2);
}

bool same(vector<string> t1, vector<string> t2) {
    int fh = stoi(t1[1].substr(0, 2));
    int fm = stoi(t1[1].substr(3)) + 10;
    if(fm >= 60) {
        fm -= 60; fh += 1;
    }
    int ih = stoi(t2[0].substr(0, 2));
    int im = stoi(t2[0].substr(3));
    
    if(fh < ih) return true;
    else if(fh == ih) return fm <= im;
    else return false;
}

int solution(vector<vector<string>> book_time) {
    sort(book_time.begin(), book_time.end(), cmp);
    
    vector<vector<string>> room;
    room.emplace_back(book_time[0]);
    for(int i = 1; i < book_time.size(); i++){
        for(int j = room.size() - 1; j >= 0 ; j--) {
            if(same(room[j], book_time[i])) {
                room.erase(room.begin() + j);
                break;
            }
        }
        room.emplace_back(book_time[i]);
    }
    return room.size();
}

시간을 다 int형으로 나타내서 priority_queue를 쓸 걸~!~!

무인도 여행

문제 설명
메리는 여름을 맞아 무인도로 여행을 가기 위해 지도를 보고 있습니다. 지도에는 바다와 무인도들에 대한 정보가 표시돼 있습니다. 지도는 1 x 1크기의 사각형들로 이루어진 직사각형 격자 형태이며, 격자의 각 칸에는 'X' 또는 1에서 9 사이의 자연수가 적혀있습니다. 지도의 'X'는 바다를 나타내며, 숫자는 무인도를 나타냅니다. 이때, 상, 하, 좌, 우로 연결되는 땅들은 하나의 무인도를 이룹니다. 지도의 각 칸에 적힌 숫자는 식량을 나타내는데, 상, 하, 좌, 우로 연결되는 칸에 적힌 숫자를 모두 합한 값은 해당 무인도에서 최대 며칠동안 머물 수 있는지를 나타냅니다. 어떤 섬으로 놀러 갈지 못 정한 메리는 우선 각 섬에서 최대 며칠씩 머물 수 있는지 알아본 후 놀러갈 섬을 결정하려 합니다.

지도를 나타내는 문자열 배열 maps가 매개변수로 주어질 때, 각 섬에서 최대 며칠씩 머무를 수 있는지 배열에 오름차순으로 담아 return 하는 solution 함수를 완성해주세요. 만약 지낼 수 있는 무인도가 없다면 -1을 배열에 담아 return 해주세요.

제한사항

• 3 ≤ maps의 길이 ≤ 100
  • 3 ≤ maps[i]의 길이 ≤ 100
  • maps[i]는 'X' 또는 1 과 9 사이의 자연수로 이루어진 문자열입니다.
  • 지도는 직사각형 형태입니다.

코드

#include <bits/stdc++.h>
using namespace std;

int n, m;
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};
vector<vector<int>> vis;
vector<string> _maps;

int bfs(int x, int y) {
    queue<pair<int, int>> q;
    q.push({x, y});
    int sz = _maps[x][y] - '0';
    vis[x][y] = 1;
    
    while(!q.empty()) {
        x = q.front().first;
        y = q.front().second;
        q.pop();
        
        for(int i = 0; i < 4; i++){
            int nx = x + dx[i];
            int ny = y + dy[i];
            
            if(nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
            if(vis[nx][ny] || _maps[nx][ny] == 'X') continue;
            
            q.push({nx, ny});
            sz += _maps[nx][ny] - '0';
            vis[nx][ny] = 1;
        }
    }
    return sz;
}

vector<int> solution(vector<string> maps) {
    n = maps.size(); m = maps[0].size(); _maps = maps;
    vis = vector<vector<int>>(n, vector<int>(m, 0));
    vector<int> answer;
    
    for(int i = 0; i < n; i++){ 
        for(int j = 0; j < m; j++){
            if(!vis[i][j] && maps[i][j] != 'X') {
                answer.emplace_back(bfs(i, j));
            }
        }
    }
    if(answer.empty()) return {-1};
    sort(answer.begin(), answer.end());
    return answer;
}

평범한 bfs 문제였다

뒤에 있는 큰 수 찾기

문제 설명
정수로 이루어진 배열 numbers가 있습니다. 배열 의 각 원소들에 대해 자신보다 뒤에 있는 숫자 중에서 자신보다 크면서 가장 가까이 있는 수를 뒷 큰수라고 합니다.
정수 배열 numbers가 매개변수로 주어질 때, 모든 원소에 대한 뒷 큰수들을 차례로 담은 배열을 return 하도록 solution 함수를 완성해주세요. 단, 뒷 큰수가 존재하지 않는 원소는 -1을 담습니다.

제한사항

• 4 ≤ numbers의 길이 ≤ 1,000,000
  • 1 ≤ numbers[i] ≤ 1,000,000

코드

테스트 21, 22에서 시간 초과

#include <bits/stdc++.h>
using namespace std;

vector<int> solution(vector<int> numbers) {
    vector<int> answer(numbers.size(), -1);
    for(int i = numbers.size() - 2; i >= 0; i--) {
        if(numbers[i] < numbers[i + 1]) answer[i] = numbers[i + 1];
        else if(numbers[i] == numbers[i + 1]) answer[i] = answer[i + 1];
        else {
            if(numbers[i] >= answer[i + 1]) {
                for(int j = i + 1; j < numbers.size(); j++){
                    if(numbers[i] < numbers[j]) {
                        answer[i] = numbers[j];
                        break;
                    }
                }
            }
            else answer[i] = answer[i + 1];
        }
    }
    return answer;
}

시간 초과일 것 같다고 생각했다..
이 코드에서는 else 문에 들어갔을 때, numbers[i]보다 큰 값이 없는 경우 for문을 끝까지 돌기 때문에 중간에 탈출할 수 있는 구문을 만들어줘야겠다고 생각했다.

 else {
	if(numbers[i] >= answer[i + 1]) {
		for(int j = i + 1; j < numbers.size(); j++){
			if(numbers[i] < numbers[j]) {
				answer[i] = numbers[j];
				break;
			}
            if(numbers[i] >= numbers[j] && answer[j] == -1) break;
	}
}

이렇게 했더니 21번은 통과했다. 22번은 도대체 뭐지?!

잠깐 생각해본 결과 [5, 4, 1, 2, 3, 4, 5, 6] 이런 식으로 들어있으면 시간 초과가 발생할거라는 것을 알아냈다. 그래서 stack을 이용하기로 했다.

성공

#include <bits/stdc++.h>
using namespace std;

vector<int> solution(vector<int> numbers) {
    vector<int> answer(numbers.size(), -1);
    stack<int> st;
    for(int i = numbers.size() - 2; i >= 0; i--) {
        
        if(numbers[i] < numbers[i + 1]) {
            answer[i] = numbers[i + 1];
            st.push(numbers[i + 1]);
        }
        else if(numbers[i] == numbers[i + 1]) answer[i] = answer[i + 1];
        else {
            if(numbers[i] < answer[i + 1]) answer[i] = answer[i + 1];
            else {
                while(!st.empty()) {
                    if(numbers[i] < st.top()) {
                        answer[i] = st.top();
                        st.push(answer[i]);
                        break;
                    }
                    st.pop();
                }
            }
        }
    }
    return answer;
}