골드에그

1. 문제요약

코딩테스트 연습 - 표현 가능한 이진트리 | 프로그래머스 스쿨 (programmers.co.kr)

아래 과정을 수행해서 만들어지는 숫자를 포화 이진 트리로 표현 가능한 숫자라고 가정한다.

1. 이진수를 저장할 빈 문자열을 생성합니다.
2. 주어진 이진트리에 더미 노드를 추가하여 포화 이진트리로 만듭니다. 루트 노드는 그대로 유지합니다.
3. 만들어진 포화 이진트리의 노드들을 가장 왼쪽 노드부터 가장 오른쪽 노드까지, 왼쪽에 있는 순서대로 살펴봅니다. 노드의 높이는 살펴보는 순서에 영향을 끼치지 않습니다.
4. 살펴본 노드가 더미 노드라면, 문자열 뒤에 0을 추가합니다. 살펴본 노드가 더미 노드가 아니라면, 문자열 뒤에 1을 추가합니다.
5. 문자열에 저장된 이진수를 십진수로 변환합니다.

반대로 숫자가 주어질 때, 포화 이진 트리로 표현 가능한지 구하시오.

2. 문제예제

문제 지문에 잘 나와있으므로 생략한다.

3. 팩트추출

Fact 1 : 문제에서 이야기하는 표현 가능한 이진트리는 트리 중앙에 있는 부모 노드의 값이 항상 있어야 한다는 특징을 가지고 있다. 그래서 중앙에 값이 있는지 체크하기 위해 포화 이진 트리 크기로 배열을 늘리고 중앙에 값이 있는지 재귀로 호출하면서 체크해야 한다. 전체 과정을 수행하기 위한 처리 루틴은 다음과 같다.

1. 숫자를 이진수로 바꾸었을 때, 이진수 자릿수를 구한다.
2. 이진수 자릿수를 포화 이진 트리 노드의 갯수만큼 늘린다.
3. 늘린 자릿수만큼 배열을 할당하고, 남은 앞 부분은 0 더미로 채운다.
4. 재귀로 호출하면서 트리의 서브트리 중앙 노드 값들을 값이 있는지 체크한다.

Fact 2 : 이진수로 표현했을 때 자릿수를 구하려면 중학교 때 배운 기수법과 로그의 성질을 이해해야 한다.

최종 m 번째 숫자가 결국 n 진법으로 나타냈을 때 자릿수와 같다. m * (n 진법 ^ m-1)

이 m 을 구하기 위해 log 를 활용하면 logn(10진수 숫자) + 1 이 된다. 

Fact 3 : 이진수 자릿수를 포화 이진 트리 노드의 갯수만큼 늘리려면 포화 이진 트리 노드의 갯수 공식을 알아야 한다.

트리 높이에 따라 포화 이진 트리 노드의 갯수를 구해보면 1, 3, 7, 15 ... 와 같은 수열임을 확인할 수있고, 이는  2^n-1 인 수식으로 표현이 가능하다. 즉, 이진수 자릿수보다 같거나 한 단계 큰 포화 이진 트리 노드의 갯수를 구하면 된다.

4. 문제전략

Fact 2 + Fact 3 공식과 DFS 로 트리를 절반씩 순회하면서 중앙에 있는 값이 0 인지 체크하면 된다. 

5. 소스코드

class Solution {
    public int treeLength;
    public int result;
    
    public void validateBinaryTree(boolean[] target, int start, int end, boolean isEnd) {
        int mid = (start + end) / 2;
        boolean current = target[mid];
        if (isEnd && current) {
            result = 0;
            return;
        }
        if (start != end) {
            validateBinaryTree(target, start, mid-1, !current);
            validateBinaryTree(target, mid+1, end, !current);
        }
    }

    private boolean[] makeTarget(long number) {
        int binaryLength = (int) Math.floor(Math.log(number) / Math.log(2)) + 1;

        int treeHeight = 1;
        treeLength = 0;
        while (treeLength < binaryLength) {
            treeLength = (int) Math.pow(2, treeHeight++) - 1;
        }

        boolean[] target = new boolean[treeLength];
        int i = treeLength - 1;
        while(true) {
            long div = number / 2;
            long mod = number % 2;
            number = div;
            target[i--] = (mod == 1);
            if (div == 1) {
                target[i] = true;
                break;
            } else if (div == 0) {
                break;
            }
        }
        return target;
    }
    public int[] solution(long[] numbers) {
        int[] answer = new int[numbers.length];
        for (int i = 0; i < numbers.length ; i++) {
            result = 1;
            boolean[] target = makeTarget(numbers[i]);
            validateBinaryTree(target, 0, treeLength-1, false);
            answer[i] = result;
        }
        return answer;
    }
}

