문제 1보다 큰 N개의 도시 중 한 곳에 공항을 지을 예정입니다. 사람들의 편의를 위해 공항으로부터 각 사람들까지의 도시간 이동 거리가 최소가 되는 도시에 짓기로 하였습니다. 편의상 도시는 일직선상에 놓여있다고 가정하며 좌표의 범위는 음수가 포함됩니다. 또한 좌표는 정렬되어 있지 않습니다. 직선상의 위치와 그 도시에 사는 사람들의 수가 주어질 때, 공항을 지을 도시의 위치를 반환해주는 함수 chooseCity 함수를 완성하세요. 거리가 같은 도시가 2개 이상일 경우 위치가 더 작은 쪽의 도시를 선택하면 됩니다. 예를 들어 다음과 같은 정보의 도시가 있다고 가정해 봅시다. 위치 1 2 3 인구수 5 2 3 이 살 경우, 각각의 도시에 공항을 지었을 때의 사람들의 이동 거리는 8, 8, 12 이므로 1번 또..
코딩테스트
문제 1년을 기준으로 매월 K일이 주어졌을 때 해당 일이 평일인지(월~금) 또는 주말인지(토, 일) 구하는 알고리즘을 작성하시오. 입력: day, k day: 매년 1월 1일의 날짜. 월요일부터 일요일까지를 나타내는 int형 값. 월: 0, 화: 1, 수: 2, … 토: 5, 일: 6 k: 날짜(1~28 사이의 자연수) 윤년은 계산하지 않고 일반적으로 월은 1월부터 12월까지 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31일로 가정한다. 예를 들어 1월 1일이 월요일이라 가정하고 매 달 1일의 날짜를 구하려고 하면 입력은 day = 0, k = 1이다. 결과는 1월 1일이 월요일, 즉 평일이므로 0, 2월 1일은 목요일이므로 평일 0, .. 이와 같은 방식으로 반환되는..
문제 대문자 알파벳 A~Z중 임의로 구성된 8개의 카드 3세트가 주어진다. 주어지는 카드 세트를 활용하여 입력된 Words중 만들 수 있는 Word를 반환하라. 만드는 규칙은 다음과 같다. 조건 1. 모든 카드는 한번만 쓸 수 있다. 조건 2. A~Z까지 모든 카드가 존재하지 않을 수도 있다. 조건 3. 동일한 카드가 존재할 수 있으며, 동일한 카드는 동일한 라인에 존재한다. 조건 4. 3세트(줄) 중 어느 하나라도 사용되지 않으면 안된다. 아무것도 만들 수 있는 단어가 없으면 {“-1”}을 반환한다. 문제의 예시는 다음과 같다. 알파벳 카드 { "ABCDEFGH", "IJKLMNOP", "QRSTUVWX" } 가 다음과 같이 주어지고 만들 단어가 { "AIMR", "CBOX", "ANV", "AGIP"..
문제 어떤 호텔의 방을 예약하려 한다. 최종적으로 방에 예약 된 사람의 번호를 출력하라. 단, 예약을 취소할 경우 대기열에서 제외되고, 취소한 사람이 다시 예약을 하는 경우 대기열의 맨 뒤에 추가된다. 호텔의 방의 개수는 K로 주어지고, 회원에 대한 상태가 입력으로 주어진다. 입력의 형태는 다음과 같다. [m, n] 형태의 고객 x 명 ( x는 1~10만 ), 방의 개수 K m : 고객 이름(1, 2, ,3, 4, 5, … 자연수) n : 0 또는 1 0은 예약 취소, 1은 예약 K : 1~1000까지 자연수 다음은 테스트 케이스이다. 입력: {[1,1], [2,1], [3,1], [2,0], [2,1]}, 2 출력: {1, 3} 먼저 방의 개수는 2개이다. 1이라는 사람이 예약을 하였고 다음으로 2와 ..
문제 자연수 N개로 이루어진 집합 중에, 각 원소의 합이 S가 되는 수의 집합은 여러 가지가 존재합니다. 최고의 집합은, 위의 조건을 만족하는 집합 중 각 원소의 곱이 최대가 되는 집합을 의미합니다. 집합 원소의 개수 n과 원소들의 합 s가 주어지면, 최고의 집합을 찾아 원소를 오름차순으로 반환해주는 bestSet 함수를 만들어 보세요. 만약 조건을 만족하는 집합이 없을 때는 배열 맨 앞에 –1을 담아 반환하면 됩니다. 예를 들어 n=3, s=13이면 [4,4,5]가 반환됩니다. (자바는 집합이 없는 경우 크기가 1인 배열에 -1을 담아 반환해주세요.) 풀이 #include #include #include using namespace std; vector bestSet(int no, int sum) { ..
문제 앞에서부터 읽을 때와 뒤에서부터 읽을 때 똑같은 단어를 팰린드롬(palindrome)이라고 합니다. 예를들어서 racecar, 10201은 팰린드롬 입니다. 두 자연수 n, m이 매개변수로 주어질 때, n 이상 m 이하의 자연수 중 팰린드롬인 숫자의 개수를 return 하도록 solution 함수를 완성해 주세요. 제한사항 m은 500,000이하의 자연수이며, n은 m 이하의 자연수입니다. 입출력 예 n m result 1 100 18 100 300 20 입출력 예 설명 입출력 예 #1 1 이상 100 이하의 팰린드롬은 다음과 같이 18개가 있습니다. 1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 22, 33, 44, 55, 66, 77, 88, 99 입출력 예 #2 100 이상 300 이..
문제 O와 X로 채워진 표가 있습니다. 표 1칸은 1 x 1 의 정사각형으로 이루어져 있습니다. 표에서 O로 이루어진 가장 큰 정사각형을 찾아 넓이를 반환하는 findLargestSquare 함수를 완성하세요. 예를 들어 1 2 3 4 5 X O O O X X O O O O X X O O O X X O O O X X X X X 가 있다면 정답은 1 2 3 4 5 X O O O X X O O O O X X O O O X X O O O X X X X X 가 되며 넓이는 9가 되므로 9를 반환해 주면 됩니다. 풀이 해당 문제는 프로그래머스 뿐만 아니라 백준을 비롯한 다양한 알고리즘 연습 사이트에 등장하며 코딩 테스트에서도 종종 나오는 단골 문제 중 하나이다.(물론 응용되지만..) 간단하게 요약하면 현재 지점의..
문제 수학을 공부하던 민지는 재미있는 사실을 발견하였습니다. 그 사실은 바로 연속된 자연수의 합으로 어떤 숫자를 표현하는 방법이 여러 가지라는 것입니다. 예를 들어, 15를 표현하는 방법은 (1+2+3+4+5) (4+5+6) (7+8) (15) 로 총 4가지가 존재합니다. 숫자를 입력받아 연속된 수로 표현하는 방법을 반환하는 expressions 함수를 만들어 민지를 도와주세요. 예를 들어 15가 입력된다면 4를 반환해 주면 됩니다. 풀이 #include using namespace std; int expressions(int testCase) { int answer = 0; int num = 1, temp = 0; for (int i = 1; i
문제 어떤 수 N(1≤N≤1,000,000) 이 주어졌을 때, N의 다음 큰 숫자는 다음과 같습니다. N의 다음 큰 숫자는 N을 2진수로 바꾸었을 때의 1의 개수와 같은 개수로 이루어진 수입니다. 1번째 조건을 만족하는 숫자들 중 N보다 큰 수 중에서 가장 작은 숫자를 찾아야 합니다. 예를 들어, 78을 2진수로 바꾸면 1001110 이며, 78의 다음 큰 숫자는 83으로 2진수는 1010011 입니다. N이 주어질 때, N의 다음 큰 숫자를 찾는 nextBigNumber 함수를 완성하세요. 풀이 무식하게 코딩한 방법이긴 한데.. 풀 당시 다른 사람들의 코드를 봐도 현재로선 더 좋은 방법이 떠오르지가 않는다.. 코드 자체는 워낙 쉬우니 간단하게 설명하면(너무 직관적이다..) 숫자를 2진수로 변환하고 1 ..
문제 효진이는 멀리 뛰기를 연습하고 있습니다. 효진이는 한번에 1칸, 또는 2칸을 뛸 수 있습니다. 칸이 총 4개 있을 때, 효진이는 (1칸, 1칸, 1칸, 1칸) (1칸, 2칸, 1칸) (1칸, 1칸, 2칸) (2칸, 1칸, 1칸) (2칸, 2칸) 5가지 방법으로 맨 끝 칸에 도달할 수 있습니다. 멀리뛰기에 사용될 칸의 수 n이 주어질 때, 효진이가 끝에 도달하는 방법이 몇 가지인지 출력하는 jumpCase 함수를 완성하세요. 예를 들어 4가 입력된다면, 5를 반환해 주면 됩니다. 풀이 1부터 경우의 수를 구해나가다 보면 규칙성을 찾을 수 있다. 개적화로 그럴싸한 코드를 만들 수 있지만 제출용 코드는 위와 같았다. 경우의 수를 따져보면 아래와 같다. n 1 2 3 4 5 6 … answer1 2 3 5..
