Codility - Triangle ☞ 문제 링크 문제 설명 중복되지 않는 인덱스 3가지를 선택하고, 2가지 인덱스 값의 합이 나머지 1가지의 인덱스 값보다 모두 큰 경우가 존재하는지 찾는 문제입니다. 예제로 주어진 케이스는 A[0] = 10, A[2] = 5, A[4] = 8 인 경우인데,10 + 5 > 8 (참) // A[P] + A[Q] > A[R]5 + 8 > 10 (참) // A[Q] + A[R] > A[P]8 + 10 > 5 (참) // A[R] + A[P] > A[Q]세가지 경우가 문제에 내용을 만족하는 참입니다. 이런 경우의 배열이라면 1을 반환하고, 아니라면 0을 반환해야 합니다. 풀이에 핵심은 배열을 정렬한 상태에서 인접한 세개의 인덱스간의 비교만 진행하면 됩니다.(그리고 인덱스에 대한..
코딜리티(Codility) - GenomicRangeQuery ☞ 문제링크 문제 설명 주어진 문자열(S)의 각 문자 A,C,G,T는 각각 'impact factor'라는 이름의 값으로 1,2,3,4를 갖고 있습니다. P배열과 Q배열은 주어진 문자열(S)인덱스를 말합니다. 예를들어, P[0] = 2 / Q[0] = 4 인 경우는 CAGCCTA 문자열의 2번째 4번째 문자열을 가르키는 것이고, CAGCCTA 그 사이에 존재하는 문자열의 'impact facotr' 값 중에 가장 작은 값을 찾아야 합니다. CAGCCTA 에서 G C C 중 가장 작은 값은 C의 값인 2가 됩니다. 같은 방법으로 P[1] = 5 / Q[1] = 5 인 경우는 CAGCCTA 4가 되고, P[2] = 0 / Q[2] = 6 인 경우..
프로그래머스 알고리즘 - 더 맵게 ☞ 프로그래머스 '더 맵게' 문제링크 음식 중에 가장 덜 매운 2가지의 음식을 반복적으로 선택해야 합니다. 우선순위 큐(Priority Queue)를 사용하면 가장 덜 매운 2가지 음식을 찾기 편합니다. 우선순위 큐에 대한 내용은 이전 포스팅에 있습니다. ☞ 우선순위 큐 - Java에서 다루기 풀이코드 (java) class Solution { public int solution(int[] scoville, int K) { int answer = 0; PriorityQueue priorityQueue = new PriorityQueue(); //우선순위 큐에 음식 담아주기 for (int i : scoville) { priorityQueue.add(i); } //가장 덜..
우선순위 큐(Priority Queue) 일반적인 큐는 제일 먼저 들어간 데이터가 가장 먼저 나오게 되는 자료구조 입니다. 대표적인 예로는 은행업무를 기다리는 손님들의 대기열 입니다. 이런 큐의 특성과 달린 우선순위 큐(Priority Queue)는 들어간 순서에 상관없이 일정한 규칙에 따라 우선순위를 선정하고, 우선순위가 가장 높은 데이터가 가장 먼저 나오게 됩니다. 대표적인 예로는 병원의 응급환자를 생각하면 됩니다. 은행과 달리 위급한 우선순위에 따라 먼저 처리되기 때문입니다. 우선순위 큐 사용하기 우선순위 큐도 Java내부적으로 구현이 되어 있습니다. 일반적인 큐를 사용하는 것처럼 add(); peek(); poll(); 등의 메소드를 사용할 수 있습니다. PriorityQueue priorityQ..
Minimum Path Sum ☞ 문제링크 크기가 m,n인 2차원 배열의 좌측 상단(0,0)부터, 우측 하단(m-1,n-1) 까지 이동하는데, 이동 경로의 배열 값들을 모두 더하게 되는 경우, 이 값의 최소 값을 구하는 문제입니다. 예시로 들어둔 배열은 아래와 같습니다. 괄호안에는 좌표를 표시했습니다. 1 (0,0) 3 (0,1) 1 (0,2) 1 (1,0) 5 (1,1) 1 (1,2) 4 (2,0) 2 (2,1) 1 (2,2) 각 좌표들의 최소 합은 다음과 같이 구할 수 있습니다.좌표가 0,0 인 경우는 항상 그 좌표의 값과 같습니다. (경우의 수가 1개)좌표가 (0,x) 혹은 (x,0) 처럼 0이 들어가는 경우도 경우의 수가 1개 뿐입니다. 바로 이전의 좌표 값만 더해주면 됩니다. 예를들어 0,1의 ..
참조 투명성 수학과 프로그래밍에서 모두 '함수'라는 말을 사용하고, 유사한 개념으로 사용됩니다. 하지만 둘의 결정적으로 다른 점이 있습니다. 수학에서의 함수는 같은 입력값이면 계산 된 결과는 항상 같습니다. 예를들어 f(x) = x*2 라는 함수가 있을 때, 같은 x 값을 넣게 되면 반환되는 f(x) 값은 항상 같습니다. 하지만 프로그래밍에서는 항상 같지 않습니다. int count = 0; int count(){ return count++; } 위와 같은 함수 count의 경우 매번 반환되는 값이 다르게 됩니다. final int x = 10; int getX(){ return x; } 반면 위와 같은 함수는 항상 같은 x의 값을 반환하게 됩니다. 이러한 경우를 '참조 투명'하다 라고 합니다. 앞서서 ..
Best Time to Buy and Sell Stock ☞ 문제링크 입력값으로 주식(Stock)의 가격이 나오게 되고, 가장 큰 수익을 내게 되는 경우의 수익값을 반환해주면 됩니다. 예를 들어, 입력값이 7,1,5,3,6,4 인 경우 가격1에 사서 6에 파는 경우 수익이 가장 크게 나오게 됩니다. 7인 경우는 1의 과거이기 때문에 1 이후에 나온 값 중에서만 팔아야합니다. 문제풀이 (java) 순차적으로 읽어가며 가장 작은 값이 나온 경우 minPrice를 대체하고, minPrice와 현재 시장가의 차로 수익을 계산 합니다. 수익이 이전까지 계산된 수익보다 큰 경우 대체합니다. 만약 minPrice를 따로 구하지 않고 모든 경우를 계산 하게 되면 정답을 구할 수는 있으나 효율성이 크게 떨어지게 됩니다...
Forbidden Zero ☞ 문제 링크 입력받은 정수의 다음 숫자를 구하면 됩니다. 다만 숫자 중에 0이 포함되어 있으면 안됩니다. 예를들어 9의 다음 숫자는 0을 포함한 10이 아닌 11이 되어야 하고, 99의 다음 숫자는 100이 아닌 111이 되어야 합니다. 입력 값에 1을 더한 숫자를 구하고, 그 숫자의 0이 있으면 그 0을 1로 바꿔주는 방식으로 0이 없는 다음 숫자를 구할 수 있습니다. 저는 숫자를 char로 바꾸고, char를 하나씩 비교해가며 0인 char를 1로 바꿔주는 방법을 선택 했습니다. 반환할때는 다시 정수로 변환합니다. 풀이코드 (java) public class Main { public static void main(String[] args) { Scanner sc = new..