우박수 (Hailstone Sequence) 이란
우박수 수열이란 만약 Hailstone()함수에 어떠한 수 n을 대입했을때,
\( n ㅡ> n/2 \) (n이 짝수)
\( n ㅡ> 3n+1 \) (n이 홀수)
if \( n = 5 \),
출력 : [5, 16, 8, 4, 2, 1]
라는 과정을 통해 결국에는 마지막 숫자는 1이 된다는 추측입니다
우박수 수열을 콜라츠 추측(Collatz Conjecture)이라고도 합니다
이와같은 우박수 수열을 코드로 나타낸다면 아래와 같을 것 입니다
public static void main(String[] args) {
int n = 5;
while (n != 1) {
System.out.println(n);
if (n % 2 == 0) {
n = n/2;
}
else {
n = 3*n + 1;
}
}
System.out.println(n);
}
문제 1 : Max 우박수 수열
위에서 우박수 수열에 대해서 배웠습니다. 그럼 maxHailstone(5)를 입력했을 때, 모든 숫자가 아닌 최고값만을 출력하는 알고리즘을 구하세요 (int 값 반환)
Test cases:
System.out.println(maxHailstone(5)); ㅡ> 16
System.out.println(maxHailstone(7)); ㅡ> 52
Answer:
public static int maxhailstone(int n) {
int tmp = n;
while (n != 1) {
if (n % 2 == 0) {
n = n/2;
}
else {
n = 3*n + 1;
}
if(tmp < n) {
tmp = n;
}
}
return tmp;
}
문제 2 : 희귀 char
공백이 아닌 문자열이 입력될때, 문자열에서 단 한 번만 나타나는 문자중 첫번째 문자가 출력됩니다. 해당 문자가 없다면 newline 문자를 반환하는 알고리즘을 구하세요 (char값 반환)
Test cases :
System.out.print(appearOnce("aabc")); ㅡ> b
System.out.print(appearOnce("aabbc")); ㅡ> c
System.out.print(appearOnce("aabbcc")); ㅡ>
Answer:
public static char appearOnce(String input){
for(int i = 0; i < input.length(); i++) {
String s = Character.toString(input.charAt(i));
String s_end = input.substring(i+1, input.length());
String start_s = input.substring(0, i);
if(i == 0) {
if(s_end.contains(s)) {
continue;
}else {return input.charAt(i);}
}else {
if(s_end.contains(s) || start_s.contains(s)) {
continue;
}else {return input.charAt(i);}
}
}
return '\n';
}
문제 3 : 윤년은 언제야?
임의의 년도가 입력값으로 들어왔을때, 입력 년도가 윤년인지 아닌지 구분하는 알고리즘을 구하세요(boolean 반환)
Test cases :
System.out.println(isLeapYear(2020)); ㅡ> true
System.out.println(isLeapYear(2022)); ㅡ> false
윤년이란 4년에 한번씩 양력 2월이 29일까지 있는 해를 말한다. 그러니까 1년이 365일이 아니라 366일이다
Answer :
public static boolean isLeapYear(int year) {
boolean output = false;
if(year %4 == 0) {
output = true;
}
if(year % 4 == 0 && year % 100 == 0) {
output = false;
}
if(year % 4 == 0 && year % 100 == 0 && year % 400 == 0) {
output = true;
}
return output;
}생각보다 너무 간단한데? 라고 느끼실 수 있는데, 윤년은 4로 나누어 진다는 규칙뿐만 아니라, 4와 100으로 나누어 진다면 윤년이 되지 않고, 4, 100 그리고 400으로 나누어지면 윤년이 된다는 규칙이 있습니다. 이점을 유의하셔야합니다
문제 4 : concat
concat() 함수는 비어있지 않은 두 문자열 source와 target 입력값을 받습니다. 이때 source가 target문자열을 포함하기위해 기존 source문자열에 자기 자신을 반복해서 합칩니다. 이때 몇번 반복하는지 반복값을 반환하는 알고리즘을 구하세요 * target을 포함하는게 불가능하다면 -1를 리턴합니다 (int값 반환)
Test cases :
System.out.println(concatContain("ab", "baba")); ㅡ> 2
System.out.println(concatContain("ab", "ab")); ㅡ> 0
System.out.println(concatContain("abbb", "bababa")); ㅡ> -1
Answer :
public static int concatContain(String source, String target) {
int times = 0;
for(int i = 0; i < target.length(); i++) {
if(source.contains(Character.toString(target.charAt(i)))) {
continue;
}else {
return -1;
}
}
while(true) {
if(source.length() > target.length()*2) {
return -1;
}
if(source.contains(target)) {
break;
}
source = source + source;
times ++;
}
return times;
}
참조
Xian Liverpool University Professor Erick Purwanto's learning materials