[프로그래머스] 뉴스 클러스터링 (Lv2)

date

Apr 11, 2023

slug

programmers-newsclustering

author

status

Public

category

🧩 Problem Solving

tags

프로그래머스

summary

합집합 교집합 원소 수 세기

type

Post

thumbnail

문제 링크

문제 분석 및 설계

아이디어

• 주어진 두개의 문자열의 다중집합을 HashMap으로 저장
• Key = 다중집합 문자열 ex) “FR”
• Value = 해당 문자열의 개수
• 예시) “FRENCEN” 문자열의 경우, ”FR” 1 ”RE” 1 ”EN” 2 ”NC” 1 ”CE” 1
• 전처리 1) 문자열 내의 모든 알파벳을 대문자로 변경
• “string”.toUpperCase()
• 전처리 2) 문자열 내에 알파벳이 아닌 문자가 있을 경우 해당 다중집합 문자열은 무시
• “string”.chatAt() 을 사용하여 ‘A’ ≤ c ≤ ‘Z’ 내부에 있는지 확인

• 교집합
• A: a b b c / a 1 b 2 c 1
• B: b c / b 1 c 1
• int = b 1
• 둘 중 하나의 HashMap을 순회하며
• 둘 다 있는 경우에 Math.min(value1,value2) 를 사용하여 둘 중 더 적은 개수로 카운트

• 합집합
• 합집합 원소 넣을 HashSet 생성
• 두개의 HashMap을 모두 순회하며, 하나라도 있는 키는 일단 넣음
• 모든 키를 입력한 HashSet를 모두 순회하며
• 문자열 1에만 있다면 문자열 1에서의 개수
• 문자열 2에만 있다면 문자열 2에서의 개수
• 둘 모두에 있다면 Math.max(문자열1 개수, 문자열2 개수)

• 소인수분해 최소공배수 최대공약수

시간복잡도

• 문자열길이 N

• HashMap 생성 O(N)

• 교집합 : HashMap 순회 O(N)

• 합집합 : HashSet 입력 O(2N) + HashSet 순회 O(N)

• 총 O(N)

자료구조

• HashMap set1, set2

• HashSet set

Point 1. 합집합 / 교집합 설계

• 교집합
• 둘 중 하나의 HashMap을 순회하며
• 둘 다 있는 경우에 Math.min(value1,value2) 를 사용하여 둘 중 더 적은 개수로 카운트

• 합집합
• 합집합 원소 넣을 HashSet 생성
• 두개의 HashMap을 모두 순회하며, 하나라도 있는 키는 일단 넣음
• 모든 키를 입력한 HashSet를 모두 순회하며
• 문자열 1에만 있다면 문자열 1에서의 개수
• 문자열 2에만 있다면 문자열 2에서의 개수
• 둘 모두에 있다면 Math.max(문자열1 개수, 문자열2 개수)

Point 2. Edge 케이스(?) 처리

• 유사도 = intersection / union
• 만약 union==0 이라면 DivisionByZero 에러 발생

• 문자열 내부 알파벳이 아닌 기호
• 전처리 1) 문자열 내의 모든 알파벳을 대문자로 변경
• “string”.toUpperCase()
• 전처리 2) 문자열 내에 알파벳이 아닌 문자가 있을 경우 해당 다중집합 문자열은 무시
• “string”.chatAt() 을 사용하여 ‘A’ ≤ ≤ ‘Z’ 내부에 있는지 확인

메모

• <Key, Value> 형태를 사용하고 싶으면 HashMap을 사용해야 함

• containsKey(Key) // 해당 키 값이 존재하는지 여부

• get(Key)

• put(Key, Value)

• 만약 i 인덱스로부터 2개 길이의 서브스트링 하고 싶다면

• substring(i, i+2)