Move Fast

문제

• 문제 링크
• 문제 설명: 왼쪽 그림에 소개된 블록들만 배치된 2차원 배열 보드가 주어질 때 오른쪽 그림과 같이 검은 블록을 떨어뜨려 속이 꽉 찬 직사각형을 만들어 없앨 수 있다. 이 때 제거 가능한 블록의 최대 개수를 반환하는 함수를 작성하라.

• 입력: 보드의 원소는 0~200 사이의 자연수이며 0은 빈칸, 나머지 숫자는 블록의 번호이다.
• 출력: 제거 가능한 블록의 최대 개수

풀이

• 없앨 수 있는 블록은 아래 그림처럼 위가 비어있으면서 블록 위쪽에 다른 블록이 없는 경우

• 블록의 모양을 확인하는 방법
  • 아래와 같이 블록 번호별로 좌표를 순서대로 저장하면 좌표를 비교해서 블록 모양을 알아낼 수 있음

vector<pii> v[201]; // 블록당 좌표
for (int y = 0; y < N; y++)
    for (int x = 0; x < N; x++)
        if (board[y][x] > 0)
            v[board[y][x]].push_back({y, x});

• canDelete(block) := Y좌표값과 X좌표값을 비교하여 블록 모양을 검사한 뒤 위쪽에 막고 있는 블록이 없는지 검사하여 검은 블록을 모두 놓을 수 있으면 true를 반환, 아니면 false
• 블록은 위쪽부터 하나씩 없애야 가장 많이 없앨 수 있기 때문에 차례대로 제거해준다.
• 정답 코드

#include <string>
#include <vector>
#define Y first
#define X second
using namespace std;
typedef pair<int,int> pii;

vector<pii> v[201]; // 블록당 좌표
int N;

bool canDelete(int block, vector<vector<int>>& board) {
    vector<pii> c = v[block];
    if (c[1].Y == c[2].Y and c[1].Y == c[3].Y) { // 아래 3개의 사각형, 위에 1개 사각형 있는 경우
        if (c[0].Y + 1 == c[1].Y) {
            int tmp[2];
            if (c[0].X == c[1].X) tmp[0] = c[2].X, tmp[1] = c[3].X;
            else if (c[0].X == c[2].X) tmp[0] = c[1].X, tmp[1] = c[3].X;
            else if (c[0].X == c[3].X) tmp[0] = c[1].X, tmp[1] = c[2].X;
            for (int i = c[0].Y; i >= 0; i--)
                if (board[i][tmp[0]] > 0 or board[i][tmp[1]] > 0)
                    return false;
            return true;
        }
    } else if (c[0].X == c[1].X and c[2].Y == c[3].Y) { // 세로로 3개 사각형이 있는 경우
        int tmp;
        if (c[0].X == c[2].X) tmp = c[3].X;
        else if (c[0].X == c[3].X) tmp = c[2].X;
        else return false;
        for (int i = c[2].Y-1; i >= 0; i--)
            if (board[i][tmp] > 0) return false;
        return true;
    }
    return false;
}

int solution(vector<vector<int>> board) {
    int answer = 0;
    N = board.size();
    for (int y = 0; y < N; y++)
        for (int x = 0; x < N; x++)
            if (board[y][x] > 0)
                v[board[y][x]].push_back({y, x});
    
    for (int y = 0; y < N; y++) {
        for (int x = 0; x < N; x++) {
            int& blockNumber = board[y][x];
            if (blockNumber > 0) {
                if (canDelete(blockNumber, board)) {
                    answer++;
                    // 블록 제거
                    for (auto& p : v[blockNumber]) board[p.Y][p.X] = 0;
                }
            }
        }
    }
    return answer;
}

문제

• 문제 링크
• 문제 설명: 셔틀을 타고 사무실로 갈 수 있는 도착 시각 중 제일 늦은 시각을 구하는 함수를 작성
  • 셔틀은 09:00부터 총 n회 t분 간격으로 역에 도착하며, 하나의 셔틀에는 최대 m명의 승객이 탈 수 있다.
  • 셔틀은 도착했을 때 도착한 순간에 대기열에 선 크루까지 포함해서 대기 순서대로 태우고 바로 출발한다. 예를 들어 09:00에 도착한 셔틀은 자리가 있다면 09:00에 줄을 선 크루도 탈 수 있다.
  • 단, 콘은 게으르기 때문에 같은 시각에 도착한 크루 중 대기열에서 제일 뒤에 선다. 또한, 모든 크루는 잠을 자야 하므로 23:59에 집에 돌아간다. 따라서 어떤 크루도 다음날 셔틀을 타는 일은 없다.
