[백준_1268] 임시 반장 정하기 ( 구현 - 자바스크립트 )

문제

 

https://www.acmicpc.net/problem/1268

1268번: 임시 반장 정하기

 

 

문제를 이해했는가?

 

다른 친구들과 같은 반이였던 횟수가 가장 많은 친구를 '임시반장'으로 선출한다.

 

 

접근 방법은 ?

 

[1] 브루트포스

처음에는 모든 값들을 비교한다는 생각을 가졌지만, 학생의 수가 1000명 까지 늘을 수 있다는 조건이 존재했다.

 

천 명의 인원을 모두 확인 해야 하기 때문에, 1000 * 1000 의 연산이 필요했고 뿐만 아니라, 5학년 모두를 탐색 해야 하기 때문에 브루트포스로 진행을 해버리면 500만번의 연산이 필요하다.

 

물론, 1초에 "1억"번 이라고 가정을 한다면 시간 내에 해결 할 수는 있겠지만 더 좋은 방법에 대해서 고민을 하게 되었다.

 

[2] 정답으로 가는 패턴을 찾자.

 

결과적으로 우리에게 요구되는건 "가장 많은 학생"과 같은 반이 된 기록이 있는 학생을 고르는 것이다. 

 

즉, 이걸 뒤집어서 생각해보면 일일이 다 찾지 않더라도 "학년 별로 가장 많이 중복된 반" 을 찾아서 그 반에 해당되는 횟수가 가장 많은 학생을 선출 하면 된다.

 

이렇게 되면 (1000 * 1000) * 2 번의 연산만이 요구되어 비교적 효율적으로 정답을 구할 수 있다.

 

function solution() {
  const nums = [];
 
 
  for (let i = 0; i < student[0].length; i++) {
    // 9반까지 존재 하기 때문에, 매 순회마다 10 크기의 배열을 만들어준다.
    const map = Array(10).fill(0);
 
    for (let j = 0; j < student.length; j++) {
     // 해당되는 반의 카운트를 증가시킨다.
      map[student[j][i]] += 1;
    }
	
    // 가장 중복이 많이 되는 반의 값을 찾는다.
    const max = Math.max(...map);
	
    // 중복이 가장 많이 됬을 때가 1이라는건 중복이 없다는걸 의미 : 0을 추가
    // 중복이 1이 아니라는건, 2이상의 값이 최고 값이기 때문에 그 값을 찾아서 추가.
    max === 1 ? nums.push(0) : nums.push(map.indexOf(max));
  }
	
  // output = [ 0, 5, 2, 6, 0 ] 
  
  // 학생 수만큼 배열을 만들어준다.
  const count = Array(student.length).fill(0);
 
  // 각 학생의 학년 별 반을 모두 순회하면서
  for (let i = 0; i < student.length; i++) {
    for (let j = 0; j < student[i].length; j++) {
      // 가장 중복이 많이 된 반에 해당된다면 카운트를 증가시킨다.
      if (student[i][j] === nums[i]) count[i] += 1;
      
    }
  }
  // 가장 많은 중복 값을 얻은 학생의 인덱스를 출력한다.
  console.log(count.indexOf(Math.max(...count)) + 1);
}

 

느낀점

 

"쉬운 문제를 어렵게 풀자" 라는 생각을 가지고 있었는데, 이러한 생각은 조금 잘못 되었음을 느낀다.

 

굳이 어렵게 푸는 것이 아닌, 문제의 의도가 어려운 문제보다 명확하니 이에 더욱 걸맞는 해결 방법을 찾기 위한 노력이 필요한게 아닐까 생각이 든다.

 

사실 이번 문제 같은 경우도 [1]의 방식을 채택 할 수 있었지만, 다른 해결 책을 찾은 것이 매우 만족스럽다.