프로그래밍 일기 — 모의고사 수수께끼
알고리즘 풀이는 매일 계속된다.
지금 매일같이 프로젝트를 진행시키는데 집중하고 있지만, 그럼에도 불구하고 알고리즘 푸는 연습은 계속하고있다. 알고리즘 코딩 테스트는 개발자로 일하고 싶다면 결코 피할 수 없는 스크리닝 과정이기 때문이다.
오늘 해결한 문제는 내가 지난 3일간 풀지 못했던 수수께끼다. 알고리즘 레벨이 한 층 올라갈 수록 어려워진다는 것을 확실히 느낀다. 오늘 문제는 그럼 어떤 것이었고, 어떻게해서 풀었는지를 정리해본다.
수수께끼 — 모의고사(2)
문제 설명
수포자는 수학을 포기한 사람의 준말입니다. 수포자 삼인방은 모의고사에 수학 문제를 전부 찍으려 합니다. 수포자는 1번 문제부터 마지막 문제까지 다음과 같이 찍습니다.
1번 수포자가 찍는 방식: 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, …
2번 수포자가 찍는 방식: 2, 1, 2, 3, 2, 4, 2, 5, 2, 1, 2, 3, 2, 4, 2, 5, …
3번 수포자가 찍는 방식: 3, 3, 1, 1, 2, 2, 4, 4, 5, 5, 3, 3, 1, 1, 2, 2, 4, 4, 5, 5, …
1번 문제부터 마지막 문제까지의 정답이 순서대로 들은 배열 answers가 주어졌을 때, 가장 많은 문제를 맞힌 사람이 누구인지 배열에 담아 return 하도록 solution 함수를 작성해주세요.
제한 조건
- 시험은 최대 10,000 문제로 구성되어있습니다.
- 문제의 정답은 1, 2, 3, 4, 5중 하나입니다.
- 가장 높은 점수를 받은 사람이 여럿일 경우, return하는 값을 오름차순 정렬해주세요.
입출력 예
- answers: [1,2,3,4,5] → 리턴값: [1]
- answers: [1,3,2,4,2] → 리턴값: [1,2,3]
입출력 예 #1
- 수포자 1은 모든 문제를 맞혔습니다.
- 수포자 2는 모든 문제를 틀렸습니다.
- 수포자 3은 모든 문제를 틀렸습니다.
따라서 가장 문제를 많이 맞힌 사람은 수포자 1입니다.
입출력 예 #2
- 모든 사람이 2문제씩을 맞췄습니다.
문제 해설
위 문제에서 포착된 패턴은 3가지다.
- patternOne: [1, 2, 3, 4, 5]
- patternTwo: [2, 1, 2, 3, 2, 4, 2, 5]
- patternThree: [3, 3, 1, 1, 2, 2, 4, 4, 5, 5]
위 문제를 푸는 과정은 아래와 같다.
- 위 패턴을 가지고 주어진 배열인
answers를 순회하면서 처음부터answers.length길이까지 하나씩 값을 참조한다. - 참조한 값을 위 3가지 배열과 비교하여 일치할 경우 크기 3인 카운트 배열([0, 0, 0])을 하나 생성해 각 배열의 카운트 값을 하나씩 증가시킨다.
- 가장 큰 값을 갖는 배열의 값의 위치값을 리턴한다.
import java.util.ArrayList;
class Solution {
public int[] solution(int[] answer) {
// 1. 3가지 패턴을 배열로 선언한다.
int[] patternOne = {1, 2, 3, 4, 5};
int[] patternTwo = {2, 1, 2, 3, 2, 4, 2, 5};
int[] patternThree = {3, 3, 1, 1, 2, 2, 4, 4, 5, 5};
// 2. 카운트용 배열 생성
int[] count = new int[3];
// 3. 주어진 배열값을 순회
for(int i = 0; i < answer.length; i++){
// 첫 번째 패턴과 위치마다 값이 일치하는지 확인
if( answer[i] == patternOne[i% patternOne.length]) {
count[0]++;
}
// 두 번째 패턴과 위치마다 값이 일치하는지 확인
if( answer[i] == patternTwo[i% patternTwo.length]) {
count[1]++;
}
// 세 번째 패턴과 위치마다 값이 일치하는지 확인
if( answer[i] == patternThree[i% patternThree.length]) {
count[2]++;
}
}
// 4. 결과 값을 저장하기 위한 배열 생성
ArrayList<Integer> arr = new ArrayList<>();
// 5. 최대값 찾기
int max = Math.max(count[0], Math.max(count[1], count[2]));
// 6. 카운트 배열의 첫 번째 값이 최대값과 일치하는지 확인
if (count[0] == max){
// 일치하면 위치 값을 '1'로 저장
arr.add(1);
}
// 카운트 배열의 두 번째 값이 최대값과 일치하는지 확인
if (count[1] == max){
// 일치하면 위치 값을 '2'로 저장
arr.add(2);
}
// 카운트 배열의 세 번째 값이 최대값과 일치하는지 확인
if (count[2] == max){
// 일치하면 위치 값을 '2'로 저장
arr.add(3);
}
// 7. 카운트 배열을 int[] 기본자료형 배열로 변환
int[] finalArr = new int[arr.size()];
for(int j = 0; j < arr.size(); j++){
finalArr[j] = arr.get(j);
}
// 8. 결과값 리턴
return finalArr;
}
}오늘 배운 가장 중요한 팁
순회하려는 배열의 크기가 참조하려는 배열의 크기보다 작을 때 (예: 위에서 answer.length < patternTwo or patternThree ), 현재 참조하는 인덱스에서 참조하려는 배열 ( patternTwo or patternThree ) 을 나누어주면 ( i%patternTwo or i%patternThree ) 참조하려는 배열의 크기를 넘지않도록 순회가 가능하다.
참조하려는 배열
b[]가 인덱스i로 반복문내에서 순회하녀는 배열a[]보다 크다면(b[].length>a[].length),b[i%a[].length]로a[].length에 맞춰b[]배열의 참조가 가능하다.
참조:
(1) https://pixabay.com/photos/child-crossroad-kid-choice-1721906/
(2) https://school.programmers.co.kr/learn/courses/30/lessons/42840
