String 함수들, 자료구조 - Java

String 함수들

잘 쓰면 코드작성시간을 줄여준다.

 

• charAt(i) : 특정 문자열의 위치
• toCharArray() => char[]
• substring(begin, end) 주의! end는 포함되지 않음
• compareTo(String anotherString) : 사전순서대로 비교해준다.
• Character.isDigit(c), Character.isLetter(c): 숫자? 문자?

---

 

 

 

문제에 적합한 자료구조 선택하기

크게 List, Set, Map 세가지이다. 

1. List

일반적인 데이터 모음에 사용

size가 정해지지 않은 동적배열이 필요할때 사용

그렇지 않은경우 Array 사용

 

ArrayList

중간 index 접근이 필요한경우.

ArrayList는 내부적으로 배열을 유지하면서 관리된다.

ArrayList의 경우 중간 삽입/삭제/캐파시티 이상의 element가 추가될 때 내부적으로 복사가 일어나기 때문에

이런 경우가 빈번하다면 LinkedList가 유리할 수 있다.

단, memory locality가 좋아서 일반적으로 LinkedList에 비해 성능이 좋다.

sort(Comparator<? super E> c)

LinkedList

중간 index 접근 없이 맨 앞이나 뒤에 넣고 빼기만 하는경우 ArrayList보다 더 빠르다.

만약 LinkedList에서 하나의 element를 찾아야 하는 경우 처음->끝까지 전부 돌면서 찾아야 하기 때문에 복잡도가 O(n) 이 된다.또한 node들이 여기저기 메모리의 공간에 산재해 있기 때문에 더 오래걸린다.

addFirst(E e)	앞에다가 넣을 수 있음
addLast(E e)	걍 add쓰면 addLast랑 같음
contains(Object o)	존재확인
remove(Object o)	index없이 value로 삭제

 

2. Map

Key, Value로 값을 저장했다가 검색해야할때 사용

key 값 중복안됨

 

HashMap

key값을 가지고 value를 빠르게 찾을수 있다. get과 put시 consistant time 퍼포먼스를 낸다.

 

이렇게 하기 위해서 너무 큰 capacity를 만들지 않아야 한다.

생성시 두가지 파라미터가 있는데, capacity(용량) 과 load factor가 있다. 

load factor은 hashtable이 얼마만큼 꽉 찼을 때 저절로 capacity를 늘릴지이다.

예를 들어,  load factor가 0.75라 하면 hash table이 75%이상 찼을 때 rehash 하며 capacity를 2배로 늘린다.

 

만약 load factor가 너무 크면 스페이스 오버헤드를 줄일수 있지만(rehash 지연), lookup cost가 늘어난다. 

rehash동작을 줄이기 위해서 만일 capacity를 예상할 수 있다면 initial size를 넣어주면 효과적이다.

 

entry에 대한 set을 갖고있다.

containsValue(Object value)	value가 있는지를 찾는다
containsKey(Object key)	key가 있는지를 찾는다
getOrDefault(Object key, V defaultValue)	key값을 가져오고, 없으면 default value를 가져온다. (짱)
keySet()	key들을 전부 가져와서 map 전체를 foreach돌릴때 사용함.

 

TreeMap

Red-black tree로 넣으면서 정렬함. key 순서대로 정렬함 (value 정렬은 노)

넣을때는 오래걸리지만 - 검색이 빠르다

 

LinkedHashMap

넣은 순서를 갖고있는 hashMap

 

3. Set 

중복X, 순서가 없다.

 

HashSet

일반적으로 많이 사용하는 Set이다. 내부적으로 HashMap을 갖고있다.

정렬이 필요없다면 HashSet

 

TreeSet

내부적으로 TreeMap(TreeMap은 Red Black Tree)으로 구현되어있다.

검색이 빠르다. 정렬이 이미 되어있다.

 

LinkedHashSet

넣은 순서를 갖고있는 hashSet. 모든 entry에 대해서 double linked list를 갖고있다.

만약 이미 있는 애를 한번 더 넣는다면? 순서가 변경되지 않는다. (최초의 순서 유지) contains 확인하고 return해버리기 때문

 

4. Stack

후입선출의 알고리즘이 필요한경우 사용 

Vector<>를 extends해서 구현되어있다. (Vector는 크기가 늘어날 수 있는 object들의 array)

 

5. Queue

java에서 Queue는 interface로 그 자체로 instance화 할 수 는 없고, 자식클래스인 AbstractQueue를 extends한 자료구조로는

PriorityQueue가 있다.

Priority queue는 priority heap 베이스로 구현되어있다. Comparator활용해서 넣으면서 순서 정렬할때 사용. 

넣으면서 정렬되기 때문에, 넣을 때 시간이 많이 걸리지만, 중간중간 정렬이 필요한경우 사용

peek()	꺼내지 않고 맨 위에꺼만 알고싶은경우
poll()	맨 위에것을 꺼낸다. (queue에서 삭제됨)

 

6. Arrays

가끔 인풋으로 ArrayList가 아닌 array가 들어오는 경우에 유용하게 쓸 수있는 API들이 있다.

Arrays.XXX(array객체) 로 사용한다. 아래 표에는 Object[] argument API만 썼지만, (int, long 등등) 에 대해서 다 존재

asList(T... a)	List로 변환
binarySearch(Object[] a, Object key)	key를 binary search해줌
fill(Object[] a, Object val)	array자체를 val값으로 다 채워줌
sort(Object[] a)	정렬. Comparator 직접 넣는 API도있음
toString(Object[] a)	붙여서 문자열로 만들어줌

 

https://docs.oracle.com/javase/8/docs/api/allclasses-noframe.html