• 입력
  • 셔틀 운행 횟수 n, 셔틀 운행 간격 t, 한 셔틀에 탈 수 있는 최대 크루 수 m, 크루가 대기열에 도착하는 시각을 모은 배열 timetable
  • 0 ＜ n ≦ 10
  • 0 ＜ t ≦ 60
  • 0 ＜ m ≦ 45
  • timetable은 최소 길이 1이고 최대 길이 2000인 배열로, 하루 동안 크루가 대기열에 도착하는 시각이 HH:MM 형식
  • 크루의 도착 시각 HH:MM은 00:01에서 23:59 사이
• 출력: 셔틀을 타고 사무실로 갈 수 있는 제일 늦은 도착 시각

풀이

• 마지막 차 시간에 m보다 적게 탄다면 마지막 차 출발 시각이 정답이 되고, 마지막 차 시간에 m 이상 탄다면 마지막 탑승자의 도착 시각보다 1분 일찍 와있어야 함.
• 시간을 모두 분 단위로 바꿔서 우선순위 큐에 삽입
• 9:00 부터 t분 간격으로 n-1회 루핑을 돌면서 대기열에 시간들 중 현재 시간 이하의 도착 시각들을 빼낸다.
• 마지막 차일 때 탑승가능한 사람 수를 구함
  • m명 이상이면 timetable의 m번째 도착 시간 - 1 을 반환
  • m명보다 작으면 마지막 차의 시각을 반환
• 정답 코드

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

string solution(int n, int t, int m, vector<string> timetable) {
    // 모든 시간을 분 단위로 바꿔서 우선순위 큐에 삽입
    priority_queue<int> pq;
    for (auto& s : timetable) {
        int minutes = ((s[0]-'0')*10 + (s[1]-'0')) * 60 + (s[3]-'0')*10 + (s[4]-'0');
        pq.push(-minutes); // 큰 값이 맨 위에 오기 때문에 -1을 곱해서 작은 값이 오도록 함
    }
    
    // 마지막 차 시간이 올 때까지 우선순위 큐에서 탑승가능한 사람들을 빼냄
    int busTime = 9*60;
    for (int i = 0; i < n-1; i++, busTime += t)
        for (int j = 0; j < m; j++)
            if (pq.empty() or -pq.top() > busTime) break;
            else pq.pop();
    
    // 마지막 차 시간에 마지막으로 탑승하는 사람의 도착 시각 - 1 구하기
    int arrivalTime;
    while (!pq.empty() and m) {
        if (-pq.top() <= busTime) {
            arrivalTime = -pq.top() - 1;
            pq.pop();
            m--;
        } else break;
    }
    
    if (m > 0) arrivalTime = busTime; // 막차에 자리가 있으면 버스 도착 시각으로 변경
    char tmp[6];
    sprintf(tmp, "%02d:%02d", arrivalTime / 60, arrivalTime % 60);
    return string(tmp);
}

문제

• 문제 링크
• 문제 설명: 로그 데이터를 분석한 후 초당 최대 처리량을 계산해보기로 했다. 초당 최대 처리량은 요청의 응답 완료 여부에 관계없이 임의 시간부터 1초(=1,000밀리초)간 처리하는 요청의 최대 개수를 의미한다.
• 입력
  • lines 배열은 N(1 ≦ N ≦ 2,000)개의 로그 문자열로 되어 있으며, 각 로그 문자열마다 요청에 대한 응답완료시간 S와 처리시간 T가 공백으로 구분되어 있다.
  • 응답완료시간 S는 작년 추석인 2016년 9월 15일만 포함하여 고정 길이 2016-09-15 hh:mm:ss.sss 형식으로 되어 있다.
  • 처리시간 T는 0.1s, 0.312s, 2s 와 같이 최대 소수점 셋째 자리까지 기록하며 뒤에는 초 단위를 의미하는 s로 끝난다.
  • 예를 들어, 로그 문자열 2016-09-15 03:10:33.020 0.011s은 "2016년 9월 15일 오전 3시 10분 33.010초"부터 "2016년 9월 15일 오전 3시 10분 33.020초"까지 "0.011초" 동안 처리된 요청을 의미한다. (처리시간은 시작시간과 끝시간을 포함)
  • 서버에는 타임아웃이 3초로 적용되어 있기 때문에 처리시간은 0.001 ≦ T ≦ 3.000이다
• 출력: 초당 최대 처리량

풀이

