기록하는 공간

문제 설명 경화는 과수원에서 귤을 수확했습니다. 경화는 수확한 귤 중 'k'개를 골라 상자 하나에 담아 판매하려고 합니다. 그런데 수확한 귤의 크기가 일정하지 않아 보기에 좋지 않다고 생각한 경화는 귤을 크기별로 분류했을 때 서로 다른 종류의 수를 최소화하고 싶습니다. 예를 들어, 경화가 수확한 귤 8개의 크기가 [1, 3, 2, 5, 4, 5, 2, 3]이라고 합시다. 경화가 귤 6개를 판매하고 싶다면, 크기가 1, 4인 귤을 제외한 여섯 개의 귤을 상자에 담으면, 귤의 크기의 종류가 2, 3, 5로 총 3가지가 되며 이때가 서로 다른 종류가 최소일 때입니다. 경화가 한 상자에 담으려는 귤의 개수 k와 귤의 크기를 담은 배열 tangerine이 매개변수로 주어집니다. 경화가 귤 k개를 고를 때 크기가 ..

소수를 찾는 유명한 알고리즘인 에라토스테네스의 체이다. 에라토스테네스의 체란? N보다 작거나 같은 모든 소수를 찾는 알고리즘이다. 2부터 N까지 모든 정수를 적는다. 아직 지우지 않은 수 중 가장 작은 수를 찾는다. 이것을 P라고하고, 이 수는 소수이다. P를 지우고, 아직 지우지 않은 P의 배수를 크기 순서대로 지운다. 아직 모든 수를 지우지 않았다면, 다시 2번 단계로 간다. ex) 소수인 2, 3, 5, 7, ... 의 배수를 지운다. 코드로 구현하면 아래와 같다. public class Eratos { static boolean[] prime = new boolean[121]; public static void main(String[] args) { int N = 120; // 소수는 false,..

문제설명 자연수 n이 주어졌을 때, n의 다음 큰 숫자는 다음과 같이 정의한다. 조건 1: n의 다음 큰 숫자는 n보다 큰 자연수이다. 조건 2: n의 다음 큰 숫자와 n은 2진수로 변환했을 때 1의 개수가 같다. 조건 3: n의 다음 큰 숫자는 조건 1,2를 만족하는 수 중 가장 작은 수이다. 예를 들어 78(1001110)의 다음 큰 숫자는 83(1010011)이다. 입출력 예 n result 78 83 15 23 코드설명 answer에 매개변수로 받은 n을 저장한다. 먼저 매개변수 n을 2진수로 변환한다. String binary = Integer.toBinaryString(n); 변환된 2진수의 1의 개수를 구한다. String 클래스의 charAt()을 이용하여 1을 찾아 oneCount를 증가..

문제설명 1부터 입력받은 숫자 n사이에 있는 소수의 개수를 반환하는 함수를 만들어라. 제한조건 n은 2이상 1000000이하의 자연수이다. 입출력 예 n result 10 4 5 3 코드설명 이 소수 찾기 문제는 에라토스테네스의 체를 사용하여 문제를 풀면 쉽게 풀 수 있다. 소수를 판별하기 위해 boolean배열을 만든다. 0과 1은 소수가 아니므로 true로 초기화해준다. boolean[] prime = new boolean[n + 1]; prime[0] = prime[1] = true; for문을 사용해 prime의 길이의 제곱근만큼 반복문을 실행한다. for (int i = 2; i

문제설명 알파벳 소문자로 이루어진 문자열을 가지고 시작한다. 문자열에서 같은 알파벳이 2개 붙어 있는 짝을 찾는다. 그다음, 그 둘을 제거한 뒤, 앞뒤로 문자열을 이어 붙인다. 이 과정을 반복하여 모두 제거하면 짝지어 제거하기가 종료된다. 문자열 S가 주어졌을 때 성공적으로 수행할 수 있으면 1을, 아닐경우 0을 반환한다. 예를 들어 문자열 S = baabaa 라고 b aa baa -> bb aa -> aa -> 제한사항 문자열의 길이 : 1,000,000이하의 자연수 문자열은 모두 소문자로 이루어져 있다. 입출력 예 s result baabaa 1 cdcd 0 코드설명 이 문제는 stack을 사용한다. Stack stack = new Stack(); stack 이 비어있지 않고, 가장 위에 위치한 값이..

문제설명 1부터 n까지 번호가 붙어있는 n명의 사람이 영어 끝말잇기를 하고 있다. 영어 끝말잇기는 다음과 같은 규칙으로 진행된다. 1번부터 번호 순서대로 한 사람씩 차례대로 단어를 말한다. 마지막 사람이 단어를 말한 다음에는 다시 1번부터 시작한다. 앞사람이 말한 단어의 마지막 문자로 시작하는 단어를 말해야 한다. 이전에 등장했던 단어는 사용할 수 없다. 한 글자인 단어는 인정되지 않는다. 다음은 3명이 끝말잇기를 하는 상황을 나타낸다. tank → kick → know → wheel → land → dream → mother → robot → tank 사람의 수 n과 사람들이 순서대로 말한 단어 words 가 매개변수로 주어질 때, 가장 먼저 탈락하는 사람의 번호와 그 사람이 자신의 몇 번째 차례에 탈..