Kakao_보석쇼핑

시작

효율성을 검증하는 문제다. 사실 문제 요구사항은 크게 어렵지 않다. 

다만, 보석의 개수가 100,000 이라는 점에서 반복문을 2번만 돌려도 시간초과가 날 수 있으니 유의해야 한다.

배열의 범위가 커지면 O(N)이나 혹은 그 이하로 프로그램이 수행해야 하는 경우가 종종 있다. 

이 문제를 접근해서 해결할 수 있는 방법은 투포인트 방법이 있다. 

여기서는 원포인트, 투포인트 접근 모두 다뤄보고자 한다. 

 

알고리즘 동작 원리(투포인트)

쉽게 말하면 보석을 조금씩 덜어내고 마침내 사라지면 마지막으로 보석을 본 시점부터 끝까지 돌며 해당 보석을 찾아가는 과정을 나열한 것이다.

 

조금 복잡해 보이지만, 별거 없다! 

눈여겨 봐야할 것은 

1. 중복제거해서 쥬얼리 종류 파악

2. HashMap에 각 쥬얼리가 얼만큼 등장했는지 (단, 쥬얼리종류가 다 있으면 카운트 스탑!)

 

Ruby가 연속해서 2번 나오는 시점에서 Ruby의 Count가 0이 된다. 

이 경우 마지막으로 본 보석의 인덱스(end 위치)부터 gems 끝까지 바라보면서 Ruby를 찾게 된다. 

만약 없으면 gems.length 직전까지 바라본다. 

해당 알고리즘의 경우 정리하면 다음과 같다. 

쥬얼리 종류를 파악한다. 파악 했다면, 나열된 쥬얼리를 카운팅한다. 다만, 쥬얼리 종류가 다 나오는 시점에서 종료된다. 

이 지점이 end의 지점이다.

그리고 start부터 쥬얼리 카운트를 줄여나간다.

왜냐하면 연속되는 쥬얼리의 간격을 확인하기 위함이다. 

카운트를 줄여가면서 0이 되는 시점에서 end부터 다시 쥬얼리를 순회한다.

카운팅이 0으로 수정된 쥬얼리를 새롭게 발견해야 연속된 쥬얼리를 파악할 수 있기 때문이다.

 

투포인트 - Ver(통과)

코드로 구성하면 다음과 같다. 

 

알고리즘 동작 원리(포인트) 

이번에는 하나의 포인트로 연속되는 쥬얼리 간격을 찾아보자.

이건 의외로 더 간단하다.

Map에 (쥬얼리 이름, 인덱스) 를 저장한다. 만약, 같은 쥬얼리가 나오면 맨앞에 쥬얼리를 지우고 뒤에 새 쥬얼리, 인덱스를 붙이게 된다.

그렇기 때문에 Java를 이용해 해결하고자 할때는 HashMap보다는 ListHashMap을 이용하는것이 좋다. (나올 때 순서보장)

그래서 하기 사진을 보면 DIA 는 인덱스가 0이고 첫번째에 위치한다.

두번째 RUBY는 1이지만 2번째에도 나왔기 때문에 RUBY,2 로 갱신한다.

DIA가 나오면 앞에 DIA가 존재하기 때문에 DIA를 지우고 뒤에 DIA,3을 붙인다. 

그런데 DIA가 연속해서 나오기 때문에 지우고 DIA,4로 붙인다. 

새롭게 나오는 쥬얼리 EMERALD를 그 뒤에 붙인다. 

그 뒤에 SAPPHIRE를 붙인다. 

쥬얼리 종류와 일치하게 되므로 start, end를 저장한다. 

이때 이 둘의 차잇값을 계산하게 된다. Min값으로 정의한다. 

같은 로직이지만, 뒤에 DIA가 존재하긴 하지만 이전에 구한 Min값이 더 작기 때문에 갱신하지 않는다. 

포인트 - Ver1(시간초과)

아래 코드는 효율성 검증을 통과하지 못한다. 

 

포인트 - Ver2(시간초과)

마찬가지로 아래 코드도 효율성 검증을 통과하지 못한다. 

 

포인트 - Ver3(통과)

아래 코드는 효율성 검증을 통과한다. 

이유는 간단한데, 

 int first = (int)hm2.get(hm2.keySet().toArray()[0]);

 int second = (int)hm2.get(hm2.keySet().toArray()[hm2.size() -1]);

이 부분이 문제였다.

왜냐하면, for문안에서 hm2를 한번 더 순회하기 때문에 최대 O(N^2) 만큼 수행될 수 있었다. 

그래서,  second의 경우 현재 index를 알고 있으면 쉽게 구할 수 있는데 (마지막 위치)

first 를 구하기 어려웠다. 왜냐하면 같은 쥬얼리가 나오게 되면 그게 중간에 있을지 처음에 있을지 알 방법이 없기 때문이다.

그래서 순서를 유지하게 해줄 ArrayList를 선언해서 쥬얼리를 순서대로 담으며 같은 쥬얼리가 나오게 되면 그게 첫번째인지 중간에 있는지 확인하는 용도로 사용하였다. 

 

모쪼록 굉장히 헷갈렸던 문제..

투포인트에 대해 깊이 공부할 수 있어서 좋았다.