• 밀리세컨즈까지 문자열에 포함되므로 모든 로그를 ms 단위로 변환
• 요청량이 변하는 부분은 로그의 시작과 끝이므로, 시작부터 시작+1초 구간과 끝부터 끝+1초 구간에서 다른 로그들과 겹친다면 겹치는 개수를 카운트한다.
  • 응답 완료 시간을 기준으로 오름차순 정렬되어 있기 때문에 i번째 로그와 겹치는 로그를 찾을 때는 i+1번째 로그부터 하나씩 탐색해보면 된다.
  • i+1번째 이후부터 로그의 인덱스를 j라고 할 때 로그가 겹치는 구간
    • i번째 로그의 시작 시각 + 1초 >= j번째 로그의 요청 시작 시각
    • i번째 로그의 끝 시각 + 1초 > j번째 로그의 요청 시작 시각
  • 어차피 i+1 이후의 로그들은 응답 완료 시각이 i번째 로그의 응답 완료 시각보다 크거나 같기 때문에 별도로 검사해줄 필요는 없다.
• 카운트한 것들 중 가장 큰 값을 반환
• 정답 코드

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

// 시간 포맷을 밀리세컨즈 단위로 변환
int timeToMilli(const string& s) {
    int hh = (s[0]-'0')*10 + (s[1]-'0');
    int mm = (s[3]-'0')*10 + (s[4]-'0');
    int ss = (s[6]-'0')*10 + (s[7]-'0');
    int ms = (s[9]-'0')*100 + (s[10]-'0')*10 + (s[11]-'0');
    return hh*3600000 + mm*60000 + ss*1000 + ms;
}

// 초 단위 시간 포맷을 밀리세컨즈 단위로 변환
int secToMilli(const string& s) {
    int ms = (s[0]-'0') * 1000;
    if (s[1] == '.')
        for (int i = 2, d = 100; s[i] != 's'; i++, d /= 10)
            ms += (s[i]-'0')*d;
    return ms;
}

int solution(vector<string> lines) {
    vector<vector<int>> timestamp;
    for (auto& s : lines) {
        istringstream iss(s);
        string data[3];
        iss >> data[0] >> data[1] >> data[2];
        int endms = timeToMilli(data[1]) + 2999;
        int duration = secToMilli(data[2]);
        int startms = endms - duration + 1;
        timestamp.push_back({startms, endms});
    }
    
    int answer = 0;
    for (int i = 0; i < timestamp.size(); i++) {
        int num = 1;
        int startms = timestamp[i][0] + 1000;
        int endms = timestamp[i][1] + 1000;
        // 다음 로그에 대해 겹치는 개수를 카운트
        for (int j = i+1; j < timestamp.size(); j++)
            if (startms >= timestamp[j][0] or endms > timestamp[j][0])
                num++;
        answer = max(answer, num);
    }
    return answer;
}

문제

• 문제 링크
• 문제 설명: 단어 목록 words가 주어질 때, 매 단어를 자동완성하기 위해 입력해야 하는 글자 수의 총합을 반환하는 함수를 작성하라. 접두사가 겹치는 경우는 겹치지 않을 때까지 입력하거나 단어를 모두 입력해야 한다.
• 입력
  • 학습과 검색에 사용될 중복 없는 단어 N개가 주어진다. 
  • 모든 단어는 알파벳 소문자로 구성되며 단어의 수 N과 단어들의 길이의 총합 L의 범위는 다음과 같다.
  • 2 <= N <= 100,000
  • 2 <= L <= 1,000,000
• 출력: 단어를 자동완성하기 위해 입력해야하는 글자 수의 총합

풀이

• 단어들의 길이 총합이 100만이므로 O(N)으로 문제를 해결해야 함
• 트라이로 구현해서 단어들이 겹치는 문자들에 대해 카운트 변수를 유지(=트라이노드의 멤버변수)
  • 삽입할 때마다 카운트 변수를 증가
• 검색할 때 단어의 끝 또는 카운트가 1이 되는 순간(=후보 단어가 하나 밖에 없는 경우) 길이를 계산해서 반환하도록 한다.
• 시간 복잡도: O(L)
• 정답 코드

#include <cstring>
#include <string>
#include <vector>
using namespace std;

struct TrieNode {
    bool terminal;
    TrieNode* children[26];
    int count;
    
    TrieNode() : terminal(false), count(0) {
        memset(children, 0, sizeof(children));
    }
    
    void insert(int pos, const string& s) {
        if (pos < s.size()) {
            int idx = s[pos] - 'a';
            if (children[idx] == 0)
                children[idx] = new TrieNode();
            children[idx]->insert(pos + 1, s);
        } else terminal = true;
        count++; // 단어 카운트
    }
    
    int search(int pos, const string& s) {
        // base case: 찾는 단어의 끝이거나 후보 단어가 1개 밖에 없으면 재귀 종료
        if ((pos == s.size() and terminal) or count == 1) return 0;
        return children[s[pos]-'a']->search(pos + 1, s) + 1;
    }
};

int solution(vector<string> words) {
    TrieNode* root = new TrieNode();
    for (auto& s : words) root->insert(0, s);
    int answer = 0;
    for (auto& s : words) answer += root->search(0, s);
    return answer;
}