본문 바로가기

프로그래밍/Algorithm

 (8)
Longest Palindromic Substring Palindrome? 문자열을 거꾸로 해도 원래의 문자열과 같은 문자열 public String longestPalindrome(String s) { if (s.length() == 0) { return ""; } String result = "" + s.charAt(0); for (int i = 0; i i; j--) { String newStr = s.substring(i, j+1); if (isPalindrome(newStr) && result.length() < newStr.length()) { result = newStr; if (s.equals(newStr)) { return s; } } } }..
MedianofTwoSortedArrays https://leetcode.com/problems/median-of-two-sorted-arrays/ Median은 중앙값이라고 표현한다 Average(or mean) 평균값과는 다르다 평균값은 극단적인 값에 영향을 받는다 예를 들어 100가구인 한 마을의 1가구당 연간 소득이 5천만원이라고 하자. 단 1가구가 연간 30억원의 소득을 올린다면 나머지 99가구는 2천만원 정도의 소득밖에 되지 않는다. 즉, 평균이라는 것은 표본들이 균일한 경우가 아니라면 원하는 결과를 얻기 어렵다. 따라서 이런 성질이 다른 표본들(=outlier)을 제거한 후 다시 계산하는 방법들이 많이 사용된다. 중앙값은 홀수 일때 가운데 값을, 짝수 일때는 가운데 두 값의 산순평균 값을 가진다. public double findMe..
코딩테스트 > 연습 깊이/너비 우선 탐색(DFS/BFS) > 타겟 넘버 get(0) +get(1) -get(1) +get(2) -get(2) +get(2) -get(2) +get(3) -get(3) -get(3) ... +get(4) -get(4) ... ... ... END END ... 해당 문제는 위의 표대로 깊이 우선의 탐색이 가능하다.인덱스가 배열 길이만큼 도달하면 탐색을 마친것으로 간주하고 종료한다.종료할 때 target 값이랑 동일하면 count를 늘린다. public class TargetNumber { /* 타겟 넘버 문제 설명 n개의 음이 아닌 정수가 있습니다. 이 수를 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다. -1+1+1+1+1 = 3 +1-1+1+..
Permutation vs Combination & BASEBALL GAME 출처 : http://blog.naver.com/PostView.nhn?blogId=bb_&logNo=221338611903&parentCategoryNo=&categoryNo=67&viewDate=&isShowPopularPosts=false&from=sectionhttps://onsil-thegreenhouse.github.io/programming/algorithm/2018/04/05/permutation_combination/ 순열과 조합은 다르다. 예를 들어 int 배열은 {1, 2, 3, 4, 4, 3, 2, 1, 1}, 그리고 선택 개수는 3이라고 하자. 조합(Combination)하는 경우의 수 : 2,3,41,3,41,2,41,2,3 순열(Permutation)하는 경우의 수 : 2,3,..
프로그래머스 > 완전탐색 > 소수찾기 package search; import java.util.HashSet; import java.util.Set; /** * Description : */ public class Permutation2 { /* https://programmers.co.kr/learn/courses/30/lessons/42839 한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다. 각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 조각으로 만들 수 있는 소수가 몇 개인지 return 하도록 solution 함수를 완성해주세요. 제한사항 numbers는 길이 1 이상 7 이하인 문자열입니다. numbers는 0~9까지 숫자만으로 ..
프로그래머스 > 해시 > 프린터 package stackqueue; import java.util.ArrayList; import java.util.List; import java.util.LinkedList; import java.util.PriorityQueue; import java.util.Queue; public class Printer { /* 일반적인 프린터는 인쇄 요청이 들어온 순서대로 인쇄합니다. 그렇기 때문에 중요한 문서가 나중에 인쇄될 수 있습니다. 이런 문제를 보완하기 위해 중요도가 높은 문서를 먼저 인쇄하는 프린터를 개발했습니다. 이 새롭게 개발한 프린터는 아래와 같은 방식으로 인쇄 작업을 수행합니다. 1. 인쇄 대기목록의 가장 앞에 있는 문서(J)를 대기목록에서 꺼냅니다. 2. 나머지 인쇄 대기목록에서 J보다 ..
프로그래머스 > 해시 > 베스트앨범 package hash; import java.util.ArrayList; import java.util.Collections; import java.util.HashMap; import java.util.List; import java.util.Map; import java.util.stream.Collectors; /** * Description : */ public class Album { //스트리밍 사이트에서 장르 별로 가장 많이 재생된 노래를 두 개씩 모아 베스트 앨범을 출시하려 합니다. //노래는 고유 번호로 구분하며, 노래를 수록하는 기준은 다음과 같습니다. // //속한 노래가 많이 재생된 장르를 먼저 수록합니다. //장르 내에서 많이 재생된 노래를 먼저 수록합니다. //장르 내에서 재생..
프로그래머스 > 해시 > 전화번호 목록 public class PhoneBook { public boolean solution1(String[] phoneBook) {//전화번호부에 적힌 전화번호 중, 한 번호가 다른 번호의 접두어인 경우가 있는지 확인하려 합니다.//전화번호가 다음과 같을 경우, 구조대 전화번호는 영석이의 전화번호의 접두사입니다.////구조대 : 119//박준영 : 97 674 223//지영석 : 11 9552 4421//전화번호부에 적힌 전화번호를 담은 배열 phone_book 이 solution 함수의 매개변수로 주어질 때, 어떤 번호가 다른 번호의 접두어인 경우가 있으면 false를 그렇지 않으면 true를 return 하도록 solution 함수를 작성해주세요.////제한 사항//phone_book의 길이는 1 이상 ..

티스토리툴바