Slow And Steady Wins The Race

Entity에 다른 entity와 lazy loaded relationship이 있을 경우 hibernateLazyInitializer가 아래와 같이 포함된다.

"xx": {
        "id": 1,
        "hibernateLazyInitializer": {}
}

참조. https://stackoverflow.com/questions/18470438/exception-thrown-when-serializing-hibernate-object-to-json

When Hibernate loads objects from the DB, 
it returns proxied objects which look like your Advertisment or SessionT 
but have more "stuff" in them (to handle their relationship to the session, 
the internal state of lazy loaded collections etc.).

This throws off the Jackson serializer since it relies on introspection to find our the properties of the objects.

이때 jackson.serialization.FAIL_ON_EMPTY_BEANS가 true로 되어 있다면 에러가 발생한다.

No serializer found for class org.hibernate.proxy.pojo.bytebuddy.ByteBuddyInterceptor and no properties discovered to create BeanSerializer (to avoid exception, disable SerializationFeature.FAIL_ON_EMPTY_BEANS)

hibernateLazyInitializer를 무시한다던지 jackson.serialization.FAIL_ON_EMPTY_BEANS를 false로 설정하여 에러를 제거하는 방법도 있지만 근본적인 문제에 대해서 살펴보자.

Entity를 API에 노출하는 것이 과연 옳은 것일까?

한가지 장점이 있다. 매우 편하다..

하지만 그로인해 발생할 수 있는 문제점이 무엇이 있을까?

- 프레젠테이션 계층을 위한 로직이 Entity에 지속적으로 추가된다.(with @Transient)

고객이 항상 하는 이야기가 있다. 이것 추가해주세요.. 저것도 추가해주세요.. 

- API 검증을 위한 로직이 Entity에 지속적으로 추가된다.(@NotNull 등)

- 하나의 Entity가 다양한 API의 요구사항을 담기 어렵다.

- Entity가 변경되면 API도 변경되어야한다. 

결론은 프레젠테이션 영역으로 부터 전달받는 Request,
프레젠테이션으로 전달하는 Response를 따로 정의하자.

- https://stackoverflow.com/questions/18470438/exception-thrown-when-serializing-hibernate-object-to-json

알고리즘 종류 : 이진탐색

수찾기

문제

N개의 정수 A[1], A[2], …, A[N]이 주어져 있을 때, 이 안에 X라는 정수가 존재하는지 알아내는 프로그램을 작성하시오.

입력

첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들이 A안에 존재하는지 알아내면 된다. 모든 정수의 범위는 -231 보다 크거나 같고 231보다 작다.

출력

M개의 줄에 답을 출력한다. 존재하면 1을, 존재하지 않으면 0을 출력한다.

예제입력1

5
4 1 5 2 3
5
1 3 7 9 5

예제출력1

1
1
0
0
1

이진탐색으로 풀어보자.

import java.util.Arrays;
import java.util.Scanner;

public class Main {
	private int N;
	private int M;
	private final int MAX = 100010;
	private int[] numbers = new int[MAX];

	public static void main(String[] args) {
		Main main = new Main();
		try {
			main.start();
		} catch (Exception e) {
			e.printStackTrace();
		}
	}

	private void start() throws Exception {
		Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
		for (int i = 0; i < N; i++) numbers[i] = sc.nextInt();
		M = sc.nextInt();
		
		Arrays.sort(numbers, 0, N);
		for (int i = 0; i < M; i++) {
			int target = sc.nextInt();
			System.out.println(binarySearch(target) ? 1 : 0);
		}
	}

	private boolean binarySearch(int target) {
		boolean found = false;
		int s = 0, e = N - 1;
		while (s <= e) {
			int divide = (s + e) / 2;
			if (numbers[divide] == target) {
				found = true;
				break;
			} else if (numbers[divide] < target) {
				s = divide + 1;
			} else {
				e = divide - 1;
			}
		}
		return found;
	}
    
    private int binarySearchRecursive(int s, int e, int target) {
		if(s == e) {
			return numbers[s] == target ? s : -1;
		} else if (s > e) {
			return -1;
		}
		
		int mid = (s + e) / 2;
		if(numbers[mid] < target) {
			return binarySearch(mid+1, e, target);
		} else if(numbers[mid] > target){
			return binarySearch(s, mid-1, target);
		} else {
			return mid;
		}
	}
}

출처

- https://www.acmicpc.net/problem/1920

Collection Framework란?

데이터를 저장하는 자료 구조와 데이터를 처리하는 알고리즘을 구조화하여 클래수로 구현해 놓은 것

Collection Framework는 자바의 인터페이스(interface)를 사용하여 구현된다.

Collection Framework 주요 인터페이스

Collection 인터페이스

List와 Set 인터페이스의 많은 공통된 부분을 Collection 인터페이스에서 정의하고, 두 인터페이스는 그것을 상속받는다.

