16498 작은 별점

완전탐색을 생각해봤다. 각 세사람이 가지고 있는 수를 가지고 만들 수 있는 경우가 1000 * 1000 * 1000으로 10억이 되어서 시간 초과가 난다는 것을 발견했다. 

 

최적화를 어떻게 해야할까?

세 수가 똑같을 경우 0으로 가장 작다.
두 수가 같고 1차이 나는 수가 있으면 1로 작다.
세 수가 모두 다르고 가장 큰 수와 가장 작은 수가 2 차이나면 2로 작다.

세 수가 모두 다르고 가장 큰 수와 가장 작은 수 가 3 차이나면 3으로 작다.

...

 

세 사람의 각 수를 비교해야한다. 근데 이걸 반복문으로 비교할 생각밖에 안났다. 아무리봐도 그건 아닌데 어떻게 해야하지?

무엇인가 비교할 때 for문에 갇혀있지 말 것 ,, for문 말고 while문을 활용해서 반복문을 쓰되 종료조건을 설정하면 된다.

 

 

세개의 배열에 포인터를 두고 포인터를 옮기는 방식으로 비교한다.

 

세 배열을 모두 정렬한다.

처음 세 개의 포인터는 모두 0에 있다.

세 수의 max값과 min값을 찾아서 result와 비교한다.

가장 작은 수의 포인터를 오른쪽으로 한 칸 옮겨준다. ( 포인터를 어떻게 옮길 것인가? 이것또한 고민이었다.)

 

 

포인터 중에 하나라도 범위를 초과하면 종료한다. 왜냐 ? 세 수를 골라야하는데 포인터가 범위를 벗어났다는 것은 세개의 수를 뽑을 수 없는거니까