알고리즘 Kata

74.

답안 :

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

class Solution {
	/*
	 * 1. 유저 신고당한수 맵핑
	 * 2. 신고한 유저와 신고 당한 유저 문자열 분리
	 * 3. 해당유저가 동일유저신고인지? 신고로그 맵을 만들어서 해당유저가 신고한 유저 목록화 <이름,신고유저Set>
	 * 4. 동일신고가 아닐 경우 신고당한수 +1, 동일신고일시 무시
	 * 5. 자신이 신고한 유저가 정지당한 유저 Set에 존재시 메일발송횟수 증가
	 * 6. 전체 유저 메일발송횟수 리턴
	 */
	public int[] solution(String[] id_list, String[] report, int k) {
		Map<String, Integer> userMap = new HashMap<>();
		Map<String, HashSet<String>> reportUserMap = new HashMap<>();
		Set<String> blockedUsers = new HashSet<>();
		// 유저 맵핑
		for (String userId : id_list) {
			userMap.put(userId, 0);
		}
		for (int i = 0; i < report.length; i++) {
			// 신고자, 피신고자 분리
			String reportWord[] = report[i].split(" ");
			String reportingUser = reportWord[0];
			String reportedUser = reportWord[1];
			// 신고 했던 이력이 있는 유저
			if (reportUserMap.containsKey(reportingUser)) {
				if (reportUserMap.get(reportingUser).contains(reportedUser)) {
					continue;
				} else {
					userMap.put(reportedUser, userMap.get(reportedUser) + 1);
					reportUserMap.get(reportingUser).add(reportedUser);
					// 피신고자가 k횟수 이상 신고시 정지
					if (userMap.get(reportedUser) >= k) {
						blockedUsers.add(reportedUser);
					}
				}
			}
			// 신고한 적이 없는유저
			else {
				userMap.put(reportedUser, userMap.get(reportedUser) + 1);
				reportUserMap.put(reportingUser, new HashSet<String>());
				reportUserMap.get(reportingUser).add(reportedUser);
				// 피신고자가 k횟수 이상 신고시 정지
				if (userMap.get(reportedUser) >= k) {
					blockedUsers.add(reportedUser);
				}
			}
		}

		int[] answer = new int[id_list.length];
		// 신고유저 정지여부 확인 및 메일발송횟수 체크
		for (int i = 0; i < answer.length; i++) {
			Set<String> a;
			Set<String> b;
			if (reportUserMap.get(id_list[i]) != null) {

				if (reportUserMap.get(id_list[i]).size() <= blockedUsers.size()) {
					a = reportUserMap.get(id_list[i]);
					b = blockedUsers;
				} else {
					a = blockedUsers;
					b = reportUserMap.get(id_list[i]);
				}
				int count = 0;
				for (String e : a) {
					if (b.contains(e)) {
						count++;
					}
				}
				answer[i] = count;
			}
		}
		return answer;
	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Solution s = new Solution();
		String[] id_list = { "a", "b", "c", "d" };
		String[] report = { "a b", "a b", "c a", "d a", "a b", "c d", "a d", "b c", "b a", "d a" };
		int k = 2;
		s.solution(id_list, report, k);
	}
}

• 알고리즘 설명 :
  • id_list[] 을 통해 유저 ID 와 신고당한 횟수를 맵핑
  • 동일 신고 여부 및 정지여부 확인을 위해 reportUserMap<Stirng, HashSet<String>> , blockedUsers Set<Stirng> 선언
  • String.split() 메소드를 이용하여 신고자, 피신고자를 분리.
  • 해당 유저가 동일 대상을 신고하는 지 확인 하기 위하여 reportUserMap 의 매핑된 HashSet에서 피신고자 존재여부 확인
  • 미존재시 대상을 Set에 삽입하고 피신고자 정지기준 확인 및 정지
  • 신고자에게 피신고자 정지시 메일발송을 위해 신고자가 신고한 피신고자들이 정지유저 Set의 존재하는지 확인.
  • 정지유저가 있을경우 정지된 유저 만큼 리턴.

Set 교집합 알고리즘 참조 :
https://docs.likejazz.com/intersection-of-two-sets/

• 틀린 답안 :