요구사항 1 : 이미지의 height 값을 계산하자.

f1 함수에서 height 값을 계산하도록 img.height 형태로 로직을 수정해보면, 정확한 값이 계산되지 않는다. 0 이 출력된다.

url 속성과 다르게 height 속성은 객체가 로드가 될 때 제대로 계산이 될 수 있기 때문이다. onLoad 속성의 이벤트(오브젝트가 로드되었을 때 발생하는 이벤트)를 사용해서 객체가 로드될 때 계산이 되도록 변경한다.

=>

const loadImage = url => {
    let img = new Image();
    img.src = url;
    img.onload = () => {
        console.log(img.height);
    }
    return img;
};
loadImage(imgs[0].url);

요구사항 2 : 이미지의 height 값을 외부로 반환하는 함수로 만들자.

onLoad 속성은 이벤트다. 오브젝트가 로드되었을 때 발생하는 이벤트로 내부 표현식에 있는 변수들을 외부로 반환하기 위해서는 onLoad 이벤트가 발생할 때까지 기다려야 한다. 순차적으로 실행되지 않고 어떤 특정 시점에 호출되는 함수 내부에 있는 변수들을 반환해야 하므로 Promise 객체를 반환하도록 변경한다.

=> 

const loadImage = url => new Promise(resolve => {
    let img = new Image();
    img.src = url;
    img.onload = () => {
    	resolve(img);
	}
});
// loadImage(imgs[0].url).then(img => console.log(img.height));

요구사항 3 : 이미지 리스트들을 순회하면서 height 값을 출력하자.

image url 이 주어졌을 때 height 값을 구하는 함수를 만들었으니 리스트들을 순회하면서 map 으로 해당 함수를 호출하여 일대일 변환해보자.

=>

// 실패코드
function f() {
    imgs
    .map(({url}) => loadImage(url))
    .map(img => img.height)
    .forEach(a => console.log(a));
}

이렇게 구현하면 loadImage 가 Promise 를 반환하기 때문에 다음 구문들도 Promise 를 인자로 받아 실행이 된다.

이 때 Promise 객체에서는 없는 속성(여기서는 height 값) 을 참조하므로 undefined 가 최종적으로 반환된다. 결과 값을 기다려야 하므로 loadImage 함수를 await 지시어를 사용해 기다리고, await 을 사용했으니 function 에는 async 가 붙는다.

그런데 이 async 함수에서 반환하는 값은 또 Promise 이므로 다음 구문에서도 계속해서 Promise 를 사용하기 위해 async-await 구문을 사용해야 한다. async-await 구문 지옥. 일단 해당 함수를 패치해서 기능 구현은 정상적으로 해두었다.

=>

function f() {
	imgs
    .map(async ({url}) => {
        const img = await loadImage(url);
        return img.height;
    })
    .forEach(async a => console.log(await a));
}

요구사항 4 : 이미지 리스트들을 순회하면서 총 height 값을 구해보자.

이미지 리스트들의 height 값을 더해 총 height 값을 구현해야 하는 요구사항이 추가되었다. 단순히 출력하는 코드를 수정해 reduce 기능을 활용한다.

=>

async function f() {
    const total = await imgs
        .map(async ({url}) => {
            const img = await loadImage(url);
            return img.height;
        })
        .reduce(async (total, height) => await total + await height, 0);
	console.log(total);
}

더 심각해졌다. 내부에 있는 async-await 구문들이 외부까지 전파가 된 모습이다. 합계를 출력해야 되기 때문에 함수 내부에 total 변수를 생성하였는데 async 구문 안에서 사용하므로 await 을 통해 결과 값을 기다려주어야 한다. await 을 붙였으니 async 가 붙을테고 Promise 가 계속 전파되어버린다.

리팩토링 1 : 제너레이터와 코드 분리를 통해 자주 사용하는 로직을 관심사 분리한다.

