You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
reacted with thumbs up emoji reacted with thumbs down emoji reacted with laugh emoji reacted with hooray emoji reacted with confused emoji reacted with heart emoji reacted with rocket emoji reacted with eyes emoji
Uh oh!
There was an error while loading. Please reload this page.
문제 링크
https://school.programmers.co.kr/learn/courses/30/lessons/42840
문제 조건
3명의 수포자가 문제를 찍는 방식은 다음과 같다.
문제의 정답이 주어졌을 때 가장 많은 문제를 맞힌 사람이 누구인지 배열에 담아 반환하라
아이디어
답을 찍을 때 반복되는 규칙은 다음과 같습니다.
제공되는 답은 특별한 규칙이 없으므로 직접 완전 탐색을 통해 모든 케이스를 탐색해야 합니다.
먼저 모든 케이스를 살펴볼 때 시간복잡도를 계산해봅시다.
문제의 개수가 N이라고 했을 때 모든 문제의 정답을 검사하려면 O(N)의 시간이 소요되고, 수포자들의 수가 M이라고 할 때 O(N)이 M번 반복되므로 O(NM)이 소요됩니다.
문제의 조건은 N이 10000 이하이며 M이 3이므로 충분히 해결 가능한 방법입니다.
먼저 각 수포자들의 규칙을 나타내는 2차원 배열 상수를 정의해두고, 나머지 연산자를 통해 해당 문제에 각 수포자들이 어떤 답을 냈는지 알아내는 메서드를 정의합니다.
이제 모든 문제를 순회하면서 각 수포자의 정답 개수를 세어주고, 가장 많은 정답의 개수를 업데이트해줍니다.
이제 max값에 해당하는 수포자를 배열로 만들어 반환해주기만 하면 됩니다.
구현
All reactions