![[프로그래머스,Level 1] 실패율(JAVA 구현)](https://img1.daumcdn.net/thumb/R750x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdn%2FnuYo6%2FbtqSPFWQf0k%2F0Yk9uACG4M6mRmsUsAwjVk%2Fimg.png)
- 첫 풀이 및 정답풀이
문제의 지문이 길지만, 문제 자체는 상당히 간단하다. 사용자들이 위치한 스테이지 정보가 담긴 stages배열이 주어지며, 최대 스테이지 수로 N이 주어진다. 실패율 = 한 스테이지에 위치한 사용자 수 / 한 스테이지에 도달한 사용자 수라는 정의를 이용하게 된다. 필자는 이를 우선 1번 예제를 토대로 표를 그려보았으며, 아래가 그 표이다.
| 스테이지 | 막힌 사용자 | 해당 스테이지를 도달한 사용자 수 |
| 1 | 1 | 8 |
| 2 | 3 | 7 |
| 3 | 2 | 4 |
| 4 | 1 | 2 |
| 5 | 0 | 1 |
막힌 사용자 수는 stages 배열의 원소로 주어진 정수들을 카운팅 하면 구할 수 있고, 해당 스테이지를 도달한 사용자 수는 막힌 스테이지가 해당 스테이지보다 높다면 이미 도달한 것이기 때문에 그 수를 카운팅 하면 된다. 표를 보면 알 수 있듯이, 실패율은 막힌 사용자 / 해당 스테이지를 도달한 사용자 수로 구할 수 있다. 이것을 바탕으로 2차원 배열을 이용해 자료를 담는 코드는 아래와 같다.
class Solution {
public int[] solution(int N, int[] stages) {
int[] answer = new int[N];
// 1. 실패율 저장을 위해 double형, 각 스테이지와 실패율 매칭을 위해 1개의 열을 더 추가한다.
double[][] cnt = new double[N+1][3];
// 2. stages 탐색, 현재 스테이지가 N+1인 경우는 고려할 필요가 없다.
for(int i = 0 ; i<stages.length;i++){
if(stages[i]>N) continue;
// 2-1. 각 스테이지 별 막힌 사용자 수를 증가.
cnt[stages[i]][0]++;
}
// 3. 1스테이지를 도달한 사용자 수는 전체 사용자 수와 같으며, 1번 인덱스의 3번째 열에 스테이지를 매칭시킨다.
cnt[1][1] = stages.length;
cnt[1][2] = 1;
// 4. 2번 인덱스부터 반복.
for(int i = 2; i<cnt.length;i++){
// 4-1. 각 스테이지에 도달한 사람의 수 = 이전 스테이지에 도달한 사람 수 - 이전 스테이지에 막힌 사람 수
cnt[i][1] = (int)(cnt[i-1][1] - cnt[i-1][0]);
// 4-2. 인덱스 별 스테이지 정보를 매칭시킨다.
cnt[i][2] = i;
}1. 위의 표는 2개의 열을 고려하지만, 3개의 열을 선언한 이유는 주석으로도 작성해 놓았듯이 이 2차원 배열을 재활용해 실패율을 저장하고, 이 실패율을 각 스테이지와 매칭 시키기 위함이다.
2. stages 배열에 주어진 원소를 탐색해, 각 스테이지에 막힌 사용자 수를 2차원 배열의 0번 열에 저장하며, 모든 스테이지를 클리한 사람은 고려할 필요가 없으므로 continue
3. 문제에서 알 수 있듯이, stages로 주어지는 원소들의 최솟값은 1이다. 이 말은 모든 사용자는 최소 1번 스테이지는 모두 도달할 수 있기 때문에 1번 스테이지에 도달한 사람의 수 = stages.length가 성립된다. 또한 1번 인덱스에 스테이지 정보를 매칭 시킨다.
4. 2번 인덱스부터 반복하며, 2 스테이지에 도달한 사람의 수 = 이전 스테이지에 도달한 사람의 수 - 이전 스테이지에 머물러 있는 사람의 수로 구할 수 있다. 이전 스테이지를 클리어 못했으므로 해당 사람 수만큼 감소하는 것이다. 또한 마찬가지로 각 인덱스 별로 각 스테이지 정보를 2차원 배열의 2번 열에 저장한다.
여기까지 수행한 결과를 위의 표를 조금 수정해서 나타내면 아래와 같다.
| 스테이지 (2차원 배열의 행 인덱스) |
막힌 사용자 수 | 해당 스테이지를 도달한 사용자 수 |
스테이지 정보 |
| 1 | 1 | 8 | 1 |
| 2 | 3 | 7 | 2 |
| 3 | 2 | 4 | 3 |
| 4 | 1 | 2 | 4 |
| 5 | 0 | 1 | 5 |
이렇게 정보를 저장한 2차원 배열을 이용해 각 스테이지 별 실패율을 2차원 배열의 0번 열을 활용해 저장한다. 이와 관련된 코드는 아래와 같다.
// 5. 2차원 배열을 탐색한다.
for(int i = 1; i<cnt.length;i++){
// 5-1. 각 스테이지에 도달한 사람이 없을 경우, 실패율은 0이다.
if(cnt[i][1] == 0) {
cnt[i][0] = 0;
continue;
}
// 5-2. 문제의 정의에 따라 실패율을 0번 열에 저장한다.
cnt[i][0] = cnt[i][0]/cnt[i][1];
}여기서 주의해야 할 점은 각 스테이지에 도달한 사람이 없는 경우이다. 이는 실패율을 0으로 저장해주어야 하며 나머지는 정의에 맞게 공식을 작성해주면 된다. 이를 표로 나타내면 아래와 같다.
| 스테이지 (2차원 배열의 행 인덱스) |
막힌 사용자 수 | 해당 스테이지를 도달한 사용자 수 |
스테이지 정보 |
| 1 | 1/8 | 8 | 1 |
| 2 | 3/7 | 7 | 2 |
| 3 | 2/4 | 4 | 3 |
| 4 | 1/2 | 2 | 4 |
| 5 | 0/1 | 1 | 5 |
이렇게 구한 실패율을 문제에서 제시하는 것처럼 내림차순으로 정렬을 한다. 2차원 배열을 특정 기준을 통해 정렬하기 위해 Comparator 인터페이스를 오버 라이딩하여 구현한다.
// 6. Comparator 인터페이스의 compare 메소드 구현.
Arrays.sort(cnt,new Comparator<double[]>(){
@Override
public int compare(double[] o1,double[] o2){
// 6-1. 2차원 배열에서 고려하지 않는 0번 인덱스는 무시하기 위해 작성.
if(o1[2] == 0 || o2[2] == 0 ) return 0;
// 6-2. 실패율이 같다면, 스테이지를 오름차순으로 정렬한다.
if(o1[0] == o2[0]) return Double.compare(o1[2],o2[2]);
// 6-3. 나머지는 실패율에 따라 내림차순 정렬한다.
else return Double.compare(o2[0],o1[0]);
}
});여기서는 기존의 2차원 배열에서 사용하지 않는 0번 인덱스를 무시하기 위해 조건을 추가해주고 실패율이 같을 때는 스테이지를 기준으로 오름차순 정렬, 나머지의 경우는 실패율에 따라 내림차순 정렬을 수행한다. 이를 수행한 결과는 아래 표와 같다.
| 스테이지 (2차원 배열의 행 인덱스) |
막힌 사용자 수 | 해당 스테이지를 도달한 사용자 수 |
스테이지 정보 |
| 1 | 2/4 | 4 | 3 |
| 2 | 1/2 | 2 | 4 |
| 3 | 1/8 | 8 | 1 |
| 4 | 3/7 | 7 | 2 |
| 5 | 0/1 | 1 | 5 |
이제 마지막으로 정렬된 스테이지 정보를 answer 배열에 담아 반환하면 된다.
// 7. 정렬된 스테이지 정보 저장.
for(int i = 1; i<cnt.length;i++){
answer[i-1] = (int)cnt[i][2];
} 전체 코드는 아래.
import java.util.Arrays;
import java.util.Comparator;
class Solution {
public int[] solution(int N, int[] stages) {
int[] answer = new int[N];
// 1. 실패율 저장을 위해 double형, 각 스테이지와 실패율 매칭을 위해 1개의 열을 더 추가한다.
double[][] cnt = new double[N+1][3];
// 2. stages 탐색, 현재 스테이지가 N+1인 경우는 고려할 필요가 없다.
for(int i = 0 ; i<stages.length;i++){
if(stages[i]>N) continue;
// 2-1. 각 스테이지 별 막힌 사용자 수를 증가.
cnt[stages[i]][0]++;
}
// 3. 1스테이지를 도달한 사용자 수는 전체 사용자 수와 같으며, 1번 인덱스의 3번째 열에 스테이지를 매칭시킨다.
cnt[1][1] = stages.length;
cnt[1][2] = 1;
// 4. 2번 인덱스부터 반복.
for(int i = 2; i<cnt.length;i++){
// 4-1. 각 스테이지에 도달한 사람의 수 = 이전 스테이지에 도달한 사람 수 - 이전 스테이지에 막힌 사람 수
cnt[i][1] = (int)(cnt[i-1][1] - cnt[i-1][0]);
// 4-2. 인덱스 별 스테이지 정보를 매칭시킨다.
cnt[i][2] = i;
}
// 5. 2차원 배열을 탐색한다.
for(int i = 1; i<cnt.length;i++){
// 5-1. 각 스테이지에 도달한 사람이 없을 경우, 실패율은 0이다.
if(cnt[i][1] == 0) {
cnt[i][0] = 0;
continue;
}
// 5-2. 문제의 정의에 따라 실패율을 0번 열에 저장한다.
cnt[i][0] = cnt[i][0]/cnt[i][1];
}
// 6. Comparator 인터페이스의 compare 메소드 구현.
Arrays.sort(cnt,new Comparator<double[]>(){
@Override
public int compare(double[] o1,double[] o2){
// 6-1. 2차원 배열에서 고려하지 않는 0번 인덱스는 무시하기 위해 작성.
if(o1[2] == 0 || o2[2] == 0 ) return 0;
// 6-2. 실패율이 같다면, 스테이지를 오름차순으로 정렬한다.
if(o1[0] == o2[0]) return Double.compare(o1[2],o2[2]);
// 6-3. 나머지는 실패율에 따라 내림차순 정렬한다.
else return Double.compare(o2[0],o1[0]);
}
});
// 7. 정렬된 스테이지 정보 저장.
for(int i = 1; i<cnt.length;i++){
answer[i-1] = (int)cnt[i][2];
}
return answer;
}
}지금까지 풀었던 level 1 문제들 중 가장 오래 걸렸던 것 같다..