리팩토링 1-1 : map 을 Promise 객체가 와도 컨트롤 할 수 있게 변경하자.

Promise 가 오면 then 과 함수를 합성해서 반환하고 일반 객체가 오면 그 객체를 함수 호출해서 그대로 반환한다. 원조 map 은 Iterable 한 객체를 인자로 받아서 가공하고 하나씩 결과 값을 방출하는 Generator 이다.(Iterator 의 특수한 형태) 새롭게 만들 map 도 Generator 형태로 만들면 된다.

=>

function* map(f, iter) {
    for (const a of iter) {
        yield a instanceof Promise ? a.then(f) : f(a);
    }
}

리팩토링 1-2 : reduce 함수도 Promise 객체를 컨트롤 할 수 있는 비동기 버전을 만든다.

인자들이 Promise 이면 계속해서 모든 인자들을 await 을 붙여 신경 써주어야 하고 함수 자체를 async 하게 만들어야 하므로 map 과 똑같이 비동기 버전을 만들 필요가 있다. 다만, map 과 다른 점은 Promise 를 반환할 일이 없기 때문에 제너레이터 성격이 아닌 이터레이터만 만들면 되므로 굳이 then 과 합성할 필요가 없다.

=>

async function reduceAsync(f, acc, iter) {
    for await (const a of iter) {
        acc = f(acc, a);
    }
    return acc;
}

만들어 둔 두 가지 함수로 리팩토링하면 아래와 같이 간결해진다.

async function f(imgs) {
    return await reduceAsync((a, b) => a + b, 0,
                map(img => img.height,
                map(({url}) => loadImage(url), imgs)));
}

어차피 이 코드도 Promise 를 반환하기 때문에 async 와 await 을 없애도 된다.

const f = (imgs) => 
	reduceAsync((a, b) => a + b, 0,
    	map(img => img.height,
        	map(({url}) => loadImage(url), imgs)));

만약에 여기서 img 중 하나가 잘못된 img 라면 어떻게 될까? 어떻게 에러 핸들링을 해야 깔끔한 코드가 될까?

정답은 이 코드 바깥에서 예외처리 한 번만 해주는 것이다. 이 함수 내부에서 어떻게든 처리하려고 하면 에러가 숨게 되고 못 찾을 가능성이 있다.

불필요하게 에러 핸들링을 미리 해두어 에러를 숨기는 것보다 차라리 에러가 발생해야 좋은 코드이다.

(인자 값으로 들어오는 입력 값이 정확한 값이라면 절대 에러가 나지 않는 코드.) 즉 순수함수를 작성하고, 해당 순수함수를 사용하는 쪽에서 에러 핸들링을 해야 에러 핸들링도 적게 하고, 깔끔한 코드를 만들 수 있게 된다. 최대한 해당 로직을 사용하는 코드 쪽에서 최종 예외 처리 해주는 것이 좋다.

Q & A

1. 에러가 발생했을 때 실행이 멈추어 버리는 이유는?

Exception 이 then 함수와 만나 합성하면 reject 이 반환되고 이 reject 이 await 이라는 구문을 만나면 예외를 throw 한다.

즉, 예외 전파가 가능한 것이다.

부동산 취득세 과세표준을 실거래가로 변경

신고가액이나 시가표준액 중 더 높은 금액을 과세표준으로 적용해왔으나 실제 취득한 가액으로 취득세 납부해야 한다.

증여취득 취득세 '시가인정액' 적용

시가인정액은 취득일 전 6개월부터 취득일 후 3개월 사이의 매매사례가액, 감정가액, 공매가격 등을 시가로 보는 기준이다. 증여로 부동산을 취득할 경우 과세표준을 시가인정액으로 정해지면서 (거의 실거래 가격) 취득세 부담이 커진다.

이월과세 5년 => 10년으로 기간 확대

재산을 증여하는 자를 '증여자', 재산을 증여받는 자를 '수증자'라고 한다.

이월과세는 수증자가 그 배우자 또는 직계존비속으로부터 증여받은 토지, 건물, 부동산을 취득할 수 있는 권리, 시설물 이용권을 5년 내 양도하면 양도차익 계산 시 취득가액을 증여자의 취득가액으로 하는 제도이다.
(세법은 이처럼 자산의 장기보유에 따른 양도차익을 줄이기 위해 특수관계인에게 증여한 뒤 단기간 내 양도함으로써 세 부담을 줄이려는 조세 회피 행위를 방지하기 위해 이월과세 규정을 두고 있다.)

