소수 만들기
📑 문1) 주어진 숫자 중 3개의 수를 더했을 때 소수가 되는 경우의 개수를 구하려고 합니다. 숫자들이 들어있는 배열 nums가 매개변수로 주어질 때, nums에 있는 숫자들 중 서로 다른 3개를 골라 더했을 때 소수가 되는 경우의 개수를 return 하도록 solution 함수를 완성해주세요.
제한사항
- nums에 들어있는 숫자의 개수는 3개 이상 50개 이하입니다.
- nums의 각 원소는 1 이상 1,000 이하의 자연수이며, 중복된 숫자가 들어있지 않습니다.
입출력 예
| nums | result |
|---|---|
[1,2,3,4] | 1 |
[1,2,7,6,4] | 4 |
입출력 예 설명
입출력 예 #1
[1,2,4]를 이용해서 7을 만들 수 있습니다.
입출력 예 #2
[1,2,4]를 이용해서 7을 만들 수 있습니다.
[1,4,6]을 이용해서 11을 만들 수 있습니다.
[2,4,7]을 이용해서 13을 만들 수 있습니다.
[4,6,7]을 이용해서 17을 만들 수 있습니다.
나의 풀이
package programmers;
public class PrimeNumber {
public static int solution(int[] nums) {
int answer = 0;
for(int i = 0; i < nums.length -2; i++) {
for(int j = i + 1; j < nums.length - 1; j++) {
for(int k = j + 1; k < nums.length; k++) {
System.out.println(nums[i] + nums[j] + nums[k]);
if(isPrime(nums[i] + nums[j] + nums[k])) {
answer += 1;
}
}
}
}
return answer ;
}
public static Boolean isPrime(int num) {
if (num < 2) return false;
for(int i = 2; i <= (int)Math.sqrt(num); i++) {
if(num % i == 0) {
return false;
}
}
return true;
}
public static void main(String[] args) {
solution(new int[] {1,2,3,4});
}
}
나의 생각
for(int i = 0; i < nums.length -2; i++) {
for(int j = i + 1; j < nums.length - 1; j++) {
for(int k = j + 1; k < nums.length; k++) {
if(isPrime(nums[i] + nums[j] + nums[k])) {
answer += 1;
}
}
}
}먼저, 중첩 for문을 통해 배열의 세 가지 수를 모든 경우를 조합하는 로직을 구현하였다. 예를들어, {1,2,3,4}가 있다고 할때, 첫 번째 for문 루프는 배열의 인덱스 i를 배열의 길이 -2까지 반복하고 이 때 i는 첫 번째 선택한 숫자의 위치를 나타낸다. 두 번째 for 루프는 배열의 인덱스 j를 i+1부터 배열의 길이 -1 까지 반복하는데, j는 두 번쨰 선택한 숫자의 위치를 나타낸다. 이렇게 설정하면 같은 숫자를 두 번 선택하는 것을 방지할 수 있다.예를들어, 첫 번째 숫자로 1을 선택했을 때(i = 0), 두 번째 숫자는 2또는 3또는4(j=1,2,3) 중 하나를 선택할 수 있다. 세 번째 for 루프는 배열의 인덱스k를 j+1부터 배열의 끝까지 반복하는데, k는 세 번째 선택한 숫자의 위치를 나타낸다.
public static Boolean isPrime(int num) {
if (num < 2) return false;
for(int i = 2; i <= (int)Math.sqrt(num); i++) {
if(num % i == 0) {
return false;
}
}
return true;
}isPrime 메서드는 주어진 정수 num이 소수인지 아닌지 판별하는 로직이다.
먼저, if (num < 2) retrun false;는, 2보다 작은 모든 수는 소수가 아니므로 이를 검사한다. 그 다음, 2부터 num의 제곱근까지 반복하는데 , 소수를 판별하는데 있어서, 특정 수의 약수가 존재한다면 그 약수는 반드시 그 수의 제곱근 이하에 존재하기 떄문에 이를 이용하면 시간 복잡도를 크게 줄일 수 있다. 그리고 소수는 1과 자기 자신 외에는 어떠한 수로도 나누어 떨어지지 않는 수이기 때문에, if(num % i == 0)에서 나누어 떨어진다면, 소수가 아님을 의미하며 return false를 반환한다. 최종적으로, for 루프가 종료되고, num이 어떤 수로도 나누어 떨어지지 않는다면, num은 소수이므로 true를 반환한다.
소수 찾기
📑 문2) 1부터 입력받은 숫자 n 사이에 있는 소수의 개수를 반환하는 함수, solution을 만들어 보세요.
소수는 1과 자기 자신으로만 나누어지는 수를 의미합니다.
(1은 소수가 아닙니다.)
제한조건
- n은 2이상 1000000이하의 자연수입니다.
입출력 예
| n | result |
|---|---|
| 10 | 4 |
| 5 | 3 |
입출력 예 설명
입출력 예 #1
- 1부터 10 사이의 소수는
[2,3,5,7]4개가 존재하므로 4를 반환
입출력 예 #2
- 1부터 5사이의 소수는
[2,3,5]3개가 존재하므로 3를 반환
나의 풀이
package programmers;
public class FindPrime {
public static int solution(int n) {
int primeCnt = 0;
for(int i = 2; i <= n; i++) {
boolean isPrime = true;
for(int j = 2; j*j <= i; j++) {
if(i % j == 0) {
isPrime = false;
break;
}
}
if (isPrime) {
primeCnt++;
}
}
return primeCnt;
}
public static void main(String[] args) {
solution(10);
}
}
나의 생각
카드 뭉치
📑 문3) 코니는 영어 단어가 적힌 카드 뭉치 두 개를 선물로 받았습니다. 코니는 다음과 같은 규칙으로 카드에 적힌 단어들을 사용해 원하는 순서의 단어 배열을 만들 수 있는지 알고 싶습니다.
- 원하는 카드 뭉치에서 카드를 순서대로 한 장씩 사용합니다.
- 한 번 사용한 카드는 다시 사용할 수 없습니다.
- 카드를 사용하지 않고 다음 카드로 넘어갈 수 없습니다.
- 기존에 주어진 카드 뭉치의 단어 순서는 바꿀 수 없습니다.
예를 들어 첫 번째 카드 뭉치에 순서대로 ["i", "drink", "water"], 두 번째 카드 뭉치에 순서대로 ["want", "to"]가 적혀있을 때 ["i", "want", "to", "drink", "water"] 순서의 단어 배열을 만들려고 한다면 첫 번째 카드 뭉치에서 "i"를 사용한 후 두 번째 카드 뭉치에서 "want"와 "to"를 사용하고 첫 번째 카드뭉치에 "drink"와 "water"를 차례대로 사용하면 원하는 순서의 단어 배열을 만들 수 있습니다.
문자열로 이루어진 배열 cards1, cards2와 원하는 단어 배열 goal이 매개변수로 주어질 때, cards1과 cards2에 적힌 단어들로 goal를 만들 있다면 "Yes"를, 만들 수 없다면 "No"를 return하는 solution 함수를 완성해주세요.
제한사항
- 1 ≤ cards1의 길이, cards2의 길이 ≤ 10
- 1 ≤ cards1[i]의 길이, cards2[i]의 길이 ≤ 10
- cards1과 cards2에는 서로 다른 단어만 존재합니다.
- 2 ≤ goal의 길이 ≤ cards1의 길이 + cards2의 길이
- 1 ≤ goal[i]의 길이 ≤ 10
- goal의 원소는 cards1과 cards2의 원소들로만 이루어져 있습니다.
- cards1, cards2, goal의 문자열들은 모두 알파벳 소문자로만 이루어져 있습니다.
입출력 예
| cards1 | cards2 | goal | result |
|---|---|---|---|
["i", "drink", "water"] | ["want", "to"] | ["i", "want", "to", "drink", "water"] | "Yes" |
["i", "water", "drink"] | ["want", "to"] | ["i", "want", "to", "drink", "water"] | "No" |
입출력 예 설명
입출력 예 #2
cards1에서 "i"를 사용하고 cards2에서 "want"와 "to"를 사용하여 "i want to"까지는 만들 수 있지만 "water"가 "drink"보다 먼저 사용되어야 하기 때문에 해당 문장을 완성시킬 수 없습니다. 따라서 "No"를 반환합니다.
나의 풀이
package programmers;
public class DeckOfCards {
public static String solution(String[] cards1, String[] cards2, String[] goal) {
int pointer1 = 0;
int pointer2 = 0;
for (String goalWord : goal) {
if (pointer1 < cards1.length && goalWord.equals(cards1[pointer1])) {
pointer1++;
} else if (pointer2 < cards2.length && goalWord.equals(cards2[pointer2])) {
pointer2++;
} else {
return "No";
}
}
return "Yes";
}
public static void main(String[] args) {
solution(new String[] {"i","drink","water"}, new String[] {"want","to"},
new String[] {"i","want","to","drink","water"});
}
}
완주하지 못한 선수
📑 문4) 수많은 마라톤 선수들이 마라톤에 참여하였습니다. 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다.
마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수들의 이름이 담긴 배열 completion이 주어질 때, 완주하지 못한 선수의 이름을 return 하도록 solution 함수를 작성해주세요.
제한사항
- 마라톤 경기에 참여한 선수의 수는 1명 이상 100,000명 이하입니다.
- completion의 길이는 participant의 길이보다 1 작습니다.
- 참가자의 이름은 1개 이상 20개 이하의 알파벳 소문자로 이루어져 있습니다.
- 참가자 중에는 동명이인이 있을 수 있습니다.
입출력 예
| participant | completion |
|---|---|
["leo", "kiki", "eden"] | ["eden", "kiki"] |
["marina", "josipa", "nikola", "vinko", "filipa"] | ["josipa", "filipa", "marina", "nikola" |
["mislav", "stanko", "mislav", "ana"] | ["stanko", "ana", "mislav"] |
입출력 예 설명
예제 #1
"leo"는 참여자 명단에는 있지만, 완주자 명단에는 없기 때문에 완주하지 못했습니다.
예제 #2
"vinko"는 참여자 명단에는 있지만, 완주자 명단에는 없기 때문에 완주하지 못했습니다.
예제 #3
"mislav"는 참여자 명단에는 두 명이 있지만, 완주자 명단에는 한 명밖에 없기 때문에 한명은 완주하지 못했습니다.
나의 풀이
효율성 검증 실패
package programmers;
import java.util.ArrayList;
public class AthletesWhoDidNotFinish {
public static String solution(String[] participant, String[] completion) {
ArrayList<String> list = new ArrayList<>();
for(String str : participant) {
list.add(str);
}
for(int i = 0; i < completion.length; i++) {
if(list.contains(completion[i])) {
list.remove(completion[i]);
}
}
return list.get(0);
}
public static void main(String[] args) {
solution(new String[] {"mislav", "stanko", "mislav", "ana"}, new String[] {"stanko", "ana", "mislav"});
}
}
hashMap 풀이
Map<String, Integer> map = new HashMap<>();
for(String player : participant) {
map.put(player, map.getOrDefault(player, 0) + 1);
}
for(String player : completion) {
map.put(player, map.get(player) -1);
}
for (String key : map.keySet()) {
if (map.get(key) != 0){
return key;
}
}
return "";나의 생각
- 참가자 목록을 map에 추가
- 첫번째 for-each 문에서는 참가자 배열을 순회하며 각 선수를 key로, 그 선수가 몇 번 등장하는지를 value로 Map에 저장,
map.getOrDefault(player,0)메서드는 Map에 player key가 존재하면 해당 key의 value를 반환하고, 존재하지 않으면 0을 반환, 따라서map.put(player, map.getOrDefault(player, 0) + 1)코드는 특정 선수가 이미 map에 있는 경우, 그 선수의 등장 횟수를 1 증가시키고, 선수가 map에 없는 경우, 새로운 key - value 쌍(player, 1)을 map에 추가
- 완주자 목록을 이용하여 map 업데이트
- 두 번째 for-each 문에서는 완주한 선수(completion)배열을 순회하며, 완주한 선수의 이름에 해당하는 key의 value를 1 감소시킴, 왜냐하면 그 선수가 완주했으므로, 완주하지 못한 선수를 찾기 위해선 해당 선수를 map에서 제거해야하기 때문
- 완주하지 못한 선수 찾기
- 마지막 for-each문에서는 map의 모든 key를 순회하며 value를 확인, 만약 어떤 key(선수이름)에 대응하는 value가 0이 아니라면, 그 선수는 참가자 목록에는 있지만 완주자 목록에는 없다는 뜻이므로 완주하지 못한 선수가 된다. 이 경우, 해당 Key를 반환하여 완주하지 못한 선수의 이름을 알려주는것
체육복
📑 문5) 점심시간에 도둑이 들어, 일부 학생이 체육복을 도난당했습니다. 다행히 여벌 체육복이 있는 학생이 이들에게 체육복을 빌려주려 합니다. 학생들의 번호는 체격 순으로 매겨져 있어, 바로 앞번호의 학생이나 바로 뒷번호의 학생에게만 체육복을 빌려줄 수 있습니다. 예를 들어, 4번 학생은 3번 학생이나 5번 학생에게만 체육복을 빌려줄 수 있습니다. 체육복이 없으면 수업을 들을 수 없기 때문에 체육복을 적절히 빌려 최대한 많은 학생이 체육수업을 들어야 합니다.
전체 학생의 수 n, 체육복을 도난당한 학생들의 번호가 담긴 배열 lost, 여벌의 체육복을 가져온 학생들의 번호가 담긴 배열 reserve가 매개변수로 주어질 때, 체육수업을 들을 수 있는 학생의 최댓값을 return 하도록 solution 함수를 작성해주세요.
제한사항
- 전체 학생의 수는 2명 이상 30명 이하입니다.
- 체육복을 도난당한 학생의 수는 1명 이상 n명 이하이고 중복되는 번호는 없습니다.
- 여벌의 체육복을 가져온 학생의 수는 1명 이상 n명 이하이고 중복되는 번호는 없습니다.
- 여벌 체육복이 있는 학생만 다른 학생에게 체육복을 빌려줄 수 있습니다.
- 여벌 체육복을 가져온 학생이 체육복을 도난당했을 수 있습니다. 이때 이 학생은 체육복을 하나만 도난당했다고 가정하며, 남은 체육복이 하나이기에 다른 학생에게는 체육복을 빌려줄 수 없습니다.
입출력 예
| n | lost | reserve | return |
|---|---|---|---|
| 5 | [2, 4] | [1, 3, 5] | 5 |
| 5 | [2, 4] | [3] | 4 |
| 3 | [3] | [1] | 2 |
입출력 예 설명
예제 #1
1번 학생이 2번 학생에게 체육복을 빌려주고, 3번 학생이나 5번 학생이 4번 학생에게 체육복을 빌려주면 학생 5명이 체육수업을 들을 수 있습니다.
예제 #2
3번 학생이 2번 학생이나 4번 학생에게 체육복을 빌려주면 학생 4명이 체육수업을 들을 수 있습니다.
나의 풀이
package programmers;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Iterator;
import java.util.List;
public class Sportswear {
public static int solution(int n, int[] lost, int[] reserve) {
List<Integer> lostList = new ArrayList<>();
List<Integer> reserveList = new ArrayList<>();
for(int a : lost) {
lostList.add(a);
}
for (int r : reserve) {
reserveList.add(r);
}
Collections.sort(lostList);
Collections.sort(reserveList);
Iterator<Integer> reserveIterator = reserveList.iterator();
while(reserveIterator.hasNext()) {
int student = reserveIterator.next();
if(lostList.contains(student)) {
lostList.remove((Integer)student);
reserveIterator.remove();
}
}
reserveIterator = reserveList.iterator();
while (reserveIterator.hasNext()) {
int student = reserveIterator.next();
if (lostList.contains(student - 1)) {
lostList.remove((Integer) (student - 1));
reserveIterator.remove();
continue;
}
if (lostList.contains(student + 1)) {
lostList.remove((Integer) (student + 1));
reserveIterator.remove();
}
}
return n - lostList.size();
}
public static void main(String[] args) {
solution(5, new int[] {2,4}, new int[] {1,3,5});
}
}
나의 생각
해당 로직은 체육복을 잃어버렸지만 여분이 있는 학생들이 있어서 체육복을 빌려줄 수 있는 상황에서 최대한 많은 학생이 체육수업을 들을 수 있드록 하는 로직을 구현한 것이다.
Iterator<Integer> 를 쓰는 이유는 ?
- 여분의 체육복을 가진 학생 목록(
reserveList)을 순회하면서 동시에 목록의 항목을 안전하게 삭제하기 위해 사용함. - Java의
List인터페이스를 구현하는 컬렉션 클래스에서는for루프 또는for-each루프를 사용하여 요소를 순회할 수 있지만, 이러한 방식으로 순회하면서 리스트에서 요소를 삭제하려고 하면ConcurrentModificationException이 발생할 수 있기 때문에 이를 방지하기 위해서임
만약 체육복을 잃어버린 학생이 여분의 체육복을 가지고 있다면
해당 경우, 체육복을 잃어버렸지만 여분의 체육복이 있는 학생은 다른 학생에게 체육복을 빌려줄 수 없음
reserveIterator = reserveList.iterator()를 재선언하는 이유는?
Iterator는 컬렉션의 요소를 한 번만 순회한다. 따라서reserveList를 두 번 순회해야 하는 경우가 발생한다. ( 첫 번째 순회에서는 체육복을 잃어버린 학생이 자신의 여분 체육복을 사용하는 경우를 처리하고, 두 번째 순회에서는 여분의 체육복을 가진 학생이 다른 학생에게 체육복을 빌려주는 경우를 처리한다) 따라서 두 번째 순회를 시작하기 전에 새로운Iterator를 생성
reserveIterator = reserveList.iterator();
while (reserveIterator.hasNext()) {
int student = reserveIterator.next();
if (lostList.contains(student - 1)) {
lostList.remove((Integer) (student - 1));
reserveIterator.remove();
continue;
}
if (lostList.contains(student + 1)) {
lostList.remove((Integer) (student + 1));
reserveIterator.remove();
}
}여분의 체육복이 있는 학생이 체육복을 잃어버린 학생의 앞 번호나 뒷 번호의 학생에게 체육복을 빌려줄 수 있는지 확인, 체육복을 빌려줄 수 있다면, 해당 학생을 lostList에서 제거하고, 체육복을 빌려준 학생을 reserveList에서 제거
