문제 출처 https://school.programmers.co.kr/learn/courses/30/lessons/42627 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 문제 풀이습관처럼 우선 순위 큐에 다 넣고, 정렬을 했었는데 경쟁을 할 때 다음 노드들의 값을 갱신 어떻게 해야 할지에서 막혀서 많은 시간 낭비를 하였다 (습관과 사고를 고쳐야 하는데 .. ) 예제 입력 jobs : [[0, 3], [1, 9], [2, 6]]result : 9 단순히 작업 시간 순으로 정렬한다고 해서 결과값을 구할 수 없었다10ms(= (3 + 11 + 16) / 3)  ..

문제 출처 https://school.programmers.co.kr/learn/courses/30/lessons/42626 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 문제 풀이모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 스코빌 지수 가장 적은 두 가지 음식을 섞어 새로운 음식을 만든다 섞은 음식의 스코빌 지수 = 가장 맵지 않은 음식의 스코빌 지수 + (두 번째로 맵지 않은 음식의 스코빌 지수 * 2) - K 이상 음식을 만들 수 있는 최소 턴 수 (만약 모두 섞었는데 못 구하는 경우 -1 리턴) - 우선 순위 큐, PriorityQueue 사용..

문제 출처https://school.programmers.co.kr/learn/courses/30/lessons/42584 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr  문제 풀이초 단위로 기록된 주식 가격이 담긴 배열 prices가 주어질때 가격이 떨어지지 않는 기간은 몇초인지 return- 제한 사항 int[] prices의 길이는 2 이상 100,000 이하 - O(n^2)으로 풀이시 O(10^10) 발생 가능- 스택을 사용하여 O(N) 풀이, 인덱스 번호를 스택에 넣는다는 아이디어를 생각하지 못했다. prices : [1, 2, 3, 2, 3]ret..

문제 링크 https://www.acmicpc.net/problem/21942 문제 풀이직접 풀이 못함, 월별 일수 계산하는 방법 알게 되어 기록 - 문자열로 된 날짜 데이터 변환이 어려운 문제였다.- 구현 로직은 Map 자료구조를 사용하여 상대적으로 간단했다- 시간복잡도: O(N)  (Map 자료구조를 사용해서 O(1)에 추가/삭제 가능)  [핵심 로직]- Map에 닉네임과 부품(key) 정보가 없는 경우 대여 이므로 HashMap 에 데이터 추가 한다- Map에 닉네임과 부품(key) 정보가 있는 경우 반납 이므로 HashMap 제거 후 패널티 계산 수행한다- 벌금의 경우에도 Map 자료구조 사용하여 {key: 닉네임, value: 벌금} 형태로 기록한다  실수 1. 최대치 long- 문제에서 yyy..

TreeSet ? - Java Collection Framework 제공하는 자료구조- 이진 탐색 트리(binary search tree)로 구현 - 시간복잡도 : O(logN)  (HashSet의 경우 O(1))- 범위 탐색과 정렬에 유리 - Collection, Set 에서 제공하는 기본 메소드 또한 사용 가능- 중복 허용 X- null 허용 X (NPE 발생)- 정렬 기준의 경우 객체의 Comparable이나 TreeSet 생성자에 Comparator 초기화하여 사용- thread-safe 하지 않다 생성자- 내부적으로 Map 자료 구조를 사용하고, 아래와 같이 생성자를 제공한다 - 인자가 없는 기본 생성자를 사용할 경우 TreeMap으로 생성된다private transient NavigableMa..

우선 순위 큐 (Priority Queue)최소 혹은 최대값을 효율적으로 찾을 수 있는 자료 구조 - 시간 복잡도 :  O( log₂N) - 힙(완전 이진 트리) 자료 구조 기반 구현  - (사전에 정렬할 필요 없이) 데이터 삽입/삭제 시 우선 순위에 따라 빠르게 접근/삭제 가능하다① 최소 힙 : 부모 노드 ≤ 자식 노드 ② 최대 힙 : 부모 노드 ≥ 자식 노드 참고. 부모-자식 인덱스 구하는 공식루트가 0번 인덱스부터인 경우① 부모 노드 = (현재 노드 - 1) / 2② 왼쪽 자식 노드 = (부모 노드 * 2) + 1③ 오른쪽 자식 노드 = 왼쪽 노드 + 1   구현해보기java.util.PriorityQueue 에서 간단하게 필요한 부분만 추출하였다public class MyPriorityQueue ..

ArrayDeque 클래스 특징① 자바 1.6 추가② 내부적으로 가변길이 배열(Resizable-array)로 데이터 관리, 용량 제한 없음③ Thread-safe 하지 않음④ Null element 금지⑤ Stack 으로 사용할시 Stack 클래스 빠르고, Queue로 사용할 시 LinkedList 클래스보다 빠르다This class is likely to be faster than Stack when used as a stack, and faster than LinkedList when used as a queue.  ArrayDeque를 Queue로 활용하는 경우 아래의 네가지 장점을 생각해 볼 수 있다① 더 높은 성능 지원 - 내부적으로 배열을 사용하여 큐를 구현하기 때문에 빠른 접근 시간을 제공..

