1. K번째수
: 배열 array의 i번째 숫자부터 j번째 숫자까지 자르고 정렬했을 때, k번째에 있는 수를 구하려 합니다.
예를 들어 array가 [1, 5, 2, 6, 3, 7, 4], i = 2, j = 5, k = 3이라면
array의 2번째부터 5번째까지 자르면 [5, 2, 6, 3]입니다.
1에서 나온 배열을 정렬하면 [2, 3, 5, 6]입니다.
2에서 나온 배열의 3번째 숫자는 5입니다.
배열 array, [i, j, k]를 원소로 가진 2차원 배열 commands가 매개변수로 주어질 때, commands의 모든 원소에 대해 앞서 설명한 연산을 적용했을 때 나온 결과를 배열에 담아 return 하도록 solution 함수를 작성해주세요.
제한사항
array의 길이는 1 이상 100 이하입니다.
array의 각 원소는 1 이상 100 이하입니다.
commands의 길이는 1 이상 50 이하입니다.
commands의 각 원소는 길이가 3입니다.
[문제 풀이 고민]
i번째에서 j 번째 까지 배열을 자르고, 자른 배열에서 k 번째 숫자를 출력
1. 2차원 배열에서 i,j,k를 먼저 빼냄
2. 빼낸 i,j,k를 적용하여 첫번째 숫자를 출력
import java.util.*;
class Solution {
public int[] solution(int[] array, int[][] commands) {
int[] answer = new int[commands.length];
for(int a = 0; a < commands.length; a++){
int i = commands[a][0];
int j = commands[a][1];
int k = commands[a][2] - 1;
int position = j - i + 1;
int c = 0;
int[] arr1 = new int[position];
for(int b = i - 1; b < j; b++){
arr1[c] = array[b];
c++;
}
Arrays.sort(arr1);
answer[a] = arr1[k];
}
return answer;
}
}[다른 사람 코드]
- Arrays.copyOfRange() : 특정 범위 배열 복사
=> Arrays.copyOfRange(원본 배열,복사하려는 시작 요소의 인덱스,복사하려는 마지막 요소의 인덱스의 바로 다음 인덱스)
import java.util.Arrays;
class Solution {
public int[] solution(int[] array, int[][] commands) {
int[] answer = new int[commands.length];
for(int i=0; i<commands.length; i++){
int[] temp = Arrays.copyOfRange(array, commands[i][0]-1, commands[i][1]);
Arrays.sort(temp);
answer[i] = temp[commands[i][2]-1];
}
return answer;
}
}2. 크기가 작은 부분문자열
: 숫자로 이루어진 문자열 t와 p가 주어질 때, t에서 p와 길이가 같은 부분문자열 중에서, 이 부분문자열이 나타내는 수가 p가 나타내는 수보다 작거나 같은 것이 나오는 횟수를 return하는 함수 solution을 완성하세요.
예를 들어, t="3141592"이고 p="271" 인 경우, t의 길이가 3인 부분 문자열은 314, 141, 415, 159, 592입니다. 이 문자열이 나타내는 수 중 271보다 작거나 같은 수는 141, 159 2개 입니다.
제한사항
1 ≤ p의 길이 ≤ 18
p의 길이 ≤ t의 길이 ≤ 10,000
t와 p는 숫자로만 이루어진 문자열이며, 0으로 시작하지 않습니다.
[문제 풀이 고민]
1. p의 문자열의 갯수 만큼 잘라서 배열에 넣기
2. 배열에서 p와 수를 비교
1)
입력값 〉 "10203", "15"
기댓값 〉 3
에서 3을 출력하는 문제가 발생
import java.util.*;
class Solution {
public int solution(String t, String p) {
int answer = 0;
int number = Integer.parseInt(p);
ArrayList<String> arr = new ArrayList<>();
int len = p.length();
for(int i = 0; i < t.length(); i += len){
if(i + len > t.length()){
arr.add(t.substring(i, t.length()));
}
else{
arr.add(t.substring(i, i + len));
}
}
for(int i = 0; i < arr.size(); i++){
if(!arr.get(i).equals("") && Integer.parseInt(arr.get(i)) <= number){
answer++;
}
}
return answer;
}
}2)런타임 에러 발생
import java.util.*;
class Solution {
public int solution(String t, String p) {
int answer = 0;
int number = Integer.parseInt(p);
ArrayList<String> arr = new ArrayList<>();
if (t.length() < p.length()) {
arr.add(t);
} else {
for (int i = 0; i <= t.length() - p.length(); i++) {
arr.add(t.substring(i, i + p.length()));
}
}
for (String s : arr) {
if (Integer.parseInt(s) <= number) {
answer++;
}
}
return answer;
}
}3) 제출 코드
- int 보다 long이 허용 범위가 높기때문에 변경
- arraylist로 하나하나 잘라서 저장을 삭제
- 자른 부분에서 바로 수 확인 후 카운트로 들어감
import java.util.*;
class Solution {
public int solution(String t, String p) {
int answer = 0;
Long number = Long.parseLong(p);
int len = p.length();
for (int i = 0; i < t.length() - len + 1; i++) {
long diff = Long.parseLong(t.substring(i, i + len));
if (diff <= number) answer++;
}
return answer;
}
}3. 구명보트
: 무인도에 갇힌 사람들을 구명보트를 이용하여 구출하려고 합니다. 구명보트는 작아서 한 번에 최대 2명씩 밖에 탈 수 없고, 무게 제한도 있습니다.
예를 들어, 사람들의 몸무게가 [70kg, 50kg, 80kg, 50kg]이고 구명보트의 무게 제한이 100kg이라면 2번째 사람과 4번째 사람은 같이 탈 수 있지만 1번째 사람과 3번째 사람의 무게의 합은 150kg이므로 구명보트의 무게 제한을 초과하여 같이 탈 수 없습니다.
구명보트를 최대한 적게 사용하여 모든 사람을 구출하려고 합니다.
사람들의 몸무게를 담은 배열 people과 구명보트의 무게 제한 limit가 매개변수로 주어질 때, 모든 사람을 구출하기 위해 필요한 구명보트 개수의 최솟값을 return 하도록 solution 함수를 작성해주세요.
제한사항
무인도에 갇힌 사람은 1명 이상 50,000명 이하입니다.
각 사람의 몸무게는 40kg 이상 240kg 이하입니다.
구명보트의 무게 제한은 40kg 이상 240kg 이하입니다.
구명보트의 무게 제한은 항상 사람들의 몸무게 중 최댓값보다 크게 주어지므로 사람들을 구출할 수 없는 경우는 없습니다.
[문제 풀이 고민]
구명 보트에는 한번에 2명이 최대 인원
구명 보트 개수의 최소값을 출력하면 됨
1)
- 하나씩 확인 후 짝이 없던 것을 확인후 짝이 있는 것을 길이에서 뺀 형태
- 몇몇 테스트 케이스에서 실패하게 됨 => 최소값을 출력하지 못하는게 문제일듯
- 여러번 경우의 수가 되는 경우도 포함이 되어버림
class Solution {
public int solution(int[] people, int limit) {
int answer = 0;
for(int i = 0; i < people.length; i++){
for(int j = i + 1; j < people.length; j++){
if(people[i] + people[j] <= limit){
answer ++;
}
}
}
answer = people.length - answer;
return answer;
}
}2) 제출 코드
- 먼저 배열을 오름차순으로 재정렬
- 가장 작은 무게와 가장 큰 무게의 합부터 확인
- 한번 더 탈 수 없는 상황을 만듬
import java.util.*;
class Solution {
public int solution(int[] people, int limit) {
int answer = 0;
Arrays.sort(people);
int left = 0;
int right = people.length - 1;
while(left <= right){
if(people[left] + people[right] <= limit){
left ++;
}
right --;
answer ++;
}
return answer;
}
}4. 예상 대진표
: △△ 게임대회가 개최되었습니다. 이 대회는 N명이 참가하고, 토너먼트 형식으로 진행됩니다. N명의 참가자는 각각 1부터 N번을 차례대로 배정받습니다. 그리고, 1번↔2번, 3번↔4번, ... , N-1번↔N번의 참가자끼리 게임을 진행합니다. 각 게임에서 이긴 사람은 다음 라운드에 진출할 수 있습니다. 이때, 다음 라운드에 진출할 참가자의 번호는 다시 1번부터 N/2번을 차례대로 배정받습니다. 만약 1번↔2번 끼리 겨루는 게임에서 2번이 승리했다면 다음 라운드에서 1번을 부여받고, 3번↔4번에서 겨루는 게임에서 3번이 승리했다면 다음 라운드에서 2번을 부여받게 됩니다. 게임은 최종 한 명이 남을 때까지 진행됩니다.
이때, 처음 라운드에서 A번을 가진 참가자는 경쟁자로 생각하는 B번 참가자와 몇 번째 라운드에서 만나는지 궁금해졌습니다. 게임 참가자 수 N, 참가자 번호 A, 경쟁자 번호 B가 함수 solution의 매개변수로 주어질 때, 처음 라운드에서 A번을 가진 참가자는 경쟁자로 생각하는 B번 참가자와 몇 번째 라운드에서 만나는지 return 하는 solution 함수를 완성해 주세요. 단, A번 참가자와 B번 참가자는 서로 붙게 되기 전까지 항상 이긴다고 가정합니다.
제한사항
N : 21 이상 220 이하인 자연수 (2의 지수 승으로 주어지므로 부전승은 발생하지 않습니다.)
A, B : N 이하인 자연수 (단, A ≠ B 입니다.)
[문제 풀이 고민]
1. 서로 이길때 마다 /2를 해서 대결하는 라운드를 계산
class Solution
{
public int solution(int n, int a, int b)
{
int answer = 0;
// [실행] 버튼을 누르면 출력 값을 볼 수 있습니다.
System.out.println("Hello Java");
//서로 만날때까지 반복
while(a != b){
a = (a + 1) / 2; //다음 라운드
b = (b + 1) / 2;
answer ++;
}
return answer;
}
}