중소기업 장기근속자 특별공급 가점 변경

5년 이상 무주택일 경우 5점 배점 => 3년 당 3점, 최대 15점으로 변경

무순위 청약 거주지역 요건 폐지

거주지역 요건 폐지하고 무주택자라면 누구나 참여 가능

청년 맞춤형 전세특례보증한도 확대

한국주택금융공사에서 운영하는 청년 맞춤형 전세자금보증을

1억원에서 2억원으로 확대

재건축 안전진단 제도 개선

구조안전 항목 50% => 30%, 주거환경과 설비노후 30% 으로 비중 변경

‘조건부재건축’ 의 점수 범위를 45~55점으로 상향. 45점 이하일 경우 바로 재건축 추진

'조건부재건축' 단지에 의무적으로 시행했던 공공기관 적정성 검토(2차 안전진단) 의무 해제 (지자체 요청으로 변경)

월세 세액공제율 및 주택임차차입금 원리금 상환액 공제 한도 상향

2023년 연말정산부터 총급여 5500만원 이하인 무주택 근로자 및 성실사업자는 월세 새액공제율을 15% 로 상향

7000만원 이하는 10% 에서 12% 로 상향

월세 세액공제율 및 주택임차차입금 원리금 상환액 공제 한도 상향

임대차 신고제란, 임대차 계약 당사자가 임대기간, 임대료 등의 계약내용을 신고하도록 하여 임대차 시장 정보를 투명하게 공개하는 제도를 말한다. 이 임대차 신고제 계도기간을이 1년이었으나 내년 5월 31일까지 1년 더 연장

종합부동산세 기본공제금액 상향

종부세 기본공제금액이 6억원에서 9억원으로 상향

1세대 1주택자의 경우에는 현행 11억원에서 12억원으로 조정

종합부동산세 중과 배제 or 하향

조정대상지역 2주택 이상 보유자는 중과세율(1.2~ 6.0%)이 아닌 일반세율(0.5~2.7%)로 과세

과세표준 12억원이 넘는 3주택 이상 다주택자는 6% 에서 5% 로 하향

종합부동산세 세부담 상한율 일원화

주택 수에 따라 다르게 적용한 세부담 상한율을 150%로 일원화

1~2주택자는 150%, 조정대상지역 2~3주택 이상자도 150% 로 세액 증가 상한선을 150% 로 고정

아파트 관리비 공개대상 50세대 이상 공동주택으로 확대

공공분양 미혼청년 특별공급 도입

공공분양 모델 중 ‘나눔형(시세 70%이하 분양가+시세차익 70% 보장)’과 ‘선택형(임대 후 분양)’에 미혼 청년을 위한 특별공급이 새롭게 신설. 원래는 기혼자 중심의 신혼부부나 생애최초 주택구입자만 해당되었다.

민간분양 면적에 따라 청약가점제 개편

투기과열지구 내 중소형 면적(전용 85㎡ 이하)에 추첨제 신설

기존에는 투기과열지구 내 중소형 면적은 가점제 100% 로 공급

규제지역 내 전용 60㎡ 이하 주택은 ‘가점 40%+추첨 60%’를 적용하고, 60㎡ 초과~85㎡ 이하 주택은 ‘가점 70%+추첨 30%’로 추첨제 비율이 상향됨

생활안정･임차보증금 반환 목적 주택담보대출 규제 완화

기존의 LTV(주택담보대출비율)·DTI(총부채상환비율) 내에서 대출을 관리. 대신 임차보증금과 생활완정 목적만 대출 허용

나머지 목적은 대출 금지

생애 첫 주택구입자 취득세 감면 요건 완화

생애 첫 주택구입자는 소득과 주택가격에 상관없이 200만원 한도 내에서 취득세가 면제

주택담보대출 채무조정 대상 확대

6억원 이하 주택 차주가 실직이나 폐업･질병 등의 이유로 대출 상환이 어려운 경우 원금 상환을 최대 3년간 유예

특례보금자리론 출시

9억원 이하 주택 구입 시 연 4%대 금리로 5억원까지 대출

임대인 미납 국세 열람제도 실효성 강화 

전세계약을 체결한 세입자가 임대인의 동의 없이도 미납 조세를 직접 확인 가능

