0. 들어가기 전 주저리
코딩 테스트를 틈틈히 풀고 있기는 했지만, 입문부터 시작한 상황에서 막힌 문제가 하나 있었다.
프로그래머스에서 풀고 있는 코딩 테스트 3일차에는 이런 문제가 있다.
보다시피 3일차로 선정되어 있는 네 문제 중 세 문제는 제법 수월하게 풀 수 있었다.
하지만 이상하게도 이 '최빈값 구하기' 문제는 며칠을 고민해도 풀리지를 않았다.
심지어 3일차에 배치된 문제 치고도 정답률이 낮은 축에 속했다. 나만 난이도가 높다고 생각하는 것도 아닌 건지, 질문 수도 다른 문제에 비해 압도적으로 많았다. (대부분의 쉬운 문제 정답률이 80~90% 정도 하니...)
아무리 머리를 쥐어뜯고 고민해봐도 안 풀리니, 결국 인터넷으로 풀이를 찾아보기도 했는데 그걸 봐도 왜 이렇게 푼 건지 이해하질 못했다.
풀이를 보고도 이렇게 풀면 되겠다, 라고 납득도 되지 않으니 한동안 이 문제만 방치해 놓고 딴 문제만 열심히 풀고 있었다. 그러다 문득 레벨 테스트 중 남는 시간에 풀어보리며 제공 받은 응용 문제 중 또다시 그놈이 나타났다.
- 주어진 배열에서 가장 자주 나오는 값인 최빈값을 구하는 함수를 작성하시오.
단, 최빈값이 여러개인 경우 가장 값이 작은 값을 구한다.
프로그래머스에서 나오는 문제와는 약간 조건이 다르기는 하지만, 또 최빈값 문제가 등장했다.
풀지 못했던 그 문제가 또다시 등장하니, 이제는 제발 제 손으로 풀고 싶다는 울분이 차올랐다.
그래서 이번 주말 공부의 주제를 이것 하나만큼은 꼭 풀어보자. 라는 목표를 가지고 공부를 시작했다.
(물론 결과적으로는 이거 한 문제만 하루종일 푼 거는 아니고... 코딩테스트 공부를 열심히 했다만)
1. 문제
우선은 프로그래머스 문제 말고 제공 받았던 응용 문제 기준으로 고민을 시작했다.
- 주어진 배열에서 가장 자주 나오는 값인 최빈값을 구하는 함수를 작성하시오.
단, 최빈값이 여러개인 경우 가장 값이 작은 값을 구한다.
2. 고민, 그리고 접근 방법
분명 해당 문제를 풀기 위한 과정은 다음과 같다고 생각했다.
- 해당 배열 중 중복되는 값을 세는 변수가 필요. 이를 통해서 중복되는 개수를 센다.
- 그 중복되는 개수를 센 다음, 그 중에서도 가장 개수가 많은 배열의 수를 반환한다.
- 최빈값이 여러 개일 경우, 제일 작은 수를 반환한다.
그런데, 중복되는 개수를 담을 변수를 어떻게 설정해야 하지? 그리고 만약 중복되는 개수가 여러 개면 그 값을 담을 변수도 여러 개가 되어야 하는데 이걸 어떻게 하지? 그에 대한 고민도 깊었고, 그 부분을 해결하지 못해 여전히 문제를 풀지 못하고 있었다.
그 막막한 과정에서 영감을 주었던 어떤 글을 보게 되었다.
접근방법
- 최빈값은 주어진 값 중에서 가장 자주 나오는 값이다.
사람은 배열 안의 값을 보고 최빈값을 확인할 수 있다. 하지만 코딩으로 구현하기 위해서는 새로운 배열이 하나 필요.
새로운 배열에서는 A(매개변수로 주어진 배열) 배열 요소 중 중복되는 값이 있으면 1씩 증가시켜서 대입한다.
그렇게 되면
{ 1, 2, 2, 2, 3, 4} 라는 배열이 있다면,
{ 1, 3, 1, 1 }의 값이 새로운 배열에 저장된다.
새로운 배열에서 최대값을 구한다면 이 최대값이 바로 기존의 A배열에서의 최빈값이 된다.개수를 센 수를 배열로 저장하는 방식. 사실은 고민해보지 않은 것은 아니었지만, 금방 떠올릴 수 있는 방법은 아니었다. 특히나 나는 저 예시를 보고서 저것보다 더 확실하고, 쉬운 접근 방식을 떠올릴 수 있었다. 그래서 실제로 해당 글을 참고했음에도 해당 글과는 다른 풀이방식을 내놓았다.
어떻게 풀었는지는 밑에서 서술하겠다.
3. 풀이 과정
1) 우선 Count를 배열로 선언하고, 그 크기를 array의 크기와 같은 것으로 초기화한다.
Count를 배열로 선언하자는 아이디어에는 도달했지만, 배열을 초기화해야 할 때 어떻게 해야 할지 막막했다. 참고했던 글에서는 배열의 크기를 다소 이해할 수 없는 수치를 넣었는데, 그대로 따라해 보기는 싫어 배열의 크기를 어떻게 할 건지에 대한 고민을 했다.
우선, 배열의 크기를 선언한 뒤에 내가 할 게 뭐지? 가만 생각을 해 보았다. 나는 다음과 같은 코드로 배열에 해당 값들을 집어넣을 것이었다.
for(int i = 0; i < array.Length; i++)
{
int findNum = array[i]; // array 배열에서 비교할 첫 번째 숫자
for(int j = 0; j < array.Length; j++)
{
if(findNum == array[j])
{
Count[i]++;
}
}
}이렇게 코드를 써 보니 문득, 이 결과가 어떻게 출력될지 생각해보게 되었다.
예시를 들어 위의 경우로, { 1, 2, 2, 2, 3, 4} 라는 배열을 해당 for 문에 넣게 되면 이렇게 결과가 나올 것이다.
{ 1, 3, 2, 1, 1, 1}
사람들이 보기에는 중복된 개수가 { 1, 3, 1, 1}로 읽히겠지만, 내가 쓴 for 문을 그대로 쓰면
위와 같이 출력될 것이다. 하지만, 그래도 실제 문제를 푸는 데에는 영향이 없다. 왜냐하면 중복된 두 번째 숫자의 Count개수는 무조건 첫 번째 중복된 Count 개수보다 작게 나올테니까.
이걸 깨닫는 순간 문제를 푸는 길이 보였고 동시에 초기에 Count[] 배열의 크기를 초기화할 방법도 보였다. 아주 단순하게, Count 배열의 크기는 Array 배열의 크기와 똑같이 선언하면 된다.
그래서 초기 부분을 아래와 같이 작성하였다.
int[] Count = new int[array.Length]; // Count 배열의 선언, array와 동일한 크기
for(int i = 0; i < array.Length; i++)
{
int findNum = array[i];
for(int j = 0; j < array.Length; j++)
{
if(findNum == array[j])
{
Count[i]++;
}
}
}이렇게 하면 { 1, 2, 2, 2, 3, 4} 라는 배열이 있을 때 출력되는 값은 { 1, 3, 2, 1, 1, 1}이다.
이제 이 Count 배열에서 다시 for 문으로 최대값 - 개수가 제일 많은 최빈값을 구한다.
int maxCount = 0; // 최빈값의 개수
int answer = 0; // 최반값의 실제 수
for(int i = 0; i < Count.Length; i++)
{
if(maxCount < Count[i])
{
maxCount = Count[i];
answer = array[i];
}
}최빈값을 어찌저찌 구한다고 해도, 그 최빈값의 실제 값이 몇인지 알 수가 없다는 게 가장 큰 고민이었다. 하지만 처음부터 array 배열의 모든 숫자의 중복여부를 세는 방식으로 설계한 덕분에,
이 최빈값의 실제 값을 알아내는 방법도 쉽게 할 수 있었다.
이와 같은 for 문에 { 1, 3, 2, 1, 1, 1}을 돌리면, 결국 maxCount = 3이 되고, array[1]의 값인 2가 반환될 것이다.
이제 남은 건, 최빈값이 한 개 이상일 경우를 찾는 것이다. 이 부분은, 오히려 앞 부분이 거의 완성된 덕분에 쉽게 만들 수 있었다. 우선은 위의 for문이 전부 실행된 뒤에, 한 번 더 값을 비교해 보면 된다.
for(int i = 0; i < Count.Length; i++)
{
if (maxCount == Count[i]) // 앞의 for문에서는 같은 수의 경우 maxCount 반영이 안되었다.
{
if(answer > array[i]) // 처음의 최빈값이 비교하는 최빈값이 수보다 클 경우
{
answer = array[i]; // 작은 최빈값 수를 최종 최빈값 수로 반영
}
}
}
return answer;이와 같은 방법으로 중복된 최빈값일 경우 제일 작은 값이 반환되도록 설정을 마쳤다.
4. 결과
최종 코드는 아래와 같이 나온다.
public static int FindModeNumber(int[] array)
{
// 개수를 세는 Count 배열을 새로 생성
int[] Count = new int[array.Length];
int maxCount = 0; // Count 중 가장 큰 수
int answer = 0; // return 할 최종 최빈값의 실제 수
// 1. array 배열의 각 수의 중복 여부를 Count
for (int i = 0; i < array.Length; i++)
{
int findNum = array[i];
for(int j = 0; j < array.Length; j++)
{
if(findNum == array[j])
{
Count[i]++;
}
}
}
// 2. Count 배열에서 가장 큰 수를 찾고, answer에 최빈값의 실제 수를 대입
for (int i = 0; i < Count.Length; i++)
{
if(maxCount < Count[i])
{
maxCount = Count[i];
answer = array[i];
}
}
// 3. 최빈값이 개수가 여러 개일 경우, answer와 비교하여 제일 작은 수를 반영
for(int i = 0; i < Count.Length; i++)
{
if (maxCount == Count[i]) // 앞의 for문에서는 같은 수의 경우 maxCount 반영이 안되었다.
{
if(answer > array[i]) // 처음의 최빈값이 비교하는 최빈값이 수보다 클 경우
{
answer = array[i]; // 작은 최빈값 수를 최종 최빈값 수로 반영
}
}
}
return answer;
}해당 코드로 예시에서의 값이 모두 정상반환된 것을 확인했으며, 그 외에 다양한 배열을 넣어도 원하는 대로 값이 출력되는 것을 확인하였다.
5. 그러면 프로그래머스 문제는?
프로그래머스 문제의 경우에는 해당 문제와의 차이점이 이렇게 되어 있다.
- 문제 설명
최빈값은 주어진 값 중에서 가장 자주 나오는 값을 의미합니다. 정수 배열 array가 매개변수로 주어질 때, 최빈값을 return 하도록 solution 함수를 완성해보세요. 최빈값이 여러 개면 -1을 return 합니다.
- 제한사항
0 < array의 길이 < 100
0 ≤ array의 원소 < 1000
- 입출력 예
[1, 2, 3, 3, 3, 4] -> 3
[1, 1, 2, 2] -> -1
[1] -> 1
- 입출력 예 설명
입출력 예 #1
[1, 2, 3, 3, 3, 4]에서 1은 1개 2는 1개 3은 3개 4는 1개로 최빈값은 3입니다.
입출력 예 #2
[1, 1, 2, 2]에서 1은 2개 2는 2개로 최빈값이 1, 2입니다. 최빈값이 여러 개이므로 -1을 return 합니다.
입출력 예 #3
[1]에는 1만 있으므로 최빈값은 1입니다.
※ 공지 - 2022년 10월 17일 제한 사항 및 테스트케이스가 수정되었습니다.
내가 위에서 풀었던 문제와의 차이점은, 최빈값이 중복일 시 제일 작은 값을 반환하는 것이 아닌, -1을 반환하라는 조건이다.
그러면, 위에서 작성한 최종 코드 부분에서 3의 부분만 수정하면 된다.
for(int i = 0; i < Count.Length; i++)
{
if (maxCount == Count[i])
{
if(answer != array[i]) // answer 가 array[i]와의 값이 다를 경우
{
answer = -1; // -1을 반환
}
}
}
return answer;
}이와 같이 드디어 골머리를 앓던 프로그래머스 문제까지 푸는 데 성공하였다.
<참고자료>
(최빈값 구하기 접근방법)
https://limitlife20.tistory.com/4
