본문 바로가기

알고리즘 문제풀이30

프로그래머스 가장 큰수 (정렬) 가장 큰 수 ​ 문제 설명 0 또는 양의 정수가 주어졌을 때, 정수를 이어 붙여 만들 수 있는 가장 큰 수를 알아내 주세요. 예를 들어, 주어진 정수가 [6, 10, 2]라면 [6102, 6210, 1062, 1026, 2610, 2106]를 만들 수 있고, 이중 가장 큰 수는 6210입니다. 0 또는 양의 정수가 담긴 배열 numbers가 매개변수로 주어질 때, 순서를 재배치하여 만들 수 있는 가장 큰 수를 문자열로 바꾸어 return 하도록 solution 함수를 작성해주세요. 제한 사항 numbers의 길이는 1 이상 100,000 이하입니다. numbers의 원소는 0 이상 1,000 이하입니다. 정답이 너무 클 수 있으니 문자열로 바꾸어 return 합니다. 입출력 예 numbers return.. 2020. 5. 26.
프로그래머스 카펫(완전탐색) Leo는 카펫을 사러 갔다가 아래 그림과 같이 중앙에는 노란색으로 칠해져 있고 테두리 1줄은 갈색으로 칠해져 있는 격자 모양 카펫을 봤습니다. Leo는 집으로 돌아와서 아까 본 카펫의 노란색과 갈색으로 색칠된 격자의 개수는 기억했지만, 전체 카펫의 크기는 기억하지 못했습니다. Leo가 본 카펫에서 갈색 격자의 수 brown, 노란색 격자의 수 yellow가 매개변수로 주어질 때 카펫의 가로, 세로 크기를 순서대로 배열에 담아 return 하도록 solution 함수를 작성해주세요. 제한사항 갈색 격자의 수 brown은 8 이상 5,000 이하인 자연수입니다. 노란색 격자의 수 yellow는 1 이상 2,000,000 이하인 자연수입니다. 카펫의 가로 길이는 세로 길이와 같거나, 세로 길이보다 깁니다. 입.. 2020. 5. 22.
프로그래머스 큰 수 만들기(그리디) 큰 수 만들기 ​ 문제 설명 어떤 숫자에서 k개의 수를 제거했을 때 얻을 수 있는 가장 큰 숫자를 구하려 합니다. 예를 들어, 숫자 1924에서 수 두 개를 제거하면 [19, 12, 14, 92, 94, 24] 를 만들 수 있습니다. 이 중 가장 큰 숫자는 94 입니다. 문자열 형식으로 숫자 number와 제거할 수의 개수 k가 solution 함수의 매개변수로 주어집니다. number에서 k 개의 수를 제거했을 때 만들 수 있는 수 중 가장 큰 숫자를 문자열 형태로 return 하도록 solution 함수를 완성하세요. 제한 조건 number는 1자리 이상, 1,000,000자리 이하인 숫자입니다. k는 1 이상 number의 자릿수 미만인 자연수입니다. 입출력 예 number k return 1924.. 2020. 5. 22.
프로그래머스 전화번호 목록(해시) import java.util.Arrays; class Solution { public boolean solution(String[] phone_book) { boolean answer = true; //전화번호가 저장된 배열 중에서 띄어쓰기를 기준으로 나눈다. //공백단위로 짜르기 for(int i = 0 ; i < phone_book.length;i++) { if(phone_book[i].contains(" ")) { phone_book[i] = phone_book[i].substring(0,phone_book[i].indexOf(" ")); }else { continue; } } // 짤랏으면 반복문을 통해 loop: for(int i = 0 ; i < phone_book.length;i++) { .. 2020. 5. 21.
프로그래머스 최댓값과 최솟값 문제 설명 문자열 s에는 공백으로 구분된 숫자들이 저장되어 있습니다. str에 나타나는 숫자 중 최소값과 최대값을 찾아 이를 (최소값) (최대값)형태의 문자열을 반환하는 함수, solution을 완성하세요. 예를들어 s가 1 2 3 4라면 1 4를 리턴하고, -1 -2 -3 -4라면 -4 -1을 리턴하면 됩니다. 제한 조건 s에는 둘 이상의 정수가 공백으로 구분되어 있습니다. sreturn 1 2 3 4 1 4 -1 -2 -3 -4 -4 -1 나의 풀이 문자열을 split 함수를 이용해 공백단위로 쪼개 String 형 배열에 저장하고 String 형의 배열을 Int 형 배열에 옮겨담아 정렬하여 맨앞의 수(제일작은수)를 앞에 마지막수(제일큰수)를뒤에 놓고 출력 import java.util.Arrays; .. 2020. 5. 19.
프로그래머스 피보나치 수 문제 설명 피보나치 수는 F(0) = 0, F(1) = 1일 때, 1 이상의 n에 대하여 F(n) = F(n-1) + F(n-2) 가 적용되는 수 입니다. 예를들어 F(2) = F(0) + F(1) = 0 + 1 = 1 F(3) = F(1) + F(2) = 1 + 1 = 2 F(4) = F(2) + F(3) = 1 + 2 = 3 F(5) = F(3) + F(4) = 2 + 3 = 5 와 같이 이어집니다. 2 이상의 n이 입력되었을 때, n번째 피보나치 수를 1234567으로 나눈 나머지를 리턴하는 함수, solution을 완성해 주세요. 제한 사항 * n은 1이상, 100000이하인 자연수입니다. 입출력 예 nreturn 3 2 5 5 입출력 예 설명 피보나치수는 0번째부터 0, 1, 1, 2, 3, 5.. 2020. 5. 19.
DFS 와 BFS DFS - depth-first search 깊이 우선 탐색 트리나 그래프에서 한 루트로 탐색하다가 특정 상황에서 최대한 깊숙히 들어가서 확인한 뒤 다시 돌아가 다른 루트로 탐색하는 방식이다. 일반적으로 재귀호출을 사용하지만 스택으로 구현하기도 한다. 단순 검색 속도 자체는 BFS에 비해서 느리다. 장점 - 단지 현 경로상의 노드들만을 기얻하면 되므로 저장 공간의 수요가 비교적 적다. - 목표 노드가 깊은 단계에 있을 경우 해를 빨리 구할 수 있다. 단점 - 해가 없는 경로에 깊이 빠질 가능성이 있다. - 얻어진 해가 최단 경로가 된다는 보장이 없다. BFS - 넓이 우선 탐색 DFS는 갈림길에서 하나의 길로 들어서서 막다른 길이 나올 때까지 깊게 탐색을 하는 것을 볼 수 있고, BFS는 갈림길에 연결되.. 2020. 5. 18.
프로그래머스 타겟 넘버 깊이/너비 우선 탐색(DFS/BFS) 풀이법 n개의 음이 아닌 정수 숫자를 적절히 더하거나 빼야한다 처음에는 모든수를 검색해야 겠다는 생각은 했지만 DFS로 풀어야 겠다는 생각은 하지 못했다. DFS는 점화식과 종료시점을 찾는것에 매우 중요하다. N개의 수가 주어지므로 DFS 깊이우선탐색에서 깊이가 N인것을 알수 있다. 두가지 경우로 하나는 양수 하나는 음수로 하여 재귀함수를 구현하고 깊이가 주어진 배열의길이와 같아지면 종료하여 배열을 모두 더해 타겟과 같은지 비교하여 같으면 ANSWER를 증가시킨다 class Solution { static int answer = 0; public void dfs (int[] numbers, int target, int d) { if(d == numbers.length) { // 깊이가 배열의 길이와 같다.. 2020. 5. 18.
프로그래머스 더 맵게(힙) 힙(Heap) ​ 완전 이진트리의 일종이다. 반정렬 상태(완전히 정렬된 상태가 아님)이며 완전 이진트리와는 다르게 중복값이 허용된다. 삽입/갖제는 트리구조이기 때문에 OlogN 이므로 매우 빠르다 보통 우선순위 큐가 힙으로 많이 구변되는데, 배열과 리스트보다 효율적이기 때문이다. ​ 힙은 최대힙과 최소힙으로 나누어지고, 최대힙은 부모 노드가 가장 큰 것이며 최소힙은 부모 노드가 가장 작은 것이다. 이를통해 여러 값 중에서 최소 값이나 최대값을 빨리 찾을 때 유용하게 이용할 수 있다. ​ 힙 자료구조는 보통 배열을 이용하며, 0 번째 인덱스는 편하게 구현하기 위해서 사용하지 않는다. ​ ​ ​ 우선순위 큐 일반적으로 큐는 선입선출의 대기열 규칙을 가지고 있다. 말그대로 먼저온놈이 먼저 나간다. ​ prio.. 2020. 5. 17.