임차개시일 전까지 세입자가 계약서를 지참해 세무서장 등에게 열람 신청을 하면 임대인의 세금 체납내역을 볼 수 있음

임차보증금, 경･공매 시 당해세보다 우선 변제

임차보증금과 당해세 관계에서만 해당

전세 집이 경·공매로 넘어가면 세금이 먼저 변제되고 남는 금액을 배분해 전세금을 돌려줬으나, 앞으로는 ‘국세 우선변제 원칙’에 예외를 적용해 세입자의 확정일자 이후 법정기일이 도래하는 세금이 있어도 보증금 먼저 변제

useQuery 옵션 중에 onSuccess, onError, onSettled 같은 상태 변화가 일어날 때 트리거해주는 옵션이 있다.

현재 조회하고 있는 데이터의 상태에 따라 동작을 수행할 수 있어 onSuccess 에서 state 를 변경하곤 한다.

심지어 구글 첫 번째 검색 결과인 스택오버플로우에서도 권장하고 있는 방법이었다.

javascript - Store data from useQuery with useState - Stack Overflow

하지만 이는 안티패턴이라고 한다. Suspense 같은 React 에서 지원하는 컴포넌트를 같이 사용하게 될 때 렌더링 순서가 어떻게 바뀔지 모르기 때문이다. 

setState in onSuccess is not working first time with suspense · Issue #3784 · TanStack/query (github.com)

실제로 Suspense 와 useQuery 의 onSuccess (setState 동작) 를 같이 사용할 때 state 값이 업데이트가 되지 않는 이유를 물어보는 Tanstack/Query Issue 이다. 정리해보면 다음과 같다.

Suspense 와 useQuery, useEffect, onSuccess 가 호출되는 순서

1. <Suspense> 컴포넌트가 마운트 된다.
2. 자식 컴포넌트가 마운트 된다.
3. useQuery 비동기 함수가 호출이 된다. (이 때 Promise 를 던진다)
4. (<Suspense> 컴포넌트가 자식의 비동기 함수를 관찰하기 시작한다.)

Promise 의 상태가 Pending 상태이므로 <Suspense> 컴포넌트의 자식 컴포넌트가 언마운트된다.

그리고 Fallback 컴포넌트를 마운트한다.

5. 해당 시점에 useEffect 는 호출되지 않는다. 이미 언마운트 되었기 때문이다.

그러나 onSuccess 는 이 시점에 호출되고 언마운트 된 컴포넌트의 state 를 변경하려고 시도하기 때문에 아무 일도 일어나지 않는다.

6. Promise 의 상태가 Complete 되면서 특정 결과를 반환할 때 캐싱 처리된다.

7. Fallback 은 언마운트 되고 다시 자식 컴포넌트를 마운트한다.

8. 자식 컴포넌트가 마운트 되는 시점에 useEffect 가 호출되고, useQuery 캐시에 저장되어 있던 결과를 로드한다.

Suspense 가 결과가 회신되기 전까지 자식 컴포넌트를 언마운트하기 때문에 onSuccess 의 호출시점이 언마운트 중에 호출 되었다면 상태가 업데이트 되지 않는다는 것이다.

그래서 useQuery 로 도출한 결과 값을 useEffect 로 모니터링하고 해당 결과 값이 바뀌면 상태를 바꾸어야 한다.

Rules of Hooks – React (reactjs.org)

Only Call Hooks at the Top Level
Don’t call Hooks inside loops, conditions, or nested functions. Instead, always use Hooks at the top level of your React function, before any early returns. By following this rule, you ensure that Hooks are called in the same order each time a component renders. That’s what allows React to correctly preserve the state of Hooks between multiple useState and useEffect calls. (If you’re curious, we’ll explain this in depth below.)

위 React 공식문서를 살펴보면, 반복문 조건문 안이나 nested function 안에 hook 을 호출하면 안 된다고 명시하고 있다.

무조건 React Function Top level 에서 호출해야 한다. 이 규칙을 정해야 hook 의 호출 시점이 일관됨을 보장할 수 있기 때문이다.

따라서 Hook 을

- 조건문에서 사용하고 싶다면 결과 값을 useState 와 useEffect 에서 핸들링한다.

