%20(1).png)
LeetCode - Tweet Counts Per Frequency
문제 설명
A social media company is trying to monitor activity on their site by analyzing the number of tweets that occur in select periods of time. These periods can be partitioned into smaller time chunks based on a certain frequency (every minute, hour, or day).
For example, the period [10, 10000] (in seconds) would be partitioned into the following time chunks with these frequencies:
Every minute (60-second chunks): [10,69], [70,129], [130,189], ..., [9970,10000]
Every hour (3600-second chunks): [10,3609], [3610,7209], [7210,10000]
Every day (86400-second chunks): [10,10000]
Notice that the last chunk may be shorter than the specified frequency's chunk size and will always end with the end time of the period (10000 in the above example).
Design and implement an API to help the company with their analysis.
Implement the TweetCounts class:
TweetCounts() Initializes the TweetCounts object.
void recordTweet(String tweetName, int time) Stores the tweetName at the recorded time (in seconds).
List<Integer> getTweetCountsPerFrequency(String freq, String tweetName, int startTime, int endTime) Returns a list of integers representing the number of tweets with tweetName in each time chunk for the given period of time [startTime, endTime] (in seconds) and frequency freq.
freq is one of "minute", "hour", or "day" representing a frequency of every minute, hour, or day respectively.입출력 예시
Example 1:
Input
["TweetCounts","recordTweet","recordTweet","recordTweet","getTweetCountsPerFrequency","getTweetCountsPerFrequency","recordTweet","getTweetCountsPerFrequency"][],["tweet3",0],["tweet3",60],["tweet3",10],["minute","tweet3",0,59],["minute","tweet3",0,60],["tweet3",120],["hour","tweet3",0,210]]
Output
[null,null,null,null,[2],[2,1],null,[4]]
Explanation
TweetCounts tweetCounts = new TweetCounts();
tweetCounts.recordTweet("tweet3", 0); // New tweet "tweet3" at time 0
tweetCounts.recordTweet("tweet3", 60); // New tweet "tweet3" at time 60
tweetCounts.recordTweet("tweet3", 10); // New tweet "tweet3" at time 10
tweetCounts.getTweetCountsPerFrequency("minute", "tweet3", 0, 59); // return [2]; chunk [0,59] had 2 tweets
tweetCounts.getTweetCountsPerFrequency("minute", "tweet3", 0, 60); // return [2,1]; chunk [0,59] had 2 tweets, chunk [60,60] had 1 tweet
tweetCounts.recordTweet("tweet3", 120); // New tweet "tweet3" at time 120
tweetCounts.getTweetCountsPerFrequency("hour", "tweet3", 0, 210); // return [4]; chunk [0,210] had 4 tweets
제약사항
0 <= time, startTime, endTime <= 109
0 <= endTime - startTime <= 104
There will be at most 104 calls in total to recordTweet and getTweetCountsPerFrequency.Solution#1
[전략]
1. tweetName별 time을 저장
- tweetName을 HashMap의 key로 사용하여 식별하고, 각 tweetName에 해당하는 time들을 ArrayList로 관리
- 저장시 정렬하게 하여, frequency 계산 처리시 순차탐색 한번만 하도록 함
- frequency 계산 함수가 호출되면,
1) HashMap에서 tweetName으로 발생한 time들을 읽어와서
2) startTime - endTime 사이 발생 가능한 구간별로,
3) 구간에 속하는 time이 있는지를 카운트 하여 반환 arrayList에 추가
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
class TweetCounts {
private HashMap<String, List<Integer>> tweetRecordsHash;
public TweetCounts() {
tweetRecordsHash = new HashMap<String, List<Integer>>();
}
public void recordTweet(String tweetName, int time) {
List<Integer> tweets = tweetRecordsHash.get(tweetName);
if (tweets == null) {
tweets = new ArrayList<Integer>();
}
tweets.add(time);
Collections.sort(tweets);
tweetRecordsHash.put(tweetName, tweets);
}
public List<Integer> getTweetCountsPerFrequency(String freq, String tweetName, int startTime, int endTime) {
List<Integer> tweets = tweetRecordsHash.get(tweetName);
List<Integer> recordCountPerPeriod = new ArrayList<Integer>();
int freqToTime = freqToTime(freq);
int periodStartTime = startTime;
int periodEndTime = periodStartTime + freqToTime;
int i = 0;
while (periodStartTime <= endTime) {
if (periodEndTime > endTime) {
periodEndTime = endTime;
}
int periodCount = 0;
while (i < tweets.size()) {
int tweetTime = tweets.get(i);
if (tweetTime < periodStartTime) {
i++;
continue;
}
if (tweetTime > periodEndTime) {
break;
}
periodCount++;
i++;
}
recordCountPerPeriod.add(periodCount);
periodStartTime = periodEndTime + 1;
periodEndTime = periodStartTime + freqToTime;
}
return recordCountPerPeriod;
}
private int freqToTime(String freq) {
if (freq.equals("minute")) {
return 59;
} else if (freq.equals("hour")) {
return 3599;
} else if (freq.equals("day")) {
return 86399;
} else {
// System.out.println("illegal freq parameter");
return -1;
}
}
}Solution#2
[전략]
1. tweetName별 time을 저장
- tweetName을 HashMap의 key로 사용하여 식별하고, 각 tweetName에 해당하는 time들을 ArrayList로 관리
- 저장시 정렬하게 하여, frequency 계산 처리시 순차탐색 한번만 하도록 함
- frequency 계산 함수가 호출되면,
1) HashMap에서 tweetName으로 발생한 time들을 읽어와서
2) startTime - endTime 사이 발생 가능한 구간별로,
3) 구간에 속하는 time이 있는지를 카운트 하여 반환 arrayList에 추가
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.TreeMap;
class TweetCounts {
private HashMap<String, TreeMap<Integer,Integer>> tweetRecordsHash;
public TweetCounts() {
tweetRecordsHash = new HashMap<String, TreeMap<Integer, Integer>>();
}
public void recordTweet(String tweetName, int time) {
TreeMap<Integer, Integer> tweets = tweetRecordsHash.get(tweetName); // 오래걸리는 부분
if (tweets == null) {
tweets = new TreeMap<Integer, Integer>();
tweets.put(time,1);
tweetRecordsHash.put(tweetName, tweets);
}
else {
tweets.put(time, tweets.getOrDefault(time, 0) + 1);
}
}
public List<Integer> getTweetCountsPerFrequency(String freq, String tweetName, int startTime, int endTime) {
TreeMap<Integer, Integer> tweets = tweetRecordsHash.get(tweetName);
int[] tweetsArr = tweets.keySet().stream().mapToInt(Integer::intValue).toArray(); // 오래걸리는 부분
List<Integer> recordCountPerPeriod = new ArrayList<Integer>();
int freqToTime = freqToTime(freq);
int periodStartTime = startTime;
int periodEndTime = periodStartTime + freqToTime;
int i = 0;
while (periodStartTime <= endTime) {
if (periodEndTime > endTime) {
periodEndTime = endTime;
}
int periodCount = 0;
while (i < tweetsArr.length) {
int tweetTime = tweetsArr[i];
if (tweetTime < periodStartTime) {
i++;
continue;
}
if (tweetTime > periodEndTime) {
break;
}
periodCount = periodCount + tweets.get(tweetTime);
i++;
}
recordCountPerPeriod.add(periodCount);
periodStartTime = periodEndTime + 1;
periodEndTime = periodStartTime + freqToTime;
}
return recordCountPerPeriod;
}
private int freqToTime(String freq) {
if (freq.equals("minute")) {
return 59;
} else if (freq.equals("hour")) {
return 3599;
} else if (freq.equals("day")) {
return 86399;
} else {
// System.out.println("illegal freq parameter");
return -1;
}
}
}풀이 과정
첫번째 방법으로 풀고나니 TC가 좋지 않았다.
다른사람들이 푼 것을 참고해보니 TreeSet, TreeMap를 사용한게 보였다.
TreeSet, TreeMap 사용 이유를 분석해보니 TreeSet, TreeMap이 element 삽입시 정렬이 되고 내부적으로 BST 자료구조인것을 알게되었다.
recordTweet이 호출될 때마다 ArrayList의 정렬이 O(NlogN)의 시간 비용이 소요되는데, TreeSet 혹은 TreeMap을 사용한다면 BST 삽입시 정렬 비용인 O(logN) 으로 줄일수 있을거라 기대하였다.
key를 관리할필요없이 time만 저장하면 된다고 생각하였기에 우선 ArrayList TreeSet로 변경하였다.
실행해보니 실패하는 케이스가 발생한다.
input parameter를 보니 동일 tweetName에 time이 중복으로 발생 가능하다.
Set 자료구조의 특성상 중복은 허용되지 않기 때문에 동일 time건에 경우 한건으로만 카운트가 되는 문제였다.
TreeMap<Integer,Integer> 로 자료구조를 변경하였다.
속도 향상을 기대하였지만 오히려 첫번째 방법보다 속도가 저하 되었다.
배열 정렬 시간비용을 아꼈음에도 다른 곳에서 trade-off가 발생한 것 같다.
어떤 작업이 특히 오래걸렸는지 알아보기 위해 system.currenttimemillis 를 이용하여 매 작업별 시간을 출력해 보았다. 1)해쉬맵에서 TreeMap을 가져올때, 2)TreeMap의 key-set을 int형 배열로 변환시킬때 다른 구간에 비해 큰 시간 소요를 알수있었다.
속도 향상을 위해서는 두가지 부분에서 고민이 더 필요하다.
공간복잡도 측면에서도 첫번째 방법보다 안좋은 결과를 보였다.
원인은 1) ArrayList -> TreeMap 2) TreeMap의 key-set을 int형 배열로 변환
일것으로 예상된다.
TreeMap을 사용한 방법에서 다른요인으로 속도저하가 있어서 오히려 ArrayList를 사용할때보다 성능이 안좋게 나오긴 했지만, input 사이즈가 커질수록(N이 커져 정렬대상이 많아질수록) 다른요인의 영향이 있더라도 정렬에서 비용이 N배만큼 차이가 날 것이란게 예상된다.
하지만 여전히 공간복잡도에 대한 trade-off는 남아있을 것이기 때문에 실무에서 적용할때는 input의 사이즈, 시스템 메모리 환경 등을 고려하여 해당 경우에 맞는 적절한 방법을 선택하는 것이 좋다 생각된다.
