[백준] 1655번 가운데를 말해요

안녕하세요~!

오늘은~ 1655번!

 

이 문제를 풀면서도 나는 얼마나 멍청한가를 깨달았던..

 

분명히 대학교에서 배운 것인데.. 왜 기억이 안나는 것인가 ㅠ_ㅠ

난 정말 멍청이야!

 

이래서 공부는 꾸준히 해야하나보다..

이제 진짜 내 목표량은 채워야지!

 

유튜브 설명 첨부드립니다!

youtu.be/DUBAgZkB0jM

일단 오늘의 문제와 입력, 출력 값이다.

근데 이것이 중요한게 아니다....

 

바로바로 여기서 제일 중요한 것은!!!!

요 시간제한이다!

 

문제만 보고 생각이 든것은..

입력을 받고 > array에 추가해서 > sort를 하면 되지 않을까였다.

그래서 한 첫번째 도전!

사실 세번째? 도전이다.

처음에 array로 해봤는데 메모리초과?가 발생해서, 그 다음은 vector로 그 다음은 boolean 값을 추가해서 계산의 횟수를 줄여보고자 했으나..

전부 시간초과

 

그래서 내가 모른는 방법이 있구나 하고

다른 이들의 방법을 찾아보았다.

 

Priority Queue에 대해 많이 나와서, Priority Queue에 대해 먼저 공부하고

문제를 풀어나갔다.

 

내가 푼 방법은 아래와 같다.

먼저 PriorityQueue 가 2가지가 필요하다.

1. 큰 값이 우선순위가 높고, 기준 수 보다 작은 수들을 저장할 minQueue

PriorityQueue<Integer> minQueue = new PriorityQueue<>(Collections.reverseOrder()); 

2. 작은 값이 우선순위가 높고, 기준 수 보다 큰 수들을 저장할 maxQueue

PriorityQueue<Integer> maxQueue = new PriorityQueue<>();

 

그 다음 알고리즘? 은!

1. 맨 처음 입력된 수는 minQueue에 넣어준다. 

2. 입력된 수와 minQueue의 헤더를 비교한다.

   입력된 수가 크다면 -> maxQueue로 / 그 외의 경우 -> minQueue로 넣어준다.

3. 넣은 후 maxQueue와 minQueue의 size를 비교한다.

   minQueue의 size가 maxQueue의 size보다 2 더 크다면, minQueue의 헤더와 maxQueue의 헤더를 스왑해준다.

   maxQueue의 size가 minQueue의 size보다 1 더 크다면, maxQueue의 헤더를 minQueue로 이동시킨다.

 

그림으로 확인해보면,

(눈에 보기 좋게 각 Queue의 head의 색을 달리 했고, Min Queue의 head가 출력되는 수 이다.)

STEP 1.

1의 값이 입력 되었을 때, minQueue에 넣어준다.

STEP 2.

입력된 5는 MinQueue의 head인 1보다 크므로 MaxQueue에 넣어준다.

STEP 2.

입력된 2는 MinQueue의 head인 1보다 크므로 MaxQueue에 넣어준다.

넣어준 뒤 두 Queue의 사이즈를 비교해준다.

MaxQueue의 size가 MinQueue의 size 보다 1더 크기 때문에, MaxQueue의 peek가 MinQueue으로 이동시켜준다.

STEP 3.

입력된 -99는 MinQueue의 head인 2보다 작으므로 MinQueue에 넣어준다.

STEP 4.

입력된 7는 MinQueue의 head인 2보다 크므로 MaxQueue에 넣어준다.

STEP 5.

입력된 5는 MinQueue의 head인 2보다 크므로 MaxQueue에 넣어준다.

넣어준 뒤 두 Queue의 사이즈를 비교해준다.

MaxQueue의 size가 MinQueue의 size 보다 1더 크기 때문에, MaxQueue의 peek가 MinQueue으로 이동시켜준다.

 

이러한 원리로 코드를 작성해보면,

두둔..

시간초과가 발생한다!!

 

원인은 바로바로

Scanner 였다.

 

검색해보니 Scanner 는 편리하지만 시간이 느리다는 단점이 있다고 한다.

그래서 Scanner보다는 BufferedReader를 사용하는게 시간 리소스를 줄이는데 도움이 된다고 한다.

 

그래서!!

최종 나의 소스는

 

성공!

 

이제 PriorityQueue에 대해서 정리해보아야겠다!

 

끘~!