본문 바로가기

전체 글159

[Java/프로그래머스/해시] Level 3: 베스트앨범 문제 programmers.co.kr/learn/courses/30/lessons/42579 코딩테스트 연습 - 베스트앨범 스트리밍 사이트에서 장르 별로 가장 많이 재생된 노래를 두 개씩 모아 베스트 앨범을 출시하려 합니다. 노래는 고유 번호로 구분하며, 노래를 수록하는 기준은 다음과 같습니다. 속한 노래가 programmers.co.kr 코드 롸... 진짜 너무 어렵잖응ㅁ..ㅠㅠㅠㅠㅠㅠ 어떤 자료구조를 쓸 지 고르는 것이 정말 어려웠다. (근데 이게 핵심임) 순서는 다음과 같다. 1. id(고유번호), play(재생횟수), genre를 담은 Song 객체를 만든다. Song 객체는 ArrayList에 삽입한다. 동시에 각 장르별 play를 합산해 HashMap에 기록해준다. 2. 정렬 3. 정렬된 Ar.. 2020. 12. 6.
[Java/프로그래머스/해시] Level 2: 위장 문제 programmers.co.kr/learn/courses/30/lessons/42578 코딩테스트 연습 - 위장 programmers.co.kr 참고 링크 2ssue.github.io/algorithm/programmers_42578/ [프로그래머스] 위장 JAVA 프로그래머스_위장 문제 풀이 코드 이 문제에서 필요한 것은 옷 종류의 개수가 몇 가지 있는지이다. 따라서 옷 종류의 이름은 쓸모없는 값이 된다. {옷 종류}:{총 개수} 와 같은 형태로 매칭되어 2ssue.github.io 코드 옷종류:총개수 로 이루어진 HashMap(key-value)을 구성한다. 이후 규칙을 찾아 공식화 하면 된다. 공식은 아래 주석에 import java.util.*; /* if 4종류의 옷과 그 옷이 {n, m,.. 2020. 12. 2.
[Java/백준/BFS] 1655번: 가운데를 말해요 문제 www.acmicpc.net/problem/1655 1655번: 가운데를 말해요 첫째 줄에는 수빈이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 수빈이가 외치는 정수가 차례대로 주어진다. 정수는 -1 www.acmicpc.net 코드 우선순위 큐의 중간 값을 빼내는 게 가능한 건지 계속 고민했다. 물론 안됨ㅎㅎ.. 결국 maxHeap, minHeap 두개를 만들어서 사용하기로 했다. 보통의 minHeap은 우선순위 오름차순이라고 치면 이 가운데 원소를 기준으로 maxHeap, minHeap으로 나누는 것이다. (작은 부분이 maxHeap, 큰 부분이 minHeap) 예를 들어 1, 5, 2, 10, -99, 7, .. 2020. 11. 27.
[Java/백준/DFS] 11724번: 연결 요소의 개수 문제 www.acmicpc.net/problem/11724 11724번: 연결 요소의 개수 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주 www.acmicpc.net 코드 import java.util.*; import java.io.*; class Main{ static ArrayList[] adjacent; static boolean[] visited; public static void dfs(int start) { visited[start] = true; for(int e : adjacent[start.. 2020. 11. 27.
[Java/백준/우선순위 큐] 11286번: 절댓값 힙 문제 www.acmicpc.net/problem/11286 11286번: 절댓값 힙 첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 0이 아니라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net 코드 import java.util.*; import java.io.*; class Main{ public static void main(String[] args) throws IOException{ BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); BufferedWriter bw = new Buffer.. 2020. 11. 25.
[Java/백준/우선순위 큐] 11279번: 최대 힙, 1927번: 최소 힙 자바의 우선순위큐 라이브러리에 원소를 담고 다시 빼면, 우선순위는 오름차순으로 정렬되어 나온다. 따라서 최대 힙을 구현하려면 우선순위 큐를 선언할 때, 매개변수로 Collections.reverseOrder()를 넣어주면 된다. www.acmicpc.net/problem/11279 11279번: 최대 힙 첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0이 www.acmicpc.net import java.util.*; import java.io.*; class Main{ public static void main(String[] args) thro.. 2020. 11. 25.
우선순위 큐(Priority Queue) www.youtube.com/watch?v=AjFlp951nz0&list=WL&index=26 우선순위 큐는 우선순위가 가장 높은 데이터를 가장 먼저 삭제하는 자료구조 구현 방법 1) 리스트를 이용하여 구현 그냥 차례대로 쭉 넣은 다음에 꺼낼 때 하나하나 확인해서 값이 큰 거 출력 2) 힙을 이용하여 구현 단순히 N개의 데이터를 힙에 넣었다가 모두 꺼내는 작업은 정렬과 동일 (힙 정렬) 삽입 시간 삭제 시간 리스트 O(1) O(N) 힙(Heap) O(logN) O(logN) 힙은 완전 이진 트리 자료구조의 일종 루트 노드로부터 시작해서 왼쪽 자식 노드, 오른쪽 자식 노드 순서대로 데이터가 차례대로 삽입되는 트리 힙에서는 항상 루트 노드를 제거한다. 최소 힙(Min Heap) 루트 노드가 가장 작은 값을 .. 2020. 11. 24.
[Java/백준/BFS] 1389번: 케빈 베이컨의 6단계 법칙 문제 www.acmicpc.net/problem/1389 1389번: 케빈 베이컨의 6단계 법칙 첫째 줄에 유저의 수 N (2 ≤ N ≤ 100)과 친구 관계의 수 M (1 ≤ M ≤ 5,000)이 주어진다. 둘째 줄부터 M개의 줄에는 친구 관계가 주어진다. 친구 관계는 A와 B로 이루어져 있으며, A와 B가 친구라는 뜻 www.acmicpc.net 코드 BFS로 풀었다. import java.util.*; import java.io.*; class Main{ static ArrayList[] adjacent; static int users; public static int addCnt(int[] visited) { int sum = 0; for(int e : visited) { //System.out... 2020. 11. 23.
[Java/프로그래머스/탐욕법] Level 2 : 구명 보트 문제 programmers.co.kr/learn/courses/30/lessons/42885 코딩테스트 연습 - 구명보트 무인도에 갇힌 사람들을 구명보트를 이용하여 구출하려고 합니다. 구명보트는 작아서 한 번에 최대 2명씩 밖에 탈 수 없고, 무게 제한도 있습니다. 예를 들어, 사람들의 몸무게가 [70kg, 50kg, 80kg, 5 programmers.co.kr 처음 생각했던 방법(걍 틀림) 우선순위 큐에 넣어서 작은 것들부터 묶으려고 했다. 하지만 이 경우 people = {30, 40, 60, 70}, limit=100 일 때 (30,40) / 60 / 70 으로 3이 리턴된다. 옳은 답은 (70,30) / (60, 40) 으로 2가 리턴되어야 한다. 두번째로 생각한 방법 ( 효율성 테스트: 실패(.. 2020. 11. 10.

티스토리툴바