본문 바로가기

Java/알고리즘

 (51)
[자바 알고리즘 인터뷰] ch 11. 해시 테이블 (3) 중복 문자 없는 가장 긴 부분 문자열 https://leetcode.com/problems/longest-substring-without-repeating-characters/description/  - 중복 문자가 없는 가장 긴 부분 문자열(Substirng)의 길이를 리턴하라   풀이 1) 슬라이딩 윈도우와 투 포인터로 크기 조절  - 슬라이딩 윈도우로 한 칸씩 우측으로 이동하면서 윈도우 내에 모든 문자가 중복이 없도록 투 포인터로 윈도우 크기를 조절하면서 풀이해보면 다음과 같다.  - 슬라이딩 윈도우의 각 단계별로 중복 문자가 없는 윈도우의 최대 길이를 순서대로 표시했다.    - 먼저 투 포인터로 문제를 풀이하되, 포인터 2개 모두 왼쪽에서 출발한다. - 각각 왼쪽 시작점에서 출발해 두 번째 포인터(right변수)는 다음과 같이 현재..
[자바 알고리즘 인터뷰] ch 11. 해시 테이블 (2) 보석과 돌 https://leetcode.com/problems/jewels-and-stones/description/  - J는 보석이며, S는 갖고 있는 돌이다. S에는 보석이 몇개나 있을까? 대소문자는 구분한다.   풀이 1) 해시 테이블을 이용한 풀이  - 갖고 있는 돌 stones의 엘리먼트 각각의 개수를 모두 헤아린 다음, jewels의 각 엘리먼트를 키로 하는 각각의 개수를 합산- 먼저 freqs라는 해시 맵을 선언Map freqs = new HashMap(); - 돌의 모음인 stones를 문자 단위로 하나씩 분리해 반복한다. 만약 처음 등장한 문자라면 1을 선언하고, 기존에 있던 문자라면 1을 더한다. //돌(S)의 빈도수 계산for(char s : stones.toCharArray()){ /..
[자바 알고리즘 인터뷰] 11장 해시 테이블 (1) 해시맵 디자인 https://leetcode.com/problems/design-hashmap/description/ - 다음과 같은 기능을 제공하는 해시맵을 디자인하라. put(key, value) : 키, 값을 해시맵에 삽입한다. 만약 이미 존재하는 키라면 업데이트한다. get(key)  : 키에 해당하는 값을 조회한다. 만약 키가 존재하지 않는다면 -1을 업데이트한다. remove(key) : 키에 해당하는 키, 값을 해시맵에서 삭제한다.   풀이 1) 개별 체이닝 방식을 이용한 해시 테이블 구현    - 키, 값을 보관하고 연결 리스트로 처리할 별도의 객체를 구현 //노드 클래스 static class Node { int key,val; Node next; Node(int key, int val..
[자바 알고리즘 인터뷰] ch 10. 데크, 우선순위 큐 (4) - 더 맵게 https://school.programmers.co.kr/learn/courses/30/lessons/42626 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr     풀이 1) 우선순위 큐  - '가장 맵지 않은 음식의 스코빌 지수 + (두 번째로 맵지 않은 음식의 스코빌 지수*2)'로 나온 새로운 음식을 다시 추가하고 반복하면서, 스코빌 지수가 K 이상일 때 반복 횟수를 출력하는 것이다.  - 가장 맵지 않은 음식을 계속해서 추출해야 한다는 점에서 우선순위큐를 활용 import java.util.*;class Solution { public int ..
[자바 알고리즘 인터뷰] ch 10. 데크, 우선순위 큐 (3) - 원점에서 가장 가까운 k개의 점 https://leetcode.com/problems/k-closest-points-to-origin/description/  - 평면상에 points 목록이 있을 때, 원점(0,0)에서 가장 가까운 k개의 점 목록을 순서대로 출력하라. 평면상에 있는 두 점의 거리는 유클리드 거리(Euclidean Distance)로 한다.   풀이 1) 유클리드 거리의 우선순위 큐 순서  - 유클리드 거리는 두 점의 직선 거리를 의미한다. - 유클리드 거리를 계산하고 이 값을 우선순위 큐로 k번 출력하면 쉽게 문제를 풀 수 있다.    - 위의 유클리드 거리를 계산하고 이 값을 우선순위 큐에 삽입하는 코드는 다음과 같다. //Point 클래스를 저장하는 우선순위 큐로, 정렬 기준은 distance로 한다. Priori..
[자바 알고리즘 인터뷰] 10장 데크, 우선순위 큐 (2) k개 정렬 리스트 병합 https://leetcode.com/problems/merge-k-sorted-lists/zm - k개의 정렬된 리스트를 1개의 정렬된 리스트로 병합하라   풀이 1) 우선순위 큐를 이용한 리스트 병합  우선순위 큐  - 어떠한 특정 조건에 따라 우선순위가 가장 높은 엘리먼트가 먼저 추출되는 자료형 - 이 문제의 예제 입력값은 [[1,4,5],[1,3,4],[2,7]] 이며, 먼저 다음과 같이 반복문으로 각 연결 리스트의 첫 번째 노드를 큐에 저장한다. //각 연결 리스트의 첫 번째 노드를 큐에 저장for(ListNode node : lists){ if(node!=null) pq.add(node);} - 이렇게 하면 큐에는 각 연결 리스트의 루트인 1,1,2가 저장된다. - 그렇다면 ..
[자바 알고리즘 인터뷰] 10장 데크, 우선순위 큐 (1) 원형 데크 디자인 데크- Double-Ended-Queue의 줄임말로, 글자 그대로 양쪽 끝을 모두 추출할 수 있는, 큐를 일반화한 형태의 추상 자료형(ADT)이다. - 양쪽에서 삽입과 삭제를 모두 처리할 수 있으며, 스택과 큐의 특징을 모두 갖고 있다. - 이중 연결 리스트(Doubly Linked List)로 구현   - 양쪽으로 head와 tail이라는 이름의 두 포인터를 갖고 있다가 새로운 아이템이 추가될 때마다 앞쪽 또는 뒤쪽으로 연결해주기만 하면 된다.  - 자바에서 데크를 구현하는 Deque 자료형은 Queue와 마찬가지로 인터페이스이며, Queue를 확장해 정의되어 있다 ,- 실제 구현은 LinkedList 또는 ArrayDeque로 할 수 있다.  //데크 선언Deque deque = new LinkedL..
[자바 알고리즘 인터뷰] 9장 스택,큐 (6) 원형 큐 디자인 https://leetcode.com/problems/design-circular-queue/description/    - 원형 큐를 디자인하라, 큐가 비어 있다면 -1을 리턴하며, 해당 원형 큐의 사용 예는 다음과 같다.   풀이 1) 배열을 이용한 풀이  - 원형큐(Circular Queue)는 FIFO 구조를 지닌다는 점에서 기존 큐와 동일하다. - 그러나 마지막 위치가 시작 위치와 연결되는 원형 구조를 띠기 때문에, 링 버퍼(Ring Buffer)라고 부른다.   - 기존의 큐는 공간이 꽉 차면 더 이상 엘리먼트를 추가할 수 없다. - 심지어 앞쪽에 엘리먼트들이 deQueue()로 모두 빠져서 충분한 공간이 남게 돼도 그 쪽으로는 추가할 수 있는 방법이 없다.  - 그러나 원형 큐는 앞쪽에 공간..

티스토리툴바