- 반복문에서 사용하고 싶다면 Hook 에서 반복을 지원하는지 살펴보거나, 반복할 리스트를 map 으로 맵핑하여 인자로 전달한다.

된다.

Bean 디버깅에 대해 구글링해보면 아래와 같이 Bean 을 직접 디버깅하기 보다는 Bean 에 대한 log 설정을 추가하여 살펴보는 것이 다였다. 그래서 내가 개발한 Bean 은 디버깅을 하지 못 하는 것일까? 계속 고민했었는데 아니다. 잘 된다.

java - Debugging Spring configuration - Stack Overflow

위와 같은 내용은 내가 개발한 Bean 이 아닌 Spring 내부 Bean 이거나 써드 파티 모듈의 Bean 의 동작을 확인하고 싶을 때 설정하는 것이다. 내가 개발한 Bean 은 BreakPoint 도 잘 설정이 되고 잘 멈춘다.

만약 Bean 내부에 브레이크포인트가 설정을 하였는데도 멈추지 않는다면 아래와 같은 경우를 의심해보아야 한다.

1. Bean 으로 등록만 하고 코드에서 사용하지 않는 경우

2. Bean 내부 브레이크포인트들이 써드파티 모듈에서만 처리되는 경우

3. Bean 이 정상적으로 로드되지 않는 경우

3 번은 아래와 같이 테스트하여 Bean 이 로드되는지 확인하면 된다.

@SpringBootTest
public class Test {

    @Autowired
    private ApplicationContext applicationContext;

    @Test
    public void contextLoads() throws Exception {
        if (applicationContext != null) {
            String[] beans = applicationContext.getBeanDefinitionNames();

            for (String bean : beans) {
                System.out.println("bean : " + bean);
            }
        }
    }
}

필자는 아래 네이버에서 작성한 Jackson Module 글을 읽고 똑같이 Module 을 설정하여 조금 더 깔끔한 코드를 만들려고 노력했는데 아무리 해봐도 되지 않았다. Jackson의 확장 구조를 파헤쳐 보자 (naver.com)

Bean 은 정상적으로 로드가 되는데 브레이크포인트도 걸리지 않고 정상적으로 파싱이 되지 않아 3일을 버린 것 같다. ㅠ

결론은 Bean 으로 만든 Module 을 ObjectMapper 에 연동하지 않아 발생한 문제였다. 아래와 같이 코드를 수정하니 정상적으로 json 이 파싱되었다.

objectMapper.registerModule(내가 만든 모듈);

이 문장 하나 때문에 Jackson 라이브러리 분석을 얼마나 했는지 모른다. 결국 Bean 으로 설정한 Module 과 registerModule 로 연동이 되지 않아서였다.

1. 문제요약

24042번: 횡단보도 (acmicpc.net)

횡단보도에 파란불이 들어오면 반대편 지역으로 이동할 수 있으며 이동하는 데 1분이 걸린다. 1 + i ( 0 <= i < M) 번째 신호는 i, M+i, 2M+i, 3M+i, ... 분 주기에 시작해서 1분 동안 Ai 번 지역과 Bi 번 지역을 잇는 횡단보도에 파란불이 들어오고, 다른 모든 횡단보도에는 빨간불이 들어온다. 한 주기 동안 같은 횡단보도에 파란불이 여러 번 들어올 수 있다.

횡단보도와 신호의 정보가 주어질 때, 시간 0 분에서 시작해서 1 번 지역에서 N 번 지역까지 가는 최소 시간을 구하시오.

2. 문제예제

3. 문제풀이(수동)

예제 풀이 2번을 수동 풀이한다.

각 횡단보도가 켜지는 시간대는 위 표와 같다. 내가 만약 7 - 8 번 구간을 처음에 선택하였다면 그 다음 구간을 선택할 때 걸리는 시간이 시계방향처럼 연산된다. 그 다음 1 - 5 번 구간을 선택하면 +2 가 되고, 3 - 4 번 구간을 선택하면 한 바퀴 돌아서 +10 이 된다. 그 다음 구간의 시간 대가 현재 시간 대보다 적다면 한 바퀴 돌아서 연산된다.

그렇게 1번부터 8번까지 순회하는 길이 가장 빠른 구간은 다음과 같다.

1 - 2 >> 2 - 3 >> 3 - 4 >> 4 - 8 로 7 + 2 + 4 + 5 = 18 이다.

4. 팩트추출

