알고리즘을 학습할 수록 느끼는 점이지만, 나는 정말 문제 해석이 너무 어렵다.
잘 알아듣다가도 이해가 안되는 부분이 생기면 거기서 막혀버린다. 이번 숙제도 그랬다. 난이도 하인데 왜 바로바로 못 풀겠지? 문제 해석하는 데에만 시간이 많이 들었다.
최대한 잘 정리해보려고 하는데 이번에도 막히는 부분이 생겼다.
/**음악 테스트 응시자의 패턴
* 시험 문제의 정답이순서대로 들어있는 배열 answer가 주어졌을 때,
* 가장 많은 문제를 맞힌 사람이 누구인지 배열에 담아 return하는 함수를 작성하기
* 응시자 3명
* (1) 1번 응시자의 패턴: [도, 레, 미, 파]
* 4개의 음계를 순차적으로 반복
* ex) 도,레,미,파,도,레,미,파,도,레,...
* (2) 2번 응시자의 패턴: [레, 레, 파, 파, 도, 도]
* 6개의 음계를 순차적으로 반복
* ex) 레,레,파,파,도,도,레,레,파,파,...
* (3) 3번 응시자의 패턴: [미, 파, 미, 도, 레, 도]
* 6개의 음계를 순차적으로 반복
* ex) 미,파,미,도,레,도,미,파,미,도,...
* 입력
* 배열 answer (ex. 도, 레, 미, 파, ... )
answer의 크기 N (0 ≤ N ≤ 5000)
answer의 값은 도, 레, 미, 파 중 하나
* 출력
* 가장 많은 문제를 맞힌 사람*/그런데 문제의 제한사항이 2가지가 있다.
제한사항
시험은 최대 10,000 문제로 구성되어있습니다.
문제의 정답은 1, 2, 3, 4, 5중 하나입니다.
가장 높은 점수를 받은 사람이 여럿일 경우, return하는 값을 오름차순 정렬해주세요.
제한사항
시험은 최대 5,000 문제로 구성되어있습니다.
가장 높은 점수를 받은 사람이 여럿일 경우, return하는 값을 오름차순 정렬해주세요.
정답이 1, 2, 3, 4, 5 ??
오타이신거죠제발오타라고해주세요
이건일단 제쳐두고 뒤를 쭉쭉 읽었다.
→ 매니저 님께 바로 질문드리니 첫번째 제한사항으로 풀라고 딱 정해주셨다. 근데 막상 문제를 풀어보니 직접 배열을 입력하는 경우라 중요하지 않은 부분이었음...(물론 실제 프로그램을 만들게 된다면 중요함!!!)
입력
- 우선 문제의 개수 N을 입력받는다.
- 도, 레, 미, 파 중 하나의 값이 N개의 정답 문자열로 / 공백으로 구분되어 / 주어짐.
여기서도 혼란2가 탄생한다.
해석 1. 입력받는 값은 개수 N 하나뿐이다.
이 경우 4가지 문자열 중 값을 랜덤하게 하나씩 가져와 배열로 만드는 과정이 필요하다.
해석 2. 문제의 개수 N도 입력받고 그 뒤에 answer도 입력받는다.
굳이요..?문제의 개수가 10,000개면 사용자가 10,000번 입력해야 하는데?
내가 너무 확대해석하는 것일 수도 있어서 제시된 예시 코드를 가져왔다.
public class Solution {
public int[] solution(String[] answers) {
int[] answer = {} ;
return answer;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
Solution solution = new Solution();
// 문제 개수 입력
int N = sc.nextInt();
// 정답 배열 입력
String[] answers = new String[N];
for(int i = 0; i < N; i++) {
answers[i] = sc.next();
}
// 결과 출력
int[] result = solution.solution(answers);
StringBuilder sb = new StringBuilder();
for(int i = 0; i < result.length; i++) {
sb.append(result[i]);
if(i < result.length - 1) {
sb.append(" ");
}
}
System.out.println(sb.toString());
}해석 2가 맞았다. 아직 테스트 단위라서 큰 정답 배열이 들어올 경우를 고려하지 않아도 되나보다.
정답 배열을 직접 입력받는 형태라면 문제가 쉽다. 바로 코딩 시작.
1. Element 설정
- 응시자 1, 2, 3의 패턴을 배열 형태로 정의
tester1 = {도, 레, 미, 파}
tester2 = {레, 레, 파, 파, 도, 도}
tester3 = {미, 파, 미, 도, 레, 도} - 입력받은 문자열을 공백을 기준으로 분리해 저장할 answer 배열
- 응시자 3인의 점수를 담을 score[3] 배열
2. 풀이 방법(접근 방법)
초기화
1) 입력된 N개의 answer 배열을 생성한다.
점수 계산 구현
2) answer 배열과 응시자들의 배열의 요소를 N개만큼 비교해간다.
- 완전탐색 + @ : 응시자들의 배열을 N개로 늘려서(패턴을 반복) 비교
→ 각 응시자의 배열이 N개로 늘어나 데이터 차지를 많이 한다. 비효율적 - 완전탐색 : 응시자의 배열[0]에서 [length-1]까지 비교를 계속 반복
→ 반복문이 겹쳐지겠지만 OK.
3) 배열의 요소 값이 일치하면 각 응시자의 score를 +1 한다.
결과 도출
4) 각 응시자의 score를 비교해 가장 큰 score를 가진 응시자를 반환한다.
3. 풀이 코드
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
public class Solution {
String[] tester1 = {"도", "레", "미", "파"};
String[] tester2 = {"레", "레", "파", "파", "도", "도"};
String[] tester3 = {"미", "파", "미", "도", "레", "도"};
public int[] solution(String[] answers) {
List<String[]> testers = new ArrayList<String[]>();
testers.add(tester1);
testers.add(tester2);
testers.add(tester3);
int[] score = new int[testers.size()]; //각 응시자의 점수 배열
ArrayList<Integer> pass = new ArrayList<>();
for (int i = 0; i < testers.size(); i++) {
for (int j = 0; j < answers.length; j++) {
if(testers.get(i)[j%testers.get(i).length].equals(answers[j]))
{score[i]++;}
}
}
int best = Math.max(Math.max(score[0], score[1]), score[2]); // 최고점수 best
for(int s = 1; s < score.length; s++) { //최고점을 가진 응시자 번호 추출
if(score[s-1]==best){ pass.add(s); }
}
int[] answer = new int[pass.size()];
for (int i = 0; i < pass.size(); i++) {
if(pass.get(i)==0){ continue; }
else answer[i] = pass.get(i);
}
return answer;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
Solution solution = new Solution();
// 문제 개수 입력
int N = sc.nextInt();
// 정답 배열 입력
String[] answers = new String[N];
for (int i = 0; i < N; i++) {
answers[i] = sc.next();
}
// 결과 출력
int[] result = solution.solution(answers);
StringBuilder sb = new StringBuilder();
for (int i = 0; i < result.length; i++) {
sb.append(result[i]);
if (i < result.length - 1) {
sb.append(" ");
}
}
System.out.println(sb.toString());
}
}- answer 배열의 크기를 동적으로 설정하고 싶어서 중간에 ArrayList pass를 추가해줬다.
이렇게 하면 result 배열이 출력될 때 0(최고점을 받지 못한 응시자)가 출력되지 않게 된다. - 응시자의 패턴 배열을 testers 라는 List으로 정리해 answers(입력된 문제 정답 배열)와 간단히 비교할 수 있도록 했다.
해설에서는 따로 List를 만들지 않고 3개의 if문을 사용했다.
추후 시간이 된다면 두 코드의 시간 복잡도를 계산해보는 것도 나쁘지 않겠다.
// 2.1. 모든 문제(answers 배열 길이)에 대해 반복 for(int i = 0; i < answers.length; i++) { // 2.2. 각 응시자별 점수 계산 // pattern[i % pattern.length]로 현재 답 확인하고 정답과 일치하면 점수 증가 if(answers[i].equals(pattern1[i % pattern1.length])) scores[0]++; // 1번 응시자 if(answers[i].equals(pattern2[i % pattern2.length])) scores[1]++; // 2번 응시자 if(answers[i].equals(pattern3[i % pattern3.length])) scores[2]++; // 3번 응시자 }
막상 다 풀고나니 왜 난이도가 '하'였는지 이해됐다. 역시 💩인지 된장인지 찍어먹어 봐야 아는 나답다.
수학 문제 풀듯이 매일 꾸준히 코딩 문제를 하나씩, 여러개씩 풀어보면서 알고리즘을 정복해봐야겠다.
