TIL 2022-06-21

알고리즘

https://dvjgdiary.tistory.com/20 (프로그래머스Lv1 - 신고결과받기)

배운점:

1. HashMap, HashSet 활용

String	<HashSet> (중복X)
A	[C, D, E]
B	[C, A, D]
C	[A, B]
D	[E]
E	[A, B]

다음과 같은 (Key, Value)형태로 데이터를 저장하고싶을 땐 HashMap + HashSet 사용

HashMap<String , HashSet<String>> map = ~~~

 

Entry에 HashSet이 포함되어있으므로 초기화시 HashSet을 생성해줘야 한다.

for (int i=0; i<map.size(); i++) {
	map.put(id_list[i], new HashSet<>);
}

 

 

HashMap의 value에 값추가

HashMap.get(Key)는 해당 Key에 대한 Value값을 리턴한다. 위의 경우 HashSet<>을 리턴받으므로 HashSet의 Operation을 사용할 수 있다. 따라서, HashSet의 add( )메소드를 사용하여 값을 추가하면 된다.

for (int i=0; i<map.size(); i++) {
	map.get(id_list[i]).add("하이");
}

 

 

 

2. 2중for문 --> 1중for문으로 단축

reporter	reported
A	[C, D, E]
B	[C, A, D]
C	[A, B]
D	[E]
E	[A, B]

reported 의 각 ID가 몇개있는지 Count하고싶다고 해보자.

위와같은 [reporter, reported] 구조에선 Count하기 위해 전체 for문을 돌며 각 reported의 for문을 돌아서 확인해야할 것이다. -> O(N^2)

 

reported	reporter
A	[B, C, E]
B	[C, E]
C	[A, B]
D	[A, B]
E	[A, D]

하지만, [reported, reporter] 구조로 자료를 저장하면 전체 for문을 돌며 각 reporter의 길이만 확인하면 된다. --> O(N)

 

소소하지만 발상의 전환연습

 

---

https://dvjgdiary.tistory.com/21 (프로그래머스Lv1 - 두 개 뽑아서 더하기)

배운점:

1. dfs, 구현방식의 조합구하기

2. 중복X는 HashSet사용

3. HashSet은 Unordered Collection으로서 정렬이 안되므로 linkedList(Collection c) 생성자로 List를 만들고 Collections.sort( List l ) 메소드로 정렬