[프로그래머스][Lv.1] - 명예의 전당(1)

 

● 소감

- 자료구조를 알면 확실히 도움이 된다.

 

● 나의 풀이

1) 문제 이해

 

- 점수는 score의 길이 만큼 제시되고, 차례차례 정렬이 이뤄지지만, k만큼의 갯수만 유지된다.

- 그럼 추가가 될 때 k 갯수를 유지하기 위한 조건만 찾으면 되고, 매 차례 정렬이 이뤄져야 하기 때문에 삽입하면 알아서 정렬을 해주는 set을 사용해야겠다고 생각했다.

- 한번 틀리고 깨달았지만 동일한 값이 또 제시될 수 있기 때문에 multiSet을 최종적으로 사용했다.

 

2) 조건 찾기

 

- 우선 사용할 multiSet을 만들고 score를 순차적으로 접근한다. 접근한 score은 차례대로 multiSet에 들어가게 되겠지만 k 개를 유지해야 하기 때문에 multiSet.size()와 k를 비교해준다.

- multiSet.size()가 k를 넘게 됐다면 Set의 front와 back (deque가 아니기 때문에 이렇게 접근할 순 없지만 이해를 위해) 중 어떤걸 지울지를 봐야하는데, 접근한 score가 Set의 front보다 컸다면 front가 밀릴테니 front를 제거, 그 반대라면 back을 제거 하는 식으로 처리했다.

if(multiSet.size() > k)
{
	if (*(multiSet.begin()) <= score[i])
		multiSet.erase(multiSet.begin());
	else
		multiSet.erase(multiSet.end());
}

 

 

● 내가 작성한 답

vector<int> solution(int k, vector<int> score)
{
	vector<int> answer;

	multiset<int> scoreSet;

	for(int i = 0; i < score.size(); i++)
	{
		scoreSet.insert(score[i]);

		if(scoreSet.size() > k)
		{
			if (*(scoreSet.begin()) <= score[i])
				scoreSet.erase(scoreSet.begin());
			else
				scoreSet.erase(scoreSet.end());
		}

		answer.push_back(*(scoreSet.begin()));
	}

	return answer;
}