.png&blockId=18f00b21-a9bc-4e35-aeb8-ecb07bddb89a)
레벨 1이지만 사악한 문제..(정답률 30퍼대)
배열로 풀기
이전에 풀었던 문제인데 사실 그때는 해시가 뭔지도 몰라서 그냥 배열로 풀었다.. 카카오 기출인만큼 1레벨인데도 어렵고 코드가 긴느낌,, (다른 분들 파이썬 코드보니 자바라 그런것 같기도;)
//해시 아닌것으로 풂
class User{
String username;
int index=0;
}
class Solution {
public int[] solution(String[] id_list, String[] report, int k) {
int [][] list=new int[id_list.length][id_list.length+1];
User[] user=new User[id_list.length];
for(int i=0;i<id_list.length;i++){ //...1) 1000회
user[i]=new User();
user[i].username=id_list[i];
}
for(int i=0;i<report.length;i++){ //...2) 20만회
String[] splited=report[i].split(" ");
for(int j=0;j<id_list.length;j++){ //...3) 1000회
int idx=0;
boolean bool=false;
//신고한 유저 이름 검색
if(user[j].username.equals(splited[0])){
idx=j;
bool=true;
//신고당한 유저 이름 검색
for(int p=0;p<id_list.length;p++){ //...4) 1000회
if(user[p].username.equals(splited[1])){
if(list[idx][p]==0){
//같은유저가 같은 유저를 신고한 경우가 아닐경우
list[idx][p]=1;
list[p][id_list.length]++;
}
break;
}
}
}
if(bool){
break;
}
}
}
int[] answer = new int[id_list.length];
for(int i=0;i<id_list.length;i++){ //...5) 1000회
if(list[i][id_list.length]>=k){
for(int j=0;j<id_list.length;j++){ //...6) 1000회
if(list[j][i]==1){
answer[j]++;
}
}
}
}
return answer;
}
}
Java
복사
지금 다시보니까 사실상 해시 맵을 배열로 구현한 느낌이다.
2차원 배열을 선언하고 각 행마다 id를 저장한 뒤 해당 행에 해당 id가 신고한 유저의 id를 넣는 방식.
시간복잡도 제한을 어떻게 통과했는지 모르겠다. (간당간당 했을것 같다)
1초에 1억번 연산(10^9)이 가능하다고 생각하고 설계해야한다.
위의 코드에서 id_list의 길이가 최대 1,000, report의 길이가 최대 200,000이다.
시간 복잡도: 10^3 + 2*10^5*10^3*10^3 + 10^3*10^3 =약 10^11
(10초 제한인데 어떻게 통과한걸까^^;;)
10초 제한인데 어떻게 통과한걸까^^;;)•
N의 제한에 따른 시간 복잡도를 고려한 알고리즘 설계
결국 이 문제는 해시를 이용해야 시간제한을 통과할 수 있는 문제다!
해시 맵은 get과 put 모두 시간복잡도가 단 O(1)이다.
해시로 풀기
import java.util.ArrayList;
import java.util.HashMap;
class Solution {
public static int[] solution(String[] id_list, String[] report, int k) {
HashMap<String, Integer> hm = new HashMap<>();
//"신고한사람 신고받은사람" , 있는지 없는지(null, 1)
HashMap<String ,Integer> hmCount = new HashMap<>();
// 신고 받은 사람, 신고받은 횟수(중복제외)
HashMap<String ,Integer> ans = new HashMap<>();
// 신고한 사람- 신고 메일 받은 횟수
for(int i=0;i<report.length;i++){ //...1) 10^5
//신고 저장
String[] splitted = report[i].split(" ");
if(hm.get(report[i])==null){
//한 유저가 특정 유저 최초 신고시에만 신고 저장
hm.put(report[i],1);
if(hmCount.get(splitted[1])==null){
hmCount.put(splitted[1],1);
continue;
}
hmCount.put(splitted[1],hmCount.get(splitted[1])+1);
}
}
for (String s : hmCount.keySet()) { //...2) 최대 10^3
if(hmCount.get(s)>=k){
//신고 당한 횟수가 k인 회원(s)을 찾기
for(int i=0;i<id_list.length;i++){ //...3) 10^3
//회원s를 신고한 회원 찾기
String keyString = id_list[i]+" "+s;
if(hm.get(keyString)!=null){
//회원 신고 메세지를 몇개 받는지를 저장
if(ans.get(id_list[i])==null){
ans.put(id_list[i],1);
} else{
ans.put(id_list[i],ans.get(id_list[i])+1);
}
}
}
}
}
//전체 회원의 받은 메일 개수를 저장하는 리스트
ArrayList<Integer> ansList = new ArrayList<>();
for(int i=0;i<id_list.length;i++){ //...4) 10^3
if(ans.get(id_list[i])!=null)
ansList.add(ans.get(id_list[i]));
else{
ansList.add(0);
}
}
//리스트를 다시 배열로 저장해서 리턴
int[] ansArr = new int[ansList.size()];
int size = 0;
for(Integer integer:ansList){ //...5) 10^3
ansArr[size++] = integer;
}
return ansArr;
}
}
Java
복사
