알고리즘 Kata

77.

답안 :

class Solution {
	public int[] solution(String s) {
		int[] answer = new int[2];
		int cnt = 0;
		int zeroCnt = 0;
		while (!s.equals("1")) {
			for (int i = 0; i < s.length(); i++) {
				if (s.charAt(i) == '0') {
					zeroCnt++;
				}
			}
			s = s.replace("0", "");
			s = Integer.toBinaryString(s.length());
			cnt++;
		}
		answer[0] = cnt;
		answer[1] = zeroCnt;
		return answer;
	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Solution s = new Solution();
		String s1 = "110010101001";
		System.out.println(s.solution(s1));
	}
}

• 알고리즘 설명 :
  • 문자열 s가 "1" 의 형태가 됄때까지 반복
  • 해단 문자열의 "0"의 갯수를 센 후 "0"를 삭제 및 삭제한 길이를 2진수화 하여 다시반복.
  • 해당 반복을 반복문 종료까지 카운트 후 반환.

78.

답안 :

class Solution {
	public int solution(long n) {

        int answer = 0;
        int f0 = 0;
        int f1 = 1;
        int f2 = 1;

        for(int i=1; i<n; i++){
            f2 = (f0 + f1) % 1234567;
            f0 = f1;
            f1 = f2;
        }
        answer = f2;

        return (int) answer;
    }

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Solution s = new Solution();
		int n = 3;
		System.out.println(s.solution(n));
	}
}

• 알고리즘 설명 :
  • 피보나치수열의 특성을 활용하여 값을 구하되 수가 너무 커지지않게 문제의 조건인 N%1234567 의 값을 구하기 위해 계산단위마다 나눠줌.

틀린답안 :

class Solution {
	public int solution(int n) {
		if (n <= 1)
			return n;
		else
			return (solution(n - 1) + solution(n - 2))%1234567;
	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Solution s = new Solution();
		int n = 3;
		System.out.println(s.solution(n));
	}
}

• 결과적으론 틀린답안 보단 특성상 불가능에 가까운 답안이 맞는거같음.
• 재귀 함수에서는 동일한 함수를 계속해서 호출될 때마다 함수를 위한 메모리가 계속해서 할당된다. 함수가 호출될 때마다 사용되는 임시 저장 메모리를 스택이라고 부른다.
• 재귀 함수를 이용하다보면 함수가 종료되지 않고, 함수가 계속해서 호출이 되는데 이 경우 스택 공간이 초과되는 스택 오버플로(stack overfolw)가 발생하여 오류가 생긴다.
  
• 해당 오류때문에 문제에서 원하는 N>100,000 의 값은 구할수 없음
  참조 : https://bentist.tistory.com/57

SQL Kata

87.

• 직원중 보너스가 1,000 미만인 이름과 보너스 액수를 출력

답안 :

select e1.name, b1.bonus
from Employee e1 
left join Bonus b1
on e1.empId = b1.empId
where b1.bonus < 1000 or b1.bonus is null

• 각 테이블을 사용하며 NULL값도 이용해야기에 LeftJoin을 사용.
• 이후 where 절을 통해 조건을 정해주면된다

88.

• 해당 학생이 과목에대해 시험에 몇번 참석했는지에대해 출력

답안 :

select s1.student_id , s1.student_name ,s2.subject_name, count(e1.subject_name) as 'attended_exams'
from Students s1
cross join Subjects s2
left join Examinations e1
on e1.subject_name = s2.subject_name and s1.student_id = e1.student_id
group by 1,2,3
order by 1,3

• 해당과목의 시험을 보지 않은 학생도 포함해야기에 CROSS JOIN을 사용.
• 이후엔 그룹화와 정렬을 통해 출력을 해주면된다.
• 주로 leetcode 문제쪽엔 NULL 이라 0 처리에 관대한듯..