본문 바로가기
  • Jetpack 알아보기

알고리즘120

[JAVA] 프로그래머스 Lv.1 : 다트 게임 🔥 2018 KAKAO BLIND RECRUITMENT 1. 다트 게임은 총 3번의 기회로 구성된다. 2. 각 기회마다 얻을 수 있는 점수는 0점에서 10점까지이다. 3. 점수와 함께 Single(S), Double(D), Triple(T) 영역이 존재하고 각 영역 당첨 시 점수에서 1제곱, 2제곱, 3제곱 (점수1 , 점수2 , 점수3 )으로 계산된다. 4. 옵션으로 스타상(*) , 아차상(#)이 존재하며 스타상(*) 당첨 시 해당 점수와 바로 전에 얻은 점수를 각 2배로 만든다. 아차상(#) 당첨 시 해당 점수는 마이너스된다. 5. 스타상(*)은 첫 번째 기회에서도 나올 수 있다. 이 경우 첫 번째 스타상(*)의 점수만 2배가 된다. (예제 4번 참고) 6. 스타상(*)의 효과는 다른 스타상(*)의 .. 2021. 6. 3.
[JAVA] 프로그래머스 Lv.1 : 크레인 인형뽑기 게임 🔥 2019 카카오 개발자 겨울 인턴십 예제: board moves result [[0,0,0,0,0],[0,0,1,0,3],[0,2,5,0,1],[4,2,4,4,2],[3,5,1,3,1]] [1,5,3,5,1,2,1,4] 4 제한 조건: board 배열은 2차원 배열로 크기는 "5 x 5" 이상 "30 x 30" 이하입니다. board의 각 칸에는 0 이상 100 이하인 정수가 담겨있습니다. 0은 빈 칸을 나타냅니다. 1 ~ 100의 각 숫자는 각기 다른 인형의 모양을 의미하며 같은 숫자는 같은 모양의 인형을 나타냅니다. moves 배열의 크기는 1 이상 1,000 이하입니다. moves 배열 각 원소들의 값은 1 이상이며 board 배열의 가로 크기 이하인 자연수입니다. Solution #1 impo.. 2021. 6. 2.
[JAVA] 프로그래머스 Lv.1 : 예산 🔥 Summer/Winter Coding (~2018) 예제: d budget result [1, 3, 2, 5, 4] 9 3 [2, 2, 3, 3] 10 4 제한 조건: d는 부서별로 신청한 금액이 들어있는 배열이며, 길이(전체 부서의 개수)는 1 이상 100 이하입니다. d의 각 원소는 부서별로 신청한 금액을 나타내며, 부서별 신청 금액은 1 이상 100,000 이하의 자연수입니다. budget은 예산을 나타내며, 1 이상 10,000,000 이하의 자연수입니다. Solution #1 import java.util.Arrays; class Solution { public int solution(int[] d, int budget) { int answer = 0; Arrays.sort(d); for (.. 2021. 6. 2.
[JAVA] 프로그래머스 Lv.1 : 로또의 최고 순위와 최저 순위 🔥 2021 Dev-Matching : 웹 백엔드 개발자 (상반기) 예제: arr result [1,1,3,3,0,1,1] [1,3,0,1] [4,4,4,3,3] [4,3] 제한 조건: lottos는 길이 6인 정수 배열입니다. lottos의 모든 원소는 0 이상 45 이하인 정수입니다. 0은 알아볼 수 없는 숫자를 의미합니다. 0을 제외한 다른 숫자들은 lottos에 2개 이상 담겨있지 않습니다. lottos의 원소들은 정렬되어 있지 않을 수도 있습니다. win_nums은 길이 6인 정수 배열입니다. win_nums의 모든 원소는 1 이상 45 이하인 정수입니다. win_nums에는 같은 숫자가 2개 이상 담겨있지 않습니다. win_nums의 원소들은 정렬되어 있지 않을 수도 있습니다. Solution.. 2021. 6. 2.
[JAVA] 프로그래머스 Lv.1 : 같은 숫자는 싫어 예제: arr result [1,1,3,3,0,1,1] [1,3,0,1] [4,4,4,3,3] [4,3] 제한 조건: 배열 arr의 크기 : 1,000,000 이하의 자연수 배열 arr의 원소의 크기 : 0보다 크거나 같고 9보다 작거나 같은 정수 Solution #1 import java.util.*; public class Solution { public int[] solution(int[] arr) { Stack stack = new Stack(); for (int i : arr) { if (stack.isEmpty()) { stack.push(i); } else if (stack.peek() != i) { stack.push(i); } } int[] answer = new int[stack.siz.. 2021. 6. 2.
[JAVA] 프로그래머스 Lv.1 : 신규 아이디 추천 🔥 2021 KAKAO BLIND RECRUITMENT 1단계 new_id의 모든 대문자를 대응되는 소문자로 치환합니다. 2단계 new_id에서 알파벳 소문자, 숫자, 빼기(-), 밑줄(_), 마침표(.)를 제외한 모든 문자를 제거합니다. 3단계 new_id에서 마침표(.)가 2번 이상 연속된 부분을 하나의 마침표(.)로 치환합니다. 4단계 new_id에서 마침표(.)가 처음이나 끝에 위치한다면 제거합니다. 5단계 new_id가 빈 문자열이라면, new_id에 "a"를 대입합니다. 6단계 new_id의 길이가 16자 이상이면, new_id의 첫 15개의 문자를 제외한 나머지 문자들을 모두 제거합니다. 만약 제거 후 마침표(.)가 new_id의 끝에 위치한다면 끝에 위치한 마침표(.) 문자를 제거합니다. .. 2021. 6. 2.
[Java] 정렬 알고리즘 (4) - 퀵 정렬 (Quick Sort) 퀵 정렬 (Quick Sort) 1. Pivot 값을 기준으로 왼쪽에서부터 검사해서 큰 값을, 오른쪽에서부터 작은 값을 발견한다. 2. 두 값을 바꾸기 연산하고, 같은 과정을 수행한다. 3. 큰 값의 index 와 작은 값의 index 가 교차하는 경우, 작은 값과 Pivot 값을 바꾸기 연산한다. → Pivot 값을 기준으로 왼쪽은 Pivot 값보다 작은 값들, 오른쪽은 큰 값들로 분할된다. 4. 분할된 영역에서 같은 과정을 수행한다. → 재귀 성격 3. 시간 복잡도 : O(𝑁𝑙𝑜𝑔𝑁) 4. 작은 값과 큰 값으로 분할을 할 수 없는 경우 = 이미 정렬되어 있는 경우 : O(𝑁²) import java.util.Arrays; public class QuickSort { int[] array = new .. 2021. 5. 23.
[Java] 정렬 알고리즘 (3) - 삽입 정렬 (Insertion Sort) 삽입 정렬 (Insertion Sort) 1. 앞의 원소들이 이미 정렬이 되어 있다고 가정한다. 2. 특정 원소에서 앞의 원소들을 살펴보며 적당한 위치를 찾는 것 3. 시간 복잡도 : O(𝑁²) 4. 선택 정렬, 버블정렬보다 효율적인 알고리즘 → 필요 시에 바꾸기 연산을 수행하기 때문. 특히 이미 정렬이 되어 있을 경우에는최고의 효율을 보여준다. import java.util.Arrays; public class InsertSort { int[] array = new int[]{10, 2, 5, 8, 12, 73}; public void sort() { int j, temp; for (int i = 0; i = 0 && a.. 2021. 5. 23.
[Java] 정렬 알고리즘 (2) - 버블 정렬 (Bubble Sort) 버블 정렬 (Bubble Sort) 1. 두 숫자를 비교해서 더 작은 숫자를 왼쪽에 두는 것 2. 반복이 끝났을 때, 최댓값이 맨 뒤에 있게 된다. 3. 시간 복잡도 : O(𝑁²) 4. 선택 정렬보다 비효율적인 알고리즘 → 선택 정렬은 비교하면서 최솟값을 저장하고, 한 번 반복이 끝나고 바꾸기 연산을 수행하지만 버블 정렬은 비교할 때마다 바꾸기 연산이 이뤄지기 때문이다. import java.util.Arrays; public class BubbleSort { int[] array = new int[]{10, 2, 5, 8, 12, 73}; public void sort() { int temp; for (int i = 0; i < array.length; i++) { for (int j = 0; j < .. 2021. 5. 23.
[Java] 정렬 알고리즘 (1) - 선택 정렬 (Selection Sort) 선택 정렬 (Selection Sort) 1. 가장 작은 숫자를 가장 앞에 두는 것 2. 반복이 끝났을 때, 최솟값이 맨 앞에 있게 된다. 3. 시간 복잡도 : O(𝑁²) import java.util.Arrays; public class SelectionSort { int[] array = new int[]{10, 2, 5, 8, 12, 73}; public void sort() { int min, temp, index = 0; for (int i = 0; i array[j]) { min = array[j]; index = j; } } temp = .. 2021. 5. 23.