문제

  • 문제 링크
  • 문제 설명: 로그 데이터를 분석한 후 초당 최대 처리량을 계산해보기로 했다. 초당 최대 처리량은 요청의 응답 완료 여부에 관계없이 임의 시간부터 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
  • 출력: 단어를 자동완성하기 위해 입력해야하는 글자 수의 총합
words result
["go","gone","guild"] 7
["abc","def","ghi","jklm"] 4
["word","war","warrior","world"] 15

풀이

  • 단어들의 길이 총합이 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;
}

문제

  • 문제 링크
  • 문제 설명: 1초마다 회전하는 음식판이 있다. 1번부터 N번까지 음식 번호가 증가하는 순서대로 음식을 섭취할 때, K초에 네트워크 장애가 발생한다면 네트워크 정상화 후 먹어야하는 음식의 번호를 반환하는 함수를 작성하라.
    • 음식을 모두 섭취했다면 가장 가까운 음식이 다음 대상이 된다.
    • 마지막 번호의 음식을 섭취한 후에는 회전판에 의해 다시 1번 음식이 무지 앞으로 온다.
  • 입력
    • food_times 는 각 음식을 모두 먹는데 필요한 시간이 음식의 번호 순서대로 들어있는 배열이다.
    • k 는 방송이 중단된 시간을 나타낸다.
    • food_times 의 길이는 1 이상 200,000 이하이다.
    • food_times 의 원소는 1 이상 100,000,000 이하의 자연수이다.
    • k는 1 이상 2 x 10^13 이하의 자연수이다.
  • 출력: 네트워크 정상화 후 먹어야하는 음식 번호
    • 만약 더 섭취해야 할 음식이 없다면 -1을 반환하면 된다.
food_times k result
[3, 1, 2] 5 1

풀이

  • food_times의 길이가 2*10^5 이기 때문에 O(N) 또는 O(NlogN) 만에 해결해야 함
  • 먼저 모든 음식들을 우선순위 큐에 삽입
    • 원소 := (섭취시간, 인덱스)
    • 우선순위 큐는 가장 큰 값을 top() 으로 반환하므로 -1을 곱해서 섭취시간이 가장 작은 것을 O(1)에 얻을 수 있도록 한다.
  • 섭취 시간에 대해 다음과 같은 변수를 사용
    • food_items[i] := i번째 음식이 섭취하는데 필요한 시간
    • totalTime := 지금까지 총 걸린 시간
    • t := 현재 음식 하나를 먹을 때 섭취 시간 (최초 최소 섭취 시간)
    • n := 현재 남은 음식 개수
    • tsum := 지금까지 t가 누적된 섭취 시간
  • 큐에서 총 섭취 시간이 k이하이면 음식을 섭취하고 시간을 갱신
    • tsum += t; (최초 tsum = 0)
    • 섭취 시간 <= tsum 인 음식들만 섭취 
    • 1번 먹는데 걸린 시간: 현재 음식 하나를 먹을 때 섭취 시간 * 남은 음식 개수 = t * n
    • 1번 먹고난 후 시간: totalTime + (t * n)
    • t = -pq.top() - tsum; // 우선순위 큐는 가장 큰 값을 top 에 두기 때문에 -1을 곱해서 작은값을 위로
    • n = pq.size()
  • 총 섭취 시간이 k 보다 크면 섭취 시간을 줄일 것
    • 섭취 시간이 이미 1이면 break
    • t = (k - totalTime) / n;
    • ㄴ 이 결과가 1보다 작으면 k == totalTime 이기 때문에 네트워크 장애가 발생한 시점이므로 break
  • 남은 음식들 중 k - totalTime 번째 음식 번호를 반환
  • 정답 코드
#include <string>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
typedef long long ll;
typedef pair<ll,int> pli;

int solution(vector<int> food_times, long long k) {
    priority_queue<pli> pq;
    ll n = food_times.size(); // 현재 남은 음식 개수
    ll totalTime = 0; // 지금까지 총 걸린 시간
    ll t = 1e9; // 현재 음식 하나를 먹을 때 섭취 시간
    ll tsum = 0; // 지금까지 t가 누적된 섭취 시간
    for (int i = 0; i < n; i++) {
        pq.push({-food_times[i], i+1});
        if (food_times[i] < t) t = food_times[i];
    }
    
    while (!pq.empty()) {
        if (totalTime + t * n > k) {
            if (t == 1) break;
            t = (k - totalTime) / n; // 딱 k까지 필요한 섭취 시간 구하기
            if (t < 1) break; // k == totalTime 이면 네트워크 장애가 발생하니 종료
        }
        
        tsum += t; // 시간 누적
        while (-pq.top().first <= tsum) {
            pq.pop();
            if (pq.empty()) return -1; // 이미 다먹었으면 -1
        }
        totalTime += t * n; // 총 시간 갱신
        t = -pq.top().first - tsum; // 음식 하나당 섭취 시간 갱신
        n = pq.size(); // 남은 음식 개수 갱신
    }
    
    vector<int> v;
    while(!pq.empty()) { v.push_back(pq.top().second); pq.pop(); }
    sort(v.begin(), v.end()); // 음식 번호 순으로 정렬
    return v.size() < k-totalTime ? -1 : v[k-totalTime];
}

 