ArrayDeque 클래스 특징① 자바 1.6 추가② 내부적으로 가변길이 배열(Resizable-array)로 데이터 관리, 용량 제한 없음③ Thread-safe 하지 않음④ Null element 금지⑤ Stack 으로 사용할시 Stack 클래스보다 빠르고, Queue로 사용할 시 LinkedList 클래스보다 빠르다This class is likely to be faster than Stack when used as a stack, and faster than LinkedList when used as a queue. - 공식 doc  참고. Stack 클래스 단점자바 1.0에 추가되었고, Vector 클래스를 상속받고 있다 -- LIFO (Last In First Out) - 멀티 스레드 환경에서..

문제 링크 https://www.acmicpc.net/problem/22252 22252번: 정보 상인 호석 암흑가의 권력은 주먹과 정보에서 나온다. 주먹은 한 명에게 강하고, 정보는 세계를 가지고 놀 수 있기 때문에 호석이는 세상 모든 정보를 모으는 "정보 상인"이 되고 싶다. 정보 상인은 정보를 www.acmicpc.net 문제 풀이 - 해쉬맵, 우선순위 큐 사용하여 풀이 - 결과 최대치 long 최대치 생각해보기 - 쿼리 10만개가 주어지고, 고릴라가 10만 가치의 정보를 10만개씩 가지고 있고, 구매자가 10만개씩 구매한다면 .. 쿼리가 10만개 있을 때 5만개씩 상점에 정보 추가하고, 5만개씩 상점에서 구매자가 구매한다면 = 50,000 * 10^5 * 10^5 (int 범위 초과) - 고릴라 ..

문제 링크 https://www.acmicpc.net/problem/21276 21276번: 계보 복원가 호석 석호촌에는 N 명의 사람이 살고 있다. 굉장히 활발한 성격인 석호촌 사람들은 옆 집 상도 아버님, 뒷집 하은 할머님 , 강 건너 유리 어머님 등 모두가 한 가족처럼 살아가고 있다. 그러던 어느 날 www.acmicpc.net 문제 풀이 - 한달 지난 후 두번째 풀이 - 배열/정렬/해시맵/인접행렬과 같은 자료 구조를 활용하는 문제였다 예제 입력 7 -- 사람 수 daeil sangdo yuri hoseok minji doha haeun 7 -- 정보의 개수 hoseok sangdo -- X 의 조상은 Y이다 yuri minji hoseok daeil daeil sangdo haeun doha do..

문제 링크 https://www.acmicpc.net/problem/10799 10799번: 쇠막대기 여러 개의 쇠막대기를 레이저로 절단하려고 한다. 효율적인 작업을 위해서 쇠막대기를 아래에서 위로 겹쳐 놓고, 레이저를 위에서 수직으로 발사하여 쇠막대기들을 자른다. 쇠막대기와 레이저 www.acmicpc.net 문제 풀이 - 스택 자료 구조 응용 문제 - 시간 복잡도 : O(N) 절차 1) 스택 선언하고 "(" 인 경우 스택에 추가한다. 2) ")"는 괄호일 때 2-1) 이전 괄호가 "(" 인 경우 레이저가 되므로, pop() 후 stack.size() 를 결과에 합산한다. 2-2) 레이저가 아닌 경우(=쇠막대 하나가 끝나는 위치) pop() 후 +1 을 결과에 합산한다. 예제입력 2 (((()(()()..

HashMap - 내부적으로 hash 값을 인덱스로 하여 자료 구조 관리 - Key 중복 x , Value 중복 허용 - hash 값의 중복이 발생하는 경우 LinkedList, Tree 자료 구조 사용하여 해결하고 있음  Method 살펴보기put()- key 로 만든 hash 값에 해당하는 bucket이 없는 경우 신규 Node 저장, 있는 경우 value를 덮어씌움- 동일한 hash 값이 있는 경우 ThreadHold 값에 따라 LinkedList, Tree 로 자료 연결되어 관리 참고. HashMap put() 살펴보기  예시테스트 파일에서 공통으로 사용할 Map의 데이터를 초기화public class HashMapTest { Map map = new HashMap(); @BeforeE..

Set ? - 집합을 다루는 자료구조- 중복 x, 순서 x- 대표적인 구현체 : HashSet / TreeSet / LinkedHashSet / EnumSet- 내부적으로 Map 자료 구조에 Key에 데이터를 담는다 (Map은 Key의 중복 허용하지 않음)//java.util.HashSet.classprivate transient HashMap map;private static final Object PRESENT = new Object();public HashSet() { this.map = new HashMap();}//..public boolean add(E e) { return this.map.put(e, PRESENT) == null; // HashMap의 Key에 element를 담..

Array (배열)- 동일한 자료형(Data Type)의 데이터를 연속된 공간에 저장하기 위한 자료 구조- 기본형(Primitive Types) 또는 인스턴스(Reference Type)을 저장하기 위해 배열 사용- 처음 선언시 길이를 지정하기 때문에 런타임 환경에서 크기를 변경할 수 없다 (정적 할당, static allocation) Array 선언 및 초기화 예시# 1int[] arr = new int[10];arr[1] = 1; // .. 이하 생략# 2int[] arr = new int[] {1, 2, 3, 4};# 3 int[][] arr = {{1, 0}, {0, 1}, {-1, 0}, {-1, 0}}; 장점구조가 간단하고, 인덱스로 해당 element에 접근할 경우 시간 복잡도 O(1) 소..