Fact 1 : 최소 시간이 소요되는 구간을 찾는 문제로 다이젝스트라 알고리즘 문제다. 다만 일반적인 다이젝스트라와 다른 점은 거리 계산 시 그 다음 구간의 시간 대가 현재 시간 대보다 작으면 cost 값을 한 바퀴 돌아서 더해주어야 한다는 점이다.

5. 문제전략

다이젝스트라 응용 문제다.

6. 소스코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    private static int N, M;
    private static List<List<Node>> crossWalk;
    private static long[] distance;
    static class Node implements Comparable<Node>{
        int index;
        long cost;
        Node(int index, long cost) {
            this.index = index;
            this.cost = cost;
        }

        @Override
        public int compareTo(Node o) {
            return Long.compare(this.cost, o.cost);
        }
    }
    private static void dijkstra() {
        PriorityQueue<Node> queue = new PriorityQueue<>();
        queue.offer(new Node(1, 0));
        distance[1] = 0;

        while(!queue.isEmpty()) {
            Node currentNode = queue.poll();
            if (currentNode.cost > distance[currentNode.index])
                continue;
            for (Node next :crossWalk.get(currentNode.index)) {
                int nextIndex = next.index;
                long nextCost;
                if (currentNode.cost <= next.cost) {
                    nextCost = next.cost + 1;
                } else {
                    // 모듈러 연산
                    nextCost = ((long) Math.ceil(((double)currentNode.cost-next.cost)/M)) * M + next.cost + 1;
                }
                if (nextCost < distance[nextIndex]) {
                    distance[nextIndex] = nextCost;
                    queue.offer(new Node(nextIndex, nextCost));
                }
            }
        }
    }
    public static void main(String[] args) throws Exception {
        StringTokenizer st;
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        distance = new long[N+1];
        Arrays.fill(distance, Long.MAX_VALUE);

        crossWalk = new ArrayList<>();
        for (int i = 0; i <= N; i++) {
            crossWalk.add(new ArrayList<Node>());
        }
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            crossWalk.get(u).add(new Node(v, i));
            crossWalk.get(v).add(new Node(u, i));
        }
        dijkstra();
        System.out.println(distance[N]);
    }
}

ITEM 33 "타입 안전 이종 컨테이너를 고려하라"

이 Item 을 확인하기 전에 꼭 아래 글을 보고 오는 것을 추천한다. 갑자기 타입 안전 이종 컨테이너 이야기가 나오는데, 왜 사용해야 되는지, 어떤 방식으로 구현되어 있는지 책에는 자세하게 나와있지 않아 직접 서치하고 정리했다.

[JAVA] 타입 토큰과 슈퍼 타입 토큰이란? :: 골드에그 (tistory.com)

위 글에서는 자바 제네릭의 한계 때문에 런타임 시 타입을 확인하기 위해 타입 토큰을 사용하여 타입 안전 이종 컨테이너(THC Pattern(Typesafe Heterogenous Container Pattern)) 를 활용한다고 하지만, 책에서는 제네릭 확장 개념으로 설명하고 있다. Set<E>, Map<K, E> 처럼 제네릭은 매개변수를 한 개나 두 개 정도 밖에 사용을 못 하는데 더 확장하여 사용하고 싶지 않냐는 식이었다. 사실 취지가 마음에 와닿지는 않았다.

그래도 개념은 동일하다. 타입 안전 이종 컨테이너(THC Pattern(Typesafe Heterogenous Container Pattern))는 컨테이너 대신 키를 매개변수화한 다음, 컨테이너에 값을 꺼내거나 뺄 때 매개변수화한 키를 활용한다는 것이다.

// 선언부
public class SimpleTypeSafeMap {
	private Map<Class<?>, Object> map = new HashMap<>();
    public <T> void put(Class<T> k, T v) {
    	map.put(Objects.requireNonNull(k), v);
    }
    public <T> T get(Class<T> clazz) {
    	return clazz.cast(map.get(clazz));
    }
}

// 사용부
simpleTypeSafeMap.put(String.class, "테스트");
simpleTypeSafeMap.put(Integer.class, 1);

String string1 = simpleTypeSafeMap.get(String.class);
Integer integer1 = simpleTypeSafeMap.get(Integer.class);

위 글 예제와 같다. HashMap Key 에 타입 토큰을 지정하여 값을 로드하고 저장하면 된다.

