대구 달성공원에 놀러 온 지수는 최근에 새로 만든 타일 장식물을 보게 되었다. 타일 장식물은 정사각형 타일을 붙여 만든 형태였는데, 한 변이 1인 정사각형 타일부터 시작하여 마치 앵무조개의 나선 모양처럼 점점 큰 타일을 붙인 형태였다. 타일 장식물의 일부를 그리면 다음과 같다.
그림에서 타일에 적힌 수는 각 타일의 한 변의 길이를 나타낸다. 타일 장식물을 구성하는 정사각형 타일 한 변의 길이를 안쪽 타일부터 시작하여 차례로 적으면 다음과 같다. [1, 1, 2, 3, 5, 8, .] 지수는 문득 이러한 타일들로 구성되는 큰 직사각형의 둘레가 궁금해졌다. 예를 들어, 처음 다섯 개의 타일이 구성하는 직사각형(위에서 빨간색으로 표시한 직사각형)의 둘레는 26이다.
타일의 개수 N이 주어질 때, N개의 타일로 구성된 직사각형의 둘레를 return 하도록 solution 함수를 작성하시오.
제한 사항
N은 1 이상 80 이하인 자연수이다.
해결
전체 코드부터 보자
class Solution {
public long solution(int N) {
long answer = 0;
long n1 = 1;
long n2 = 1;
for(long i=0;i<N;i++){
answer = n1 + n2;
n1 = n2;
n2 = answer;
}
return answer * 2;
}
}
다음 직사각형의 한변의 길이는 현재와 이전의 타일 길이의 합이다. 이는 피보나치 수열과 흡사하다.
문제설명의 규칙을 보자 원하는 N개의 타일로 이루어진 직사각형의 짧은 변은 n1 긴 변은 n2의 피보나치 수로 이루어 져 있다.
N이 3인경우 n1은 2, n2는 3이다 즉 가로, 세로의 길이가 2, 3임으로 가로 세로의 합 * 2를 하면 둘레를 알 수 있다.
라디오를 자주 듣는 네오는 라디오에서 방금 나왔던 음악이 무슨 음악인지 궁금해질 때가 많다. 그럴 때 네오는 다음 포털의 '방금그곡' 서비스를 이용하곤 한다. 방금그곡에서는 TV, 라디오 등에서 나온 음악에 관해 제목 등의 정보를 제공하는 서비스이다.
네오는 자신이 기억한 멜로디를 가지고 방금그곡을 이용해 음악을 찾는다. 그런데 라디오 방송에서는 한 음악을 반복해서 재생할 때도 있어서 네오가 기억하고 있는 멜로디는 음악 끝부분과 처음 부분이 이어서 재생된 멜로디일 수도 있다. 반대로, 한 음악을 중간에 끊을 경우 원본 음악에는 네오가 기억한 멜로디가 들어있다 해도 그 곡이 네오가 들은 곡이 아닐 수도 있다. 그렇기 때문에 네오는 기억한 멜로디를 재생 시간과 제공된 악보를 직접 보면서 비교하려고 한다. 다음과 같은 가정을 할 때 네오가 찾으려는 음악의 제목을 구하여라.
방금그곡 서비스에서는 음악 제목, 재생이 시작되고 끝난 시각, 악보를 제공한다.
네오가 기억한 멜로디와 악보에 사용되는 음은 C, C#, D, D#, E, F, F#, G, G#, A, A#, B 12개이다.
각 음은 1분에 1개씩 재생된다. 음악은 반드시 처음부터 재생되며 음악 길이보다 재생된 시간이 길 때는 음악이 끊김 없이 처음부터 반복해서 재생된다. 음악 길이보다 재생된 시간이 짧을 때는 처음부터 재생 시간만큼만 재생된다.
음악이 00:00를 넘겨서까지 재생되는 일은 없다.
조건이 일치하는 음악이 여러 개일 때에는 라디오에서 재생된 시간이 제일 긴 음악 제목을 반환한다. 재생된 시간도 같을 경우 먼저 입력된 음악 제목을 반환한다.
조건이 일치하는 음악이 없을 때에는 `(None)`을 반환한다.
입력 형식
입력으로 네오가 기억한 멜로디를 담은 문자열 m과 방송된 곡의 정보를 담고 있는 배열 musicinfos가 주어진다.
m은 음 1개 이상 1439개 이하로 구성되어 있다.
musicinfos는 100개 이하의 곡 정보를 담고 있는 배열로, 각각의 곡 정보는 음악이 시작한 시각, 끝난 시각, 음악 제목, 악보 정보가 ','로 구분된 문자열이다.
음악의 시작 시각과 끝난 시각은 24시간 HH:MM 형식이다.
음악 제목은 ',' 이외의 출력 가능한 문자로 표현된 길이 1 이상 64 이하의 문자열이다.
악보 정보는 음 1개 이상 1439개 이하로 구성되어 있다.
출력 형식
조건과 일치하는 음악 제목을 출력한다.
해결
1. 문제 해석
시작시간, 종료시간, 제목, 멜로디 4가지 정보를 가지고 있는 문자열로 이루어진 배열과
사용자가 기억하고있는 멜로디를 가지고 사용자가 기억하는 노래의 제목을 찾는 문제이다.
2. 파싱
먼저 정보를 가지고있는 문자열을 파싱하여준다.
public String solution(String m, String[] musicinfos) {
String answer = "";
for (String s : musicinfos) {
String[] sArr = s.split(",");
String[] sttArr = sArr[0].split(":");
String[] edtArr = sArr[1].split(":");
int playHour = Integer.parseInt(edtArr[0]) - Integer.parseInt(sttArr[0]);
int playMin = Integer.parseInt(edtArr[1]) - Integer.parseInt(sttArr[1]) + (playHour * 60);
}
return answer;
}
문자열은 시작시간, 종료시간, 제목, 멜로디로 ","를 이용해 구분되어있다.
split(); 메서드를 이용해 소분 해준 뒤 시작시간, 종료시간을 구해준다.
시간 정보들은 시:분으로 구성되어있다. 이또한 split(); 를 이용해준다.
단 노래가 재생된 시간만큼 멜로디를 연산해야 하기때문에 parseInt를 이용해 Integer형으로 바꿔준다.
시간에 60을 곱해 분으로 바꿔준뒤 총 재생시간(분)을 구한다.
3. 재생된 멜로디구간 만들기
앞서 구한 총 재생시간으로 노래가 재생된 구간을 만들어 주는 매서드를 생성한다.
private String makeMusic(String s, int t) {
StringBuilder sb= new StringBuilder();
for (int i = 0; i < t; i++) {
sb.append(s.charAt(i % s.length()));
}
return sb.toString();
}
노래의 멜로디와 재생시간을 파라미터로 받아 시간만큼 재생된 멜로디를 문자열로 반환한다.
String music = makeMusic(sArr[3], playMin);
solution 메서드에 추가해준다.
4. 멜로디 검사
이제 사용자가 기억하는 멜로디 m과 만들어진 music을 비교해 찾는 노래가 맞는지 확인해야 한다.
if (music.contains(m)) {
if (maxPT < playMin) {
maxPT = playMin;
answer = sArr[2];
}
}
노래안에 해당 멜로디가 있으면 노래를 찾은것이다. 단 멜로디가 여러 노래에 포함 될 경우 가장 플레이타임이 긴 노래를 반환 해준다.
5. 까다로운 조건
노래의 음표에 반음이 포함되어있다. 지금껏 작성한 코드는 멜로디 및 노래에 "#"이 포함되지 않는다면 잘 작동한다.
하지만 "#"이 있을경우는 조금 문제가 생긴다.
예를들어 사용자가 기억한 멜로디가 "ABC" 노래가 "ABC#"이면 위 코드에서 contain 메소드가 true값을 반환 하지만
사실은 C와 C#은 완전히 다르다.
replaceAll메서드를 이용해 다른 문자로 변환하여 처리하자.
private String killSharp(String s) {
s = s.replaceAll("A#", "a");
s = s.replaceAll("C#", "c");
s = s.replaceAll("D#", "d");
s = s.replaceAll("F#", "f");
s = s.replaceAll("G#", "g");
return s;
}
"#"이 달린 음은 소문자로 처리를 해 준다.
노래와 멜로디 둘다 이러한 작업을 해 주면 정상 작동한다.
전체소스
class Solution {
public String solution(String m, String[] musicinfos) {
String answer = "'(None)'";
int maxPT = 0;
m = killSharp(m);
for (String s : musicinfos) {
s = killSharp(m);
String[] sArr = s.split(",");
String[] sttArr = sArr[0].split(":");
String[] edtArr = sArr[1].split(":");
int playHour = Integer.parseInt(edtArr[0]) - Integer.parseInt(sttArr[0]);
int playMin = Integer.parseInt(edtArr[1]) - Integer.parseInt(sttArr[1]) + (playHour * 60);
String music = makeMusic(sArr[3], playMin);
if (music.contains(m)) {
if (maxPT < playMin) {
maxPT = playMin;
answer = sArr[2];
}
}
}
return answer;
}
private String makeMusic(String s, int t) {
StringBuilder sb= new StringBuilder();
for (int i = 0; i < t; i++) {
sb.append(s.charAt(i % s.length()));
}
return sb.toString();
}
private String killSharp(String s) {
s = s.replaceAll("A#", "a");
s = s.replaceAll("C#", "c");
s = s.replaceAll("D#", "d");
s = s.replaceAll("F#", "f");
s = s.replaceAll("G#", "g");
return s;
}
}
무인도에 갇힌 사람들을 구명보트를 이용하여 구출하려고 합니다. 구명보트는 작아서 한 번에 최대 2명씩밖에 탈 수 없고, 무게 제한도 있습니다.
예를 들어, 사람들의 몸무게가 [70kg, 50kg, 80kg, 50kg]이고 구명보트의 무게 제한이 100kg이라면 2번째 사람과 4번째 사람은 같이 탈 수 있지만 1번째 사람과 3번째 사람의 무게의 합은 150kg이므로 구명보트의 무게 제한을 초과하여 같이 탈 수 없습니다.
구명보트를 최대한 적게 사용하여 모든 사람을 구출하려고 합니다.
사람들의 몸무게를 담은 배열 people과 구명보트의 무게 제한 limit가 매개변수로 주어질 때, 모든 사람을 구출하기 위해 필요한 구명보트 개수의 최솟값을 return 하도록 solution 함수를 작성해주세요.
제한사항
무인도에 갇힌 사람은 1명 이상 50,000명 이하입니다.
각 사람의 몸무게는 40kg 이상 240kg 이하입니다.
구명보트의 무게 제한은 40kg 이상 240kg 이하입니다.
구명보트의 무게 제한은 항상 사람들의 몸무게 중 최댓값보다 크게 주어지므로 사람들을 구출할 수 없는 경우는 없습니다.
해결
1. 문제분석
해당 문제는 최적의 해를 구하는 탐욕(greedy) 알고리즘 문제이다.
구명보트에 태울 수 있는 한 사람을 꽉꽉 채워 최소의 구명보트 개수를 구하는 문제이다.
2. 정렬
사람의 몸무게를 일일이 비교해가며 보트에 태워야 한다.
시간 복잡도를 줄이고 코드를 보기 편하게 짜기 위해 정렬을 해준다.
import java.util.Arrays;
class Solution {
public int solution(int[] people, int limit) {
int answer = 0;
Arrays.sort(people);
return answer;
}
}
자바 컬랙션인 "Arrays"의 정렬 메서드를 이용해 배열을 오름차순 정렬해준다.
3. 알고리즘
전체 소스 먼저 보자
import java.util.Arrays;
class Solution {
public int solution(int[] people, int limit) {
int answer = people.length;
Arrays.sort(people);
int l = 0;
int r = people.length-1;
while(l<r) {
if (people[l] + people[r] <= limit) l++;
r --;
}
return answer - l;
}
}
가장 무거운 사람부터 먼저 태운다고 생각하겠다.
가장 무거운 사람을 태운 뒤 빈자리를 가벼운 사람들로 채운다면 최소한의 보트 수로 무인도를 탈출할 수 있다. - (1)
배열의 시작과 끝 값을 각각 l, r로 본다.
반복문이 끝나는 시점은!(l <r) 즉 모든 사람이 보트에 타 무인도를 탈출하는 시점이다.
if (people[l] + people[r] <= limit) l++;
r--
가장 가벼운 사람과 가장 무거운 사람의 무게 합이 최대 수용 무게보다 낮으면 태운다.
그 뒤에 무거운 사람을 태운다. (1)의 말과는 이야기 흐름상 다르지만 비교 연산을 위한 것이다.
예를 들어 모든 사람 30명의 무게가 100kg이고 보트의 최대 수용 무게가 100kg인 경우 보트는 30대가 필요하다.
즉 보트에 사람을 1명 더 태울수록 필요한 보트의 개수가 1 줄어든다(l++).
줄어든 만큼 최악의 경우(answer = people.length)에서 추가로 태운 횟수(l)를 빼 준 뒤 값을 반환한다.
