시간복잡도 대표 표현식 위일수록 빠르다. 빠른 순서 ↑ 상수 시간 O(1) 로그시간 O(log N) 직선형 시간 O(N) 2차 시간 O(n^2) 지수 시간 O(C^n) 느린 순서 ↓ LIST #ArrayList 시간복잡도 add : O(1) remove : O(n) get : O(1) Contains : O(n) iterator.remove : O(n) java 1.2에 추가, thread-safe 보장 안함 특징 : 데이터 추가,삭제를 위해 임시 배열을 생성해 데이터를 복사 - 대량의 자료를 추가/삭제시 복사가 일어 나게 되어 성능 저하를 일이킴 - 데이터의 인덱스를 가지고 있어 데이터 검색시 빠름 #LinkedList 시간복잡도 add : O(1) remove : O(1) get : O(n) Cont..
전체 글
https://www.acmicpc.net/problem/1302 1302번: 베스트셀러 첫째 줄에 오늘 하루 동안 팔린 책의 개수 N이 주어진다. 이 값은 1,000보다 작거나 같은 자연수이다. 둘째부터 N개의 줄에 책의 제목이 입력으로 들어온다. 책의 제목의 길이는 50보다 작거나 같고 www.acmicpc.net import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); BufferedWriter bw = new Buf..
가장 큰 차이는 삽입시의 순서가 지켜지느냐이다. HashMap의 경우 순서가 보장되지 않는다( 사전순도 아니다) 하지만 LinkedHashMap의 경우 넣은 순서대로 정렬이 된다. 반복문으로 키값을 출력시 알 수 있다. 성능의 차이는 있지만 크게 고려할 부분은 아닐 것이다. 공통점 데이터를 key-value 쌍으로 저장한다. 비동기로 처리된다. Key 중복을 허용하지 않는다. 하나의 null 값을 저장할 수 있다. Value 중복을 허용한다. 여러 개의 null 값을 저장할 수 있다. 차이점 HashMap 데이터의 삽입 순서를 보장하지 않는다. AbstractMap 클래스를 상속하고, Map 인터페이스를 구현한다. 연결리스트로 이루어진 배열로 구현됨 LinkedHashMap 데이터의 삽입 순서를 보장한다..
https://www.acmicpc.net/problem/7785 7785번: 회사에 있는 사람 첫째 줄에 로그에 기록된 출입 기록의 수 n이 주어진다. (2 ≤ n ≤ 106) 다음 n개의 줄에는 출입 기록이 순서대로 주어지며, 각 사람의 이름이 주어지고 "enter"나 "leave"가 주어진다. "enter"인 경우는 www.acmicpc.net import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); BufferedW..
접근 제한 적용 대상 접근할 수 없는 클래스 protected 필드, 생성자, 메소드 자식 클래스가 아닌 다른 패키지에 소속된 클래스(같은 패키지는 됨) default 클래스, 필드, 생성자, 메소드 다른 패키지에 소속된 클래스 private 필드, 생성자, 메소드 모든 외부 클래스
https://www.acmicpc.net/problem/10814 10814번: 나이순 정렬 온라인 저지에 가입한 사람들의 나이와 이름이 가입한 순서대로 주어진다. 이때, 회원들을 나이가 증가하는 순으로, 나이가 같으면 먼저 가입한 사람이 앞에 오는 순서로 정렬하는 프로그램을 www.acmicpc.net import java.io.*; import java.util.*; public class Main { public static class User{ protected String name; protected Integer age; public User(String name,Integer age){ this.name = name; this.age =age; } } public static void ma..
https://www.acmicpc.net/problem/1181 1181번: 단어 정렬 첫째 줄에 단어의 개수 N이 주어진다. (1 ≤ N ≤ 20,000) 둘째 줄부터 N개의 줄에 걸쳐 알파벳 소문자로 이루어진 단어가 한 줄에 하나씩 주어진다. 주어지는 문자열의 길이는 50을 넘지 않는다. www.acmicpc.net import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws IOException{ BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); BufferedWriter bw = new Bu..
원시타입과 Object 타입의 차이 웬만하면 Object타입쓰자 stable: 앞에서 나온 놈이 앞으로간다. Object타입이 최악이 NlogN이니깐 무조건 유리한거 아닌가 싶지만 평균적인 속도가 같은 NlogN이더라도 퀵소트가 보통의 상황에서 더 빠른 NlogN이다. 또한 추가적인 메모리를 쓰지 않아서 각각의 장단점이 있다. Arrays.sort()는 원시타입과 Object타입으로 나뉜다. Collections.sort()는 리스트를 정렬하며 원시타입 배영보다 성능이 더욱 좋다. Array.sort()는 기본적으로 오름차순이다. 내림차순으로 하려면 아래와 같이 하면 된다. 원시타입의 경우 함수자체에 내림차순 기능이 없다. 쉽게 생각하면 return 값이 양수이면 지금 순서 그대로, 음수이면 순서를 바꾼..