알고리즘 Kata

68.

답안 :

public class Solution {
	public int solution(int[] ingredient) {
		int answer = 0;
		StringBuffer sb = new StringBuffer();
		// 배열 String화
		for (int iteam : ingredient) {
			sb.append(iteam);
			// 버퍼의 크기가 3이상이면서 1231의 문자열이 완성되었을때.
			if (sb.length() > 3 && sb.subSequence(sb.length() - 4, sb.length()).equals("1231")) {
				answer++;
				//해당문자열을 삭제
				sb.delete(sb.length() - 4, sb.length());
			}
		}
		return answer;

	}

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

• 알고리즘 설명 : 해당 int 배열을 StringBuffer를 통해 문자열을 만들어가면서 '1231'이 완성되었을때 해당문자열을 지운다.

틀린답안 :

public class Solution {
	public int solution(int[] ingredient) {
		int answer = 0;
		StringBuffer sb = new StringBuffer();
		String buger = "1231";
		String s;
		for (int iteam : ingredient) {
			sb.append(iteam);
		}
		s = sb.toString();
		while (s.contains(buger)) {
			s=s.replaceFirst("1231", "");
			answer++;
		}
		return answer;

	}

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

• 처음에는 String을 이용하여 풀었지만 시간초과가 나옴. Stiring은 불변성을 지니기에 replace를 통해서 계속 새로운 리터럴이 만들어지기 때문에 시간초과가 발생. String의 연산은 O( N + K )

• 다른사람 답안 :

class Solution {
    public int solution(int[] ingredient) {
        int[] stack = new int[ingredient.length];
        int sp = 0;
        int answer = 0;
        for (int i : ingredient) {
            stack[sp++] = i;
            if (sp >= 4 && stack[sp - 1] == 1
                && stack[sp - 2] == 3
                && stack[sp - 3] == 2
                && stack[sp - 4] == 1) {
                sp -= 4;
                answer++;
            }
        }
        return answer;
    }
}

• 문자열이 아닌 배열을 통해서 풀이해본 답안.
• 배열내에서 '1231'이 완성될경우 해당 인덱스부터 다시 값을 덮어씌워서 시작. 이러면 기존의 재료를 재사용가능.

SQL Kata

73.

답안 :

WITH RECURSIVE cte (n) AS
(
  SELECT 0
  UNION ALL
  SELECT n + 1 FROM cte WHERE n < 23
)
SELECT n AS HOUR, COUNT(ANIMAL_ID)
FROM cte LEFT JOIN ANIMAL_OUTS ON n = HOUR(DATETIME)
GROUP BY n
ORDER BY n

• 다른사람의 정답을 많이참조했다..
• WITH RECURSIVE 를 통해 재귀적으로 돌아가면서 n이라는 이름의 변수로 0~23의 테이블을 생성
• 해당 테이블과 ANIMAL_OUTS 테이블을 join
• 이후 groupby를 통해 시간데이터가 없는 부분도 출력
• ANIMAL_ID 를 count 해 나머지 값 출력.

WITH RECURSIVE : 쿼리를 재귀적으로 사용하게 해주는 키워드, 코딩언어의 반복문 같은 느낌.
반드시 Union을 사용해 해당 반복문을 묶어줘야한다.