import java.util.ArrayList;
import java.util.HashMap;
import java.util.Map;

class Solution {
	/*
	 * 1. 유저 신고횟수 맵핑 2. 신고한 유저와 신고 당한 유저 문자열 분리 3. 해당유저가 동일유저신고인지? 신고로그 맵을 만들어서
	 * 해당유저가 신고한 리스트 목록화 <이름,신고유저리스트> 4. 맵순회하며 k 회 이상 신고당한 유저 배열인덱스 추출 후 반환
	 */
	public int[] solution(String[] id_list, String[] report, int k) {
		Map<String, Integer> userMap = new HashMap<>();
		Map<String, ArrayList<String>> reportUserMap = new HashMap<>();
		Map<String, Boolean> blockedUsers = new HashMap<>();
		// 유저 맵핑
		for (String userId : id_list) {
			userMap.put(userId, 0);
		}
		for (int i = 0; i < report.length; i++) {
			// 신고자, 피신고자 분리
			String reportWord[] = report[i].split(" ");
			String reportingUser = reportWord[0];
			String reportedUser = reportWord[1];
			// 신고 했던 이력이 있는 유저
			if (reportUserMap.containsKey(reportingUser)) {
				ArrayList<String> tempList = reportUserMap.get(reportingUser);
				for (int j = 0; j < tempList.size(); j++) {
					if (tempList.get(j).equals(reportedUser)) {
						break;
					} else {
						userMap.put(reportedUser, userMap.get(reportedUser) + 1);
						reportUserMap.get(reportingUser).add(reportedUser);
						// 피신고자가 k횟수 이상 신고시 정지
						if (userMap.get(reportedUser) >= k) {
							blockedUsers.put(reportedUser, true);
						}
					}
				}
			}
			// 신고한 적이 없는유저
			else {
				userMap.put(reportedUser, userMap.get(reportedUser) + 1);
				reportUserMap.put(reportingUser, new ArrayList<String>());
				reportUserMap.get(reportingUser).add(reportedUser);
				// 피신고자가 k횟수 이상 신고시 정지
				if (userMap.get(reportedUser) >= k) {
					blockedUsers.put(reportedUser, true);
				}
			}
		}
		int[] answer = new int[id_list.length];
		// 신고유저 정지여부 확인 및 메일발송횟수 체크
		for (int i = 0; i < answer.length; i++) {
			// 신고한 유저리스트 받아옴
			ArrayList<String> tempList = reportUserMap.get(id_list[i]);
			// 신고한 유저가 존재할때
			if (tempList != null && !tempList.isEmpty()) {
				for (int j = 0; j < tempList.size(); j++) {
					if (blockedUsers.containsKey(tempList.get(j))) {
						answer[i] += 1;
					}
				}
			} else {
				answer[i] = 0;
			}
		}
		return answer;
	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Solution s = new Solution();
		String[] id_list = { "con", "ryan" };
		String[] report = { "ryan con", "ryan con", "ryan con", "ryan con" };
		int k = 2;
		s.solution(id_list, report, k);
	}
}

• Set이 아닌 ArrayList로 풀이하였기 때문에 반복문의 갯수가 증가.
• id의 길이의 경우 1000개 정도로 적지만 report가 200000개 의 크기를 가지기에 반복문 1개도 치명적임.
• Set을 통해 조회를 반복문없이 진행하도록 변경.

SQL Kata

84.

• 방문자 중 물품을 구매하지 않은 고객과 방문횟수를 출력

답안 :

select customer_id , count(*) as 'count_no_trans'
from Visits v
left join Transactions t
on v.visit_id = t.visit_id
where t.visit_id IS null
group by 1

• Left Join 을 통해 방문은 했지만 상품을 구매하지않은 고객 ID가 Null인 값을 확보, 이후 NULL 값인 컬럼들만 카운팅 및 출력

85.

• 전날 보다 기온이 올라간 경우 ID 를 출력

답안 :

select w1.id
from Weather w1
join Weather w2
on DATEDIFF(w1.recordDate,w2.recordDate)=1
where w1.temperature > w2.temperature

• Self Join을 활용하여 자신과 날짜가 1일 차이나는 컬럼중 온도가 올라간 경우만 출력