정렬
프로그래머스 2019 KAKAO BLIND RECRUITMENT Level 1 문제인 실패율을 Java를 이용해 풀어보았다.
처음에 맞왜틀을 계속 시전하다가 나중에 너무 기초적인 실수를 한 걸 깨닫고 내 자신이 한심했다.
문제 링크 첨부한다.
https://programmers.co.kr/learn/courses/30/lessons/42889
스테이지별로 몇 명 츄라이했는지
나는 먼저 각 스테이지별로 실패한 인원만을 쭉 받았는데 여기서 간단한 조건 하나만 추가해서 몇 명이 츄라이했는지도 구했다.
아래 코드를 살펴보며 설명하겠다.
int[] howManyTried = new int[N+1];
int[] howManyFailed = new int[N+1];
for(int stage: stages){
int tries = stage;
if(tries==N+1) tries = N; // N+1 에서 실패했다는 건 다 통과했다는 뜻, 따라서 막 스테이지에 츄라이 인원 추가
howManyTried[tries]++;
if(stage<=N) howManyFailed[stage]++;
}주어진 stages 배열을 linear하게 쭉 돌며 특정 스테이지에서 실패했다는 건 곧 그 스테이지를 시도했다는 뜻도 되기 때문에 위와 같이 작성했다. 단, stage 값이 N+1이라는 건 막 스테이지를 시도했고 통과했다는 뜻이므로 howManyTried에는 추가해주고 howManyFailed에는 추가하지 않았다.
이렇게 두 배열을 쭉 받은 후에 howManyTried를 좀 손봐야 한다.
실제 츄라이한 인원 수와 현재의 howManyTried의 원소값들은 다르다.
스테이지 1 츄라이 인원수는 스테이지 1~N 까지의 howManyTried의 값들을 다 더해줘야 하며, 스테이지 2 츄라이 인원수는 스테이지 2~N 까지의 howManyTried의 값들을 다 더해줘야 한다. 즉, 거꾸로 오며 누적합을 구해서 각 스테이지 별 츄라이 인원수를 갱신해주면 된다.
이를 위한 코드는 아래와 같다.
int sum = 0;
for(int i=N; i>=1; i--){
sum += howManyTried[i]; // 누적합
howManyTried[i] = sum;
}이렇게 각 스테이지별로 총 몇 명이 시도했고, 몇 명이 실패했는지 알게 됐다.
리스트 생성 후 조건대로 정렬해주기
각 스테이지별 실패율을 스테이지 번호와 함께 저장해줘야 하므로 이를 위한 클래스를 작성했다.
static class FailureInfo{
int stage; // 스테이지 번호
float fail; // 실패율
FailureInfo(int stage, float fail){
this.stage = stage;
this.fail = fail;
}
Integer getStage(){ return stage;}
Float getFail(){ return fail; }
}스테이지 1~N 까지 위에서 구한 howManyTried와 howManyFailed 배열을 통해 리스트를 작성하자.
LinkedList<FailureInfo> list = new LinkedList<>();
for(int i=1; i<=N; i++)
list.add(new FailureInfo(i, howManyTried[i] != 0 ?
(float)howManyFailed[i]/(float)howManyTried[i] : 0));여기서 내가 실수한 부분이 나온다. 실패수/시도수 를 계산해줄 때 분모인 howManyTried[i]가 0일 경우를 생각하지 않은 것이다.
그래서 위의 코드에는 수정 후의 코드인데, 처음에는 삼항 연산자 없이 그냥 분모 0일 때도 냅다 계산해서 넣었었다.
Comparator 이용해서 정렬해주기
이제 정렬만 남았다. 정렬은 내가 처음 사용해본 메소드로 해봤다. 매우 편리한 것 같다. FailureInfo라는 클래스를 따로 선언해서 코드를 작성했기 때문에 가능했다.
.comparing()과 .thenComparing을 이용해서 정렬했는데 매우 편리하다. 앞으로도 기억해뒀다 필요할 때 써야지.
list.sort(Comparator.comparing(FailureInfo::getFail).reversed().
thenComparing(FailureInfo::getStage));먼저 실패율 기준 내림차순으로 정렬해주고 스테이지 별로 오름차순 정렬을 해주면 문제에서 제시한 두 가지 조건에 모두 부합한다!
아래는 내가 제출한 전체 코드다.
import java.io.*;
import java.util.Comparator;
import java.util.LinkedList;
public class FailureRate {
static int[] solution(int N, int[] stages) {
int[] answer = new int[N];
int[] howManyTried = new int[N+1];
int[] howManyFailed = new int[N+1];
for(int stage: stages){
int tries = stage;
if(tries==N+1) tries = N; // N+1 에서 실패했다는 건 다 통과했다는 뜻, 따라서 막 스테이지에 츄라이 인원 추가
howManyTried[tries]++;
if(stage<=N) howManyFailed[stage]++;
}
int sum = 0;
for(int i=N; i>=1; i--){
sum += howManyTried[i];
howManyTried[i] = sum;
}
LinkedList<FailureInfo> list = new LinkedList<>();
for(int i=1; i<=N; i++)
list.add(new FailureInfo(i, howManyTried[i] != 0 ? (float)howManyFailed[i]/(float)howManyTried[i] : 0));
list.sort(Comparator.comparing(FailureInfo::getFail).reversed().thenComparing(FailureInfo::getStage));
for(int i=0; i<N; i++) answer[i] = list.get(i).stage;
return answer;
}
static class FailureInfo{
int stage;
float fail;
FailureInfo(int stage, float fail){
this.stage = stage;
this.fail = fail;
}
Integer getStage(){ return stage;}
Float getFail(){ return fail; }
}
public static void main(String args[]) throws IOException {
BufferedWriter bfw = new BufferedWriter(new OutputStreamWriter(System.out));
int n = 5;
int[] stages = { 1,2,2,1,3 };
for(int a: solution(n, stages)) bfw.write(a + " ");
bfw.close();
}
}오늘 배운 것
- 나눗셈은 분모가
0이면 안되자나. 초등학교는 나왔고?Comparator의.comparing()을 사용해보았다!