문제

  • 문제 링크
  • 문제 설명: 가사에 사용된 모든 단어들이 담긴 배열 words와 찾고자 하는 키워드가 담긴 배열 queries가 주어질 때, 각 키워드 별로 매치된 단어가 몇 개인지 순서대로 배열에 담아 반환하는 함수 작성
  • 입력
    • 가사 단어 제한 사항
      • words의 길이(가사 단어의 개수)는 2 이상 100,000 이하입니다.
      • 각 가사 단어의 길이는 1 이상 10,000 이하로 빈 문자열인 경우는 없습니다.
      • 전체 가사 단어 길이의 합은 2 이상 1,000,000 이하입니다.
      • 가사에 동일 단어가 여러 번 나올 경우 중복을 제거하고 words에는 하나로만 제공됩니다.
      • 각 가사 단어는 오직 알파벳 소문자로만 구성되어 있으며, 특수문자나 숫자는 포함하지 않는 것으로 가정합니다.
    • 검색 키워드 제한 사항
      • queries의 길이(검색 키워드 개수)는 2 이상 100,000 이하입니다.
      • 각 검색 키워드의 길이는 1 이상 10,000 이하로 빈 문자열인 경우는 없습니다.
      • 전체 검색 키워드 길이의 합은 2 이상 1,000,000 이하입니다.
      • 검색 키워드는 중복될 수도 있습니다.
      • 각 검색 키워드는 오직 알파벳 소문자와 와일드카드 문자인 '?' 로만 구성되어 있으며, 특수문자나 숫자는 포함하지 않는 것으로 가정합니다.
      • 검색 키워드는 와일드카드 문자인 '?'가 하나 이상 포함돼 있으며, '?'는 각 검색 키워드의 접두사 아니면 접미사 중 하나로만 주어집니다.
  • 출력: 키워드별 매치된 단어 개수 배열
words queries result
["frodo", "front", "frost", "frozen", "frame", "kakao"] ["fro??", "????o", "fr???", "fro???", "pro?"] [3, 2, 4, 1, 0]

풀이

  • 전체 가사단어/검색키워드 길이의 합이 100만이 넘으므로 naive한 방법으로 탐색 시 시간 초과가 발생
  • 트라이로 문자열을 탐색하되, 각 노드(문자1개)는 이후 남은 길이에 대해 단어의 개수를 map에 저장 (있는 그대로 탐색할 경우 시간초과)
  • 와일드카드가 접두사/접미사에만 등장하므로 접두사 트라이와 접미사 트라이를 둘 다 구현해서 와일드 카드가 앞에 오면 접미사 트라이에서 탐색하고 와일드 카드가 뒤에 오면 접두사 트라이에서 탐색.
  • 전처리할 때 검색 키워드 길이의 합 100만만큼 비용이 소모된다. 매칭 개수 찾는 것은 전처리보다 적게 듬
  • 정답 코드
#include <cstring>
#include <string>
#include <vector>
#include <unordered_map>
#include <algorithm>
using namespace std;

struct TrieNode {
    bool terminal;
    TrieNode* children[26];
    unordered_map<int, int> m; // (len, cnt)
    
    TrieNode(): terminal(false) {
         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;
        m[s.size() - pos]++; // 남은 길이마다 단어 수 증가
    }
    
    int search(int pos, const string& s) {
        if (s[pos] == '?') return m[s.size() - pos]; // 다음 노드에 대해 ?이면 단어 수 반환
        else if (children[s[pos]-'a'])
            return children[s[pos]-'a']->search(pos+1, s);
        return 0;
    }
};

vector<int> solution(vector<string> words, vector<string> queries) {
    TrieNode* prefixTrie = new TrieNode();
    TrieNode* suffixTrie = new TrieNode();
    for (auto& w : words) {
        prefixTrie->insert(0, w);
        reverse(w.begin(), w.end());
        suffixTrie->insert(0, w);
    }
    vector<int> answer;
    for (auto& q : queries) {
        if (q[0] == '?') { // 접두사에 와일드카드가 있으면 접미사 트라이에서 탐색
            reverse(q.begin(), q.end());
            answer.push_back(suffixTrie->search(0, q));
        } else { // 접미사에 와일드카드가 있으면 접두사 트라이에서 탐색
            answer.push_back(prefixTrie->search(0, q));
        }
    }
    return answer;
}

 

+ Recent posts