여기서 중요한 점은 키가 Class<?> 이라서 비한정적 와일드 카드이기 때문에 Map 안에 아무것도 못 넣을 수 있다고 생각할 수 있지만(타입을 체크하지 못하므로), 컨테이너 입장에서는 중첩되어 있기 때문에 Key 만 와일드카드 타입이기 때문에 모든 키가 가능하다. 또 맵의 값 타입이 Object 이기 때문에 이 맵은 키와 값 사이의 타입 관계를 보증하지 않는다. 하지만 메서드들에서 타입을 가져와 동적 캐스팅해 로드하고 타입을 키로 지정해 저장하기 때문에 상관없다. Map 자체로는 안전하지 않지만, 메서드들에서 이를 보장한다.

안전해보이지만, 아직 두 가지 제약이 존재한다.

첫 번째 제약은 클라이언트가 아래와 같이 Generic 타입이 아닌 Raw 타입을 전달하면 타입 안전성이 깨지게 된다. HashSet 이나 HashMap 같은 일반 컬렉션에 Raw 타입을 사용하는 것처럼 말이다.

map.put((Class)Integer.class, "hello");
int testInteger = map.get(Integer.class);

// 닮은 꼴 예제
HashSet<Integer> set = new HashSet<>();
((HashSet)set).add("hello");

단순히 cast 메서드는 Class 객체가 알려주는 타입의 인스턴스인지를 검사한 다음, 맞다면 그대로 반환하고 아니면 ClassCastException 예외를 던지기 때문이다. get 메서드에서는 cast 메서드로 맞는 타입인지 점검하는 반면에 put 메서드에서는 점검하지 않으므로 생기는 문제이다. 컴파일 타임 때 모두 점검하기 위해서 아래와 같이 코드를 수정하자.

    public <T> void put(Class<T> k, T v) {
    	map.put(Objects.requireNonNull(k), type.cast(v));
    }

type.cast 로 명시한 타입과 같은지 체크한다. 그냥 동적 형변환을 사용하면 된다. java.util.Collections 의 checkedSet, checkedList, checkedMap 과 같은 메서드들이 위와 같은 구조를 사용한다고 한다.

두 번째 제약은 제네릭(실체화 불가 타입)은 사용할 수 없다. 위 글에서 소개한 것처럼 제네릭에 대한 타입 토큰이나 클래스 리터럴이 준비되어 있지 않기 때문이다. 예를 들어 List<String>와 List<Integer> 는 List.class 클래스 객체를 공유하므로 타입 안전성이 깨지게 된다. 위 글에서 소개한 것처럼 슈퍼 타입 토큰 방식으로 처리해야 한다.

현재는 어떤 Class 객체든 받아들이는데 간혹 메서드들이 허용하는 타입을 제한하고 싶을 때가 있다. 그 때 한정적 타입 매개변수나 한정적 와일드카드를 사용하면 된다. 특히 애너테이션 API 가 한정적 타입 토큰을 적극적으로 사용한다.

public <T extends Annotation> T getAnnotation(Class<T> annotationType);

이 getAnnotation 메서드는 대상 요소에 달려있는 애너테이션을 런타임 때 읽어오는 기능을 한다. 토큰으로 명시한 타입의 애너테이션이 대상 요소에 달려 있다면 그 애너테이션을 반환하고 없다면 null 을 반환한다. THC 컨테이너다. (annotationType 인수가 한정적 타입 토큰으로 선언되어 있는 것을 볼 수 있다.)

만약 Class<?> 타입의 객체가 있고, 이를 getAnnotation 처럼 한정적 타입 토큰을 받는 메서드에 넘기려면 어떻게 해야 할까? Class<? extends Annotation> 은 비검사 형변환이므로 컴파일 경고가 떠서 안 되고, asSubclass 메서드로 동적 형변환 해야한다. 인자로 받은 클래스 객체로 형변환해준다. 컴파일 시점에는 알 수 없으나 런타임 때 읽어낼 수 있는 메서드이다.

"일반적인 제네릭은 한 컨테이너가 다룰 수 있는 타입 매개변수의 수가 고정되어 있다.

하지만 컨테이너 자체가 아닌 키를 타입 매개변수로 바꾸면 이런 제약이 없는 THC 컨테이너를 만들 수 있다."