영어 끝말잇기
📑 문1) 1부터 n까지 번호가 붙어있는 n명의 사람이 영어 끝말잇기를 하고 있습니다. 영어 끝말잇기는 다음과 같은 규칙으로 진행됩니다.
- 1번부터 번호 순서대로 한 사람씩 차례대로 단어를 말합니다.
- 마지막 사람이 단어를 말한 다음에는 다시 1번부터 시작합니다.
- 앞사람이 말한 단어의 마지막 문자로 시작하는 단어를 말해야 합니다.
- 이전에 등장했던 단어는 사용할 수 없습니다.
- 한 글자인 단어는 인정되지 않습니다.
다음은 3명이 끝말잇기를 하는 상황을 나타냅니다.
tank → kick → know → wheel → land → dream → mother → robot → tank
위 끝말잇기는 다음과 같이 진행됩니다.
- 1번 사람이 자신의 첫 번째 차례에 tank를 말합니다.
- 2번 사람이 자신의 첫 번째 차례에 kick을 말합니다.
- 3번 사람이 자신의 첫 번째 차례에 know를 말합니다.
- 1번 사람이 자신의 두 번째 차례에 wheel을 말합니다.
- (계속 진행)
끝말잇기를 계속 진행해 나가다 보면, 3번 사람이 자신의 세 번째 차례에 말한 tank 라는 단어는 이전에 등장했던 단어이므로 탈락하게 됩니다.
사람의 수 n과 사람들이 순서대로 말한 단어 words 가 매개변수로 주어질 때, 가장 먼저 탈락하는 사람의 번호와 그 사람이 자신의 몇 번째 차례에 탈락하는지를 구해서 return 하도록 solution 함수를 완성해주세요.
제한 사항
- 끝말잇기에 참여하는 사람의 수 n은 2 이상 10 이하의 자연수입니다.
- words는 끝말잇기에 사용한 단어들이 순서대로 들어있는 배열이며, 길이는 n 이상 100 이하입니다.
- 단어의 길이는 2 이상 50 이하입니다.
- 모든 단어는 알파벳 소문자로만 이루어져 있습니다.
- 끝말잇기에 사용되는 단어의 뜻(의미)은 신경 쓰지 않으셔도 됩니다.
- 정답은 [ 번호, 차례 ] 형태로 return 해주세요.
- 만약 주어진 단어들로 탈락자가 생기지 않는다면, [0, 0]을 return 해주세요.
입출력 예
| n | words | result |
|---|---|---|
| 3 | ["tank", "kick", "know", "wheel", "land", "dream", "mother", "robot", "tank"] | [3,3] |
| 5 | ["hello", "observe", "effect", "take", "either", "recognize", "encourage", "ensure", "establish", "hang", "gather", "refer", "reference", "estimate", "executive"] | [0,0] |
| 2 | ["hello", "one", "even", "never", "now", "world", "draw"] | [1,3] |
나의 풀이
package programmers;
import java.util.HashSet;
public class EnglishEnding {
public static int[] solution(int n, String[] words) {
HashSet<String> wordSet = new HashSet<>();
String prevWord = words[0];
wordSet.add(prevWord);
for (int i = 1; i < words.length; i++) {
if (prevWord.charAt(prevWord.length() - 1) != words[i].charAt(0) || wordSet.contains(words[i])) {
return new int[] {(i % n) + 1, (i / n) + 1};
}
wordSet.add(words[i]);
prevWord = words[i];
}
return new int[] {0, 0};
}
public static void main(String[] args) {
solution(5, new String[] {"hello", "observe", "effect", "take", "either", "recognize", "encourage", "ensure", "establish", "hang", "gather", "refer", "reference", "estimate", "executive"});
}
}
나의 생각
처음에는 Map으로 key 1,2,3,4... ,value: 끝말잇기 내용을 넣고 map에서 값을 추출해서 로직을 구현할려고 해보았다. 하지만, 알고리즘 특성상, 시간복잡도 나 메모리 쓰임이 중요하기 때문에, 이를 즉각적으로 판별할 수 있게 로직을 재구현하였다.
HashSet<String> wordSet = new HashSet<>();
String prevWord = words[0];
wordSet.add(prevWord);
for (int i = 1; i < words.length; i++) {
if (prevWord.charAt(prevWord.length() - 1) != words[i].charAt(0) || wordSet.contains(words[i])) {
return new int[] {(i % n) + 1, (i / n) + 1};
}
wordSet.add(words[i]);
prevWord = words[i];
}핵심 로직을 보면 prevWord에 words[0] 를 넣고, 중복값을 제거 해주는 wordSet에 prevWord를 넣는다. 그리고 for문 순회를 통해, prevWord의 끝문자와 words[1] 부터 시작 글자, set에 든 중복값을 비교하여 해당 로직에 들어가면 가장 먼저 탈락하는 사람의 번호와 그 사람이 자신의 몇번째 차례에 탈락하는지를 담은 int형 배열을 리터한다.
구명보트
📑 문2) 무인도에 갇힌 사람들을 구명보트를 이용하여 구출하려고 합니다. 구명보트는 작아서 한 번에 최대 2명씩 밖에 탈 수 없고, 무게 제한도 있습니다.
예를 들어, 사람들의 몸무게가 [70kg, 50kg, 80kg, 50kg]이고 구명보트의 무게 제한이 100kg이라면 2번째 사람과 4번째 사람은 같이 탈 수 있지만 1번째 사람과 3번째 사람의 무게의 합은 150kg이므로 구명보트의 무게 제한을 초과하여 같이 탈 수 없습니다.
구명보트를 최대한 적게 사용하여 모든 사람을 구출하려고 합니다.
사람들의 몸무게를 담은 배열 people과 구명보트의 무게 제한 limit가 매개변수로 주어질 때, 모든 사람을 구출하기 위해 필요한 구명보트 개수의 최솟값을 return 하도록 solution 함수를 작성해주세요.
제한사항
- 무인도에 갇힌 사람은 1명 이상 50,000명 이하입니다.
- 각 사람의 몸무게는 40kg 이상 240kg 이하입니다.
- 구명보트의 무게 제한은 40kg 이상 240kg 이하입니다.
- 구명보트의 무게 제한은 항상 사람들의 몸무게 중 최댓값보다 크게 주어지므로 사람들을 구출할 수 없는 경우는 없습니다.
입출력 예
| people | limit | return |
|---|---|---|
[70,50,80,50] | 100 | 3 |
[70,80,50] | 100 | 3 |
나의 풀이
package programmers;
import java.util.Arrays;
public class Lifeboat {
public static int solution(int[] people, int limit) {
Arrays.sort(people);
int answer = 0;
System.out.println(Arrays.toString(people));
int start = 0;
int end = people.length - 1;
while(start <= end) {
if(people[start] + people[end] <= limit) {
start++;
}
end--;
answer++;
}
return answer;
}
public static void main(String[] args) {
solution(new int[] {70, 50, 80, 50}, 100);
}
}
나의 생각
먼저 몸무게 순으로 오름차순으로 정렬을 한다. 내가 생각했던 로직의 구현 방식은 오름차순으로 정렬한 값 가벼운 순서와 무거운 순서 (즉, 배열값의 첫번째값과 마지막값) 대로 중간으로 순서가 이동하게 하는 방법을 사용하였다.
점프와 순간 이동
📑 문3) OO 연구소는 한 번에 K 칸을 앞으로 점프하거나, (현재까지 온 거리) x 2 에 해당하는 위치로 순간이동을 할 수 있는 특수한 기능을 가진 아이언 슈트를 개발하여 판매하고 있습니다. 이 아이언 슈트는 건전지로 작동되는데, 순간이동을 하면 건전지 사용량이 줄지 않지만, 앞으로 K 칸을 점프하면 K 만큼의 건전지 사용량이 듭니다. 그러므로 아이언 슈트를 착용하고 이동할 때는 순간 이동을 하는 것이 더 효율적입니다. 아이언 슈트 구매자는 아이언 슈트를 착용하고 거리가 N 만큼 떨어져 있는 장소로 가려고 합니다. 단, 건전지 사용량을 줄이기 위해 점프로 이동하는 것은 최소로 하려고 합니다. 아이언 슈트 구매자가 이동하려는 거리 N이 주어졌을 때, 사용해야 하는 건전지 사용량의 최솟값을 return하는 solution 함수를 만들어 주세요.
예를 들어 거리가 5만큼 떨어져 있는 장소로 가려고 합니다.
아이언 슈트를 입고 거리가 5만큼 떨어져 있는 장소로 갈 수 있는 경우의 수는 여러 가지입니다.
- 처음 위치 0 에서 5 칸을 앞으로 점프하면 바로 도착하지만, 건전지 사용량이 5 만큼 듭니다.
- 처음 위치 0 에서 2 칸을 앞으로 점프한 다음 순간이동 하면 (현재까지 온 거리 : 2) x 2에 해당하는 위치로 이동할 수 있으므로 위치 4로 이동합니다. 이때 1 칸을 앞으로 점프하면 도착하므로 건전지 사용량이 3 만큼 듭니다.
- 처음 위치 0 에서 1 칸을 앞으로 점프한 다음 순간이동 하면 (현재까지 온 거리 : 1) x 2에 해당하는 위치로 이동할 수 있으므로 위치 2로 이동됩니다. 이때 다시 순간이동 하면 (현재까지 온 거리 : 2) x 2 만큼 이동할 수 있으므로 위치 4로 이동합니다. 이때 1 칸을 앞으로 점프하면 도착하므로 건전지 사용량이 2 만큼 듭니다.
위의 3가지 경우 거리가 5만큼 떨어져 있는 장소로 가기 위해서 3번째 경우가 건전지 사용량이 가장 적으므로 답은 2가 됩니다.
제한 사항
- 숫자 N: 1 이상 10억 이하의 자연수
- 숫자 K: 1 이상의 자연수
입출력 예
| N | result |
|---|---|
| 5 | 2 |
| 6 | 2 |
| 5000 | 5 |
나의 풀이
ackage programmers;
public class JumpAndTeleport {
public static int solution(int n) {
int charge = 0;
while(n > 0) {
if(n % 2 ==0) {
n /= 2;
}else {
n--;
charge++;
}
}
return charge;
}
public static void main(String[] args) {
solution(10000);
}
}
나의 생각
먼저 문제에서 주어진 조건을 보면서 최소한의 충전으로 갈 목적지까지 갈 때의 최소 충천횟수를 리턴하는 문제를 구현하는게 목표이다. 내가 생각했을때의 최소한의 충전으로 목적지(N)까지 가기 위해서는 최소 0 -> 1 -> 1*2 => 2 와 같이 해당 하는 순서까지는 무조건 충전을 1회를 해야한다. 최대한 충전없이 이동하기 위해서는 해당 위치 * 2 으로 순간이동할 때 충전을 하지 않기때문에 나는 이런 현상을 기반으로 다음과 같이 생각하였다. 먼저, 10000을 예로 들어 보자.
10000 → 5000 → 2500 → 1250 → 625 → 624 → 312 → 156 → 78 → 39 → 38 → 19 → 18 → 9 → 8 → 4 → 2 → 1 →0 위 풀이 방법에서, /2 를 했을때, 나머지가 1인 경우 위의 식에서 625는 2로 나누었을 때 나머지가 1이기때문에 625 -1 = 624로 만들어 계속해서 2로 나누고, 최종적으로는 n = 0이 될때까지 반복을 하여, n -1을 하는 경우에만 charge++하는 방법을 사용하였다.
while(n > 0) {
if(n % 2 ==0) {
n /= 2;
}else {
n--;
charge++;
}
}해당 로직을 보면 알 수 있듯이, n % 2 == 0인 경우, n /= 2로 n값을 반감시키고, 그렇지않는 경우, n--로 n을 2로 나누었을 때 0이 되도록 맞춰주는 동시에, charge 변수를 올리는 방법을 생각하였다.
예상 대진표
📑 문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 : 2^1 이상 2^22 이하인 자연수 (2의 지수 승으로 주어지므로 부전승은 발생하지 않습니다.)
A, B : N 이하인 자연수 (단, A ≠ B 입니다.)
입출력 예
| N | A | B | answer |
|---|---|---|---|
| 8 | 4 | 7 | 3 |
입출력 예 설명
첫 번째 라운드에서 4번 참가자는 3번 참가자와 붙게 되고, 7번 참가자는 8번 참가자와 붙게 됩니다. 항상 이긴다고 가정했으므로 4번 참가자는 다음 라운드에서 2번이 되고, 7번 참가자는 4번이 됩니다. 두 번째 라운드에서 2번은 1번과 붙게 되고, 4번은 3번과 붙게 됩니다. 항상 이긴다고 가정했으므로 2번은 다음 라운드에서 1번이 되고, 4번은 2번이 됩니다. 세 번째 라운드에서 1번과 2번으로 두 참가자가 붙게 되므로 3을 return 하면 됩니다.
나의 풀이
잘못된 풀이
package programmers;
public class Matchup {
public static int solution(int n, int a, int b){
int round = 1;
while(n > 0) {
System.out.println("N: " + n);
System.out.println("Round: " + round);
System.out.println("");
if(a % 2 == 0) {
a /= 2;
}
else {
a /= 2;
a++;
}
if(b % 2 == 0) {
b /= 2;
}
else {
b /= 2;
b++;
}
n /= 2;
round++;
if(a == 1 && b == 2) {
break;
}
}
System.out.println(round);
return round;
}
public static void main(String[] args) {
solution(1024, 1, 2);
}
}
나의 생각 (수정된 코드 포함)
먼저, 생각하지 못한 문제점에 대해서 설명하겠다.
- 조건의 문제:
if(a == 1 && b == 2)
- a와 b가 항상 이 값으로 수렴한다고 가정할수 없다 → 예를들어, a와 b가 처음부터 1과 2라면 첫 라운드에서 바로 만날것이다.
- n의 사용
- while문에서
n을 줄이는 방식으로 진행하는데, 문제에서 주어진n은 총 참가자 수를 나타내므로 이를 기준으로 로직을 진행하는것은 적절하지 않다. 대신 a와 b가 값이 같아지는지를 기준으로 loop를 종료하면된다.
- round의 증가
- 현재 로직에서는 while문이 종료된 후에 round를 반환한다. 그러나 a와 b가 같아질 때 round값을 이미 1 증가시켜버리므로 실제는 a와 b가 만난 round보다 1이 큰 값을 반환한다.
package programmers;
public class Matchup {
public static int solution(int n, int a, int b){
int round = 0;
while (a != b) {
a = a % 2 == 0 ? a / 2 : (a / 2) + 1;
b = b % 2 == 0 ? b / 2 : (b / 2) + 1;
round++;
}
System.out.println(round);
return round;
}
public static void main(String[] args) {
solution(1024, 1, 2);
}
}
클린 코드 작성 풀이
package programmers;
public class Matchup {
public static int solution(int n, int a, int b){
int round = 0;
while (a != b) {
a = (a + 1) / 2;
b = (b + 1) / 2;
round++;
}
return round;
}
public static void main(String[] args) {
solution(1024, 100, 999);
}
}
나의 생각
while문의 조건을 n이 아니라 a와 b가 같아지는 조건으로 명확성을 주었다.
| 바꾸기 전 코드 | 바꾸고 난 코드 |
|---|---|
 |  |
바뀌기 전 코드도 문제를 푸는것엔 문제가 없다. 하지만 더 간단하게 이를 표현할 방법이 있기에 while문 내용을 수정하였다. 예를들면, a = 1또는 2라고 가정하자.
- a = 1일 경우, ( 1 + 1 ) / 2 = 1
- a = 2일 경우, ( 2 + 1) / 2 = 1
즉, int형인 경우, 소숫점은 제거되기 때문에 a = 1일 때 나오는 1은 1로 , a = 2일 때 나오는 1.5 역시 결과는 1로 나오기때문에, 이 방법을 사용하면 불필요한 if문을 제거할 수 있다.
N개의 최소공배수
📑 문5) 두 수의 최소공배수(Least Common Multiple)란 입력된 두 수의 배수 중 공통이 되는 가장 작은 숫자를 의미합니다. 예를 들어 2와 7의 최소공배수는 14가 됩니다. 정의를 확장해서, n개의 수의 최소공배수는 n 개의 수들의 배수 중 공통이 되는 가장 작은 숫자가 됩니다. n개의 숫자를 담은 배열 arr이 입력되었을 때 이 수들의 최소공배수를 반환하는 함수, solution을 완성해 주세요.
제한 사항
- arr은 길이 1이상, 15이하인 배열입니다.
- arr의 원소는 100 이하인 자연수입니다.
입출력 예
| arr | result |
|---|---|
| [2,6,8,14] | 168 |
| [1,2,3] | 6 |
나의 풀이
package programmers;
public class LeastCommonMultiple {
private static int gcd(int a, int b) {
while(b != 0) {
int temp = a % b;
a = b;
b = temp;
}
return a;
}
private static int lcm(int a, int b) {
return a * b / gcd(a,b);
}
public static int solution(int[] arr) {
int answer = arr[0];
for(int i = 1; i < arr.length; i++) {
answer = lcm(answer, arr[i]);
}
return answer;
}
public static void main(String[] args) {
solution(new int[] {2,6,8,14});
}
}
나의 생각
- 유클리드 호제법을 이용하여 GCD(최대공약수) , LCM(최소공배수)를 구할 수 있는데,
유클리드 호제법의 기본 원리는 다음과 같다.
- 두 정수 a와 b (여기서 a > b)의 최대공약수는 b와 a%b(a를 b로 나눈 나머지)의 최대공약수와 같다는 것
이 방법의 특징은 큰 두 수의 최대공약수를 더 작은 수들의 최대공약수로 줄여나가는 것이다.
유클리드 호제법의 알고리즘
a와b중에서 더 큰 수를a로 하고, 작은 수를b로 한다.a를b로 나눈 나머지를r이라고 하면,r이0이면b가 최대공약수이다.r이0이 아니라면a에b의 값을 넣고,b에는r의 값을 넣은 다음, 2번 과정을 반복한다.
최대공약수(GCD)를 구하는 방법
- 유클리드 호제법은 다음과 같은 점화식을 사용한다.
gcd(a,b) = gcd(b, a % b)
그리고 b가 0이면 a가 최대공약수가 된다.
public static int gcd(int a, int b) {
while (b != 0) {
int temp = a % b;
a = b;
b = temp;
}
return a;
}최소공배수(LCM)를 구하는 방법
- 두 수의 최소공배수는 다음과 같이 표현된다.
lcm(a, b) = (a * b) / gcd(a, b)
public static int lcm(int a, int b) {
return (a * b) / gcd(a, b);
}
