정렬33 [Baekjoon] 1758 - 알바생 강호 📝 문제 🔑 풀이 과정 · 한 사람이 내는 팁: 원래 주려고 생각했던 돈 - (받은 등수 - 1) 등수가 뒤로 갈수록 차감되는 팁의 액수가 많아진다. 즉, 강호가 최대로 팁을 받으려면, 팁의 액수가 큰 사람일수록 앞 등수에 배치해야 한다. · 팁을 내림차순으로 정렬한 뒤, 원래 주려고 생각했던 돈 - (받은 등수 - 1) 식을 사용해서 팁의 총액을 계산한다. 주의해야 할 점은, 계산된 팁이 음수라면 강호는 팁을 받을 수 없다는 점이다. → 식의 결과가 음수라면 팁이 0원 🔓 답안 import java.io.*; import java.util.ArrayList; import java.util.Collections; public class Main { public static void main(String[.. 2023. 8. 16. [Baekjoon] 18870 - 좌표 압축 📝 문제 🔑 풀이 과정 · 값들을 배열에 입력받고, 그 배열내에서 현재 가리키는 값보다 작은 값의 개수를 구하는 것이 이 문제의 목적이다. 다만 여기서 작은 값은 중복을 허용하지 않는다. · N이 10^6까지기 때문에 일반적인 전체 탐색 방법(이중 for문)으로 푼다면 시간초과가 될 것이다. · 입력 배열을 정렬한 정렬 배열을 만든다. (따로 만드는 이유는 입력 배열이 출력할 때 쓰이기 때문) 정렬 배열을 전체탐색 하면서 Map에 를 넣는다. 그 후 입력 배열을 탐색하면서 Map에서 value를 꺼낸다. · 예제 2 풀이 이미지 · 처음에는 정렬배열을 만들고, 그 후에 또 ArrayList를 새로 생성했다. 그리고 정렬 배열을 전체탐색하면서 중복값을 피해서 ArrayList에 넣고, 그 ArrayList.. 2023. 8. 1. [Baekjoon] 1302 - 베스트셀러 📝 문제 🔑 풀이 과정 · 책 개수 카운팅은 Map을 쓰고, 사전 순으로 가장 앞서는 제목을 출력하는 거니까 자바에서 기본제공하는 정렬을 쓰면 된다 까지는 파악했는데, 그 정렬을 어떻게 하지?에서 막혔었다. 근데 의외로 해결법은 간단했는데, → list로 따로 담아서 정렬을 시켜주면 된다. · 왜 항상 자료구조를 문제당 1개만 쓰려고 하는지...! 여러개 써도 상관없는데! 좀 생각을 다차원적으로 좀 해봐 내 자신아 · 그리고 Map.entrySet()이 문제풀이하면서 좀 많이 쓰이는 것 같다. 이번 기회에 이거 사용법좀 익히는 걸로... 🔓 답안 import java.io.*; import java.util.ArrayList; import java.util.Collections; import java.u.. 2023. 7. 19. [Baekjoon] 1931 - 회의실 배정 📝 문제 🔑 풀이 과정 · 이 문제는 예전에도 몇 번 풀어보려고 시도했는데, 아무리 생각해도 어떻게 해야할지를 감을 못잡았다. (그리디로 분류 되는걸 알면서도 못풀었다). 그러다가 오늘은 결국 다른분들 풀이를 참고해서 해결했다. · 우리의 목표는 최대 사용할 수 있는 회의의 최대 개수이다. 이를 그리디로 어떻게 해결할 것인가? 현재 진행중인 회의가 끝난 시점에서 시작할 수 있는 회의중에서, 가장 빨리 끝나는 회의를 선택하면 된다. · 이 문제를 풀이하기 위해서는, 회의의 끝나는 시간을 기준으로 오름차순으로 정렬한다. 처음엔 인덱스 0에 위치한 회의가 제일 빨리끝나므로 픽해주고(카운트 증가), 그 이후에 배열을 순차탐색하면서 픽했던 회의의 끝나는 시간보다 시작시간이 같거나 큰것을 또 픽해준다.(카운트 증가.. 2023. 7. 14. [Baekjoon] 1764 - 듣보잡 📝 문제 🔑 풀이 과정 이 문제는 듣도 보도 못한 사람의 집합과 보도 못한 사람의 집합 총 2개의 집합의 교집합을 구하는 기본적인 집합 문제이다. 어려운 건 없었고, HashSet을 정렬하려면 List로 변환시킨 후 정렬해야 된다는 것을 알았다. 🔓 답안 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 BufferedWriter(new OutputStreamWriter(S.. 2023. 7. 7. [알고리즘] 정렬 - 카운팅 정렬(counting sort, 계수 정렬) 🟡 카운팅 정렬(counting sort, 계수 정렬) - 다른 정렬 알고리즘들과는 다르게 입력 배열의 값을 비교하지 않고, 각 값의 등장 횟수를 세어 정렬하는 방식 - 따라서 입력 배열의 값의 범위가 제한되어야 한다. - 카운팅 정렬은 입력 배열의 크기가 N, 입력 값의 범위를 K라고 할 때, O(N+K)의 시간 복잡도를 가진다. - 입력 값의 범위가 큰 경우에는 메모리 사용량이 많아진다. 🟡 카운팅 정렬 진행 과정 카운팅 정렬의 기본 아이디어는 각 입력 요소의 등장횟수를 기록하기 위해 카운트 배열을 사용하는 것 ① 입력 배열을 순회하며 각 요소의 등장 횟수를 카운트 배열에 기록한다. 카운트 배열의 인덱스는 입력 요소의 값이고, 각 인덱스의 값은 해당 요소의 등장 횟수다. ② 카운트 배열을 누적 합 배.. 2023. 6. 30. 이전 1 2 3 4 ··· 6 다음