제공하는 주요 메소드는 아래와 같다.

메소드설명

Stack 메소드

Queue 메소드

Stack<Integer> st = new Stack<>();
st.push(1);
st.push(2);
System.out.println(st.peek()); // 2
st.pop();
System.out.println(st.peek()); // 1
st.pop();
System.out.println(st.empty());

System.out.println("===========");

Queue<Integer> q = new LinkedList<>();
q.add(1);
q.add(2);
System.out.println(q.peek()); // 1
q.remove();
System.out.println(q.peek()); // 2

- http://www.tcpschool.com/java/java_collectionFramework_concept

- https://www.javatpoint.com/collections-in-java

알고리즘 종류 : 백트랙킹

부등호

문제

두 종류의 부등호 기호 ‘<’와 ‘>’가 k개 나열된 순서열 A가 있다. 우리는 이 부등호 기호 앞뒤에 서로 다른 한 자릿수 숫자를 넣어서 모든 부등호 관계를 만족시키려고 한다. 예를 들어, 제시된 부등호 순서열 A가 다음과 같다고 하자.

A ⇒ < < < > < < > < >

부등호 기호 앞뒤에 넣을 수 있는 숫자는 0부터 9까지의 정수이며 선택된 숫자는 모두 달라야 한다. 아래는 부등호 순서열 A를 만족시키는 한 예이다. 

3 < 4 < 5 < 6 > 1 < 2 < 8 > 7 < 9 > 0

이 상황에서 부등호 기호를 제거한 뒤, 숫자를 모두 붙이면 하나의 수를 만들 수 있는데 이 수를 주어진 부등호 관계를 만족시키는 정수라고 한다. 그런데 주어진 부등호 관계를 만족하는 정수는 하나 이상 존재한다. 예를 들어 3456128790 뿐만 아니라 5689023174도 아래와 같이 부등호 관계 A를 만족시킨다. 

5 < 6 < 8 < 9 > 0 < 2 < 3 > 1 < 7 > 4

여러분은 제시된 k개의 부등호 순서를 만족하는 (k+1)자리의 정수 중에서 최댓값과 최솟값을 찾아야 한다. 앞서 설명한 대로 각 부등호의 앞뒤에 들어가는 숫자는 { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }중에서 선택해야 하며 선택된 숫자는 모두 달라야 한다. 

입력

첫 줄에 부등호 문자의 개수를 나타내는 정수 k가 주어진다. 그 다음 줄에는 k개의 부등호 기호가 하나의 공백을 두고 한 줄에 모두 제시된다. k의 범위는 2 ≤ k ≤ 9 이다. 

출력

여러분은 제시된 부등호 관계를 만족하는 k+1 자리의 최대, 최소 정수를 첫째 줄과 둘째 줄에 각각 출력해야 한다. 단 아래 예(1)과 같이 첫 자리가 0인 경우도 정수에 포함되어야 한다. 모든 입력에 답은 항상 존재하며 출력 정수는 하나의 문자열이 되도록 해야 한다. 

예제 입력 1

2
< >

예제 출력 1

897
021

예제 입력 2

9
> < < < > > > < <

예제 출력 2

9567843012
1023765489

출처

Olympiad > 한국정보올림피아드 > 한국정보올림피아드시․도지역본선 > 지역본선 2012 > 초등부 5번

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;

public class Main {
	private final int N = 10;
	private Integer k;
	private String[] opts = new String[N];
	private Boolean[] visited = new Boolean[N];
	private List<String> result = new ArrayList<>();

	public static void main(String[] args) throws Exception {
		Main main = new Main();
		main.start();
	}

	private void isValidTest() {
		System.out.println(isValid(1, 2, ">"));
	}

	private void start() throws Exception {
		Arrays.fill(visited, false);
		//System.setIn(new FileInputStream("src/test/input.txt"));
		Scanner sc = new Scanner(System.in);
		k = sc.nextInt();
		for (int i = 0; i < k; i++) {
			opts[i] = sc.next();
			// System.out.println(opts[i]);
		}
		
		backTracking(-1, -1, "");
		Collections.sort(result);
	
		
		System.out.println(result.get(result.size()-1));
		System.out.println(result.get(0));
	}

	private void backTracking(int prev, int optIdx, String numStr) {
		if (optIdx >= k) {
			result.add(numStr);
			return;
		}
		for (int i = 0; i <= 9; i++) {
			if (!visited[i] && (optIdx == -1 || isValid(prev, i, opts[optIdx]))) {
				visited[i] = true;
				backTracking(i, optIdx + 1, numStr + i);
				visited[i] = false;
			}
		}
	}

	private Boolean isValid(int a, int b, String opt) {
		return opt.equals("<") ? a < b : a > b;
	}
}

출처

- https://www.acmicpc.net/problem/2529