나의 풀이
public class NewRecruits {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
Map<Integer, Integer> rankings;
int T = Integer.parseInt(br.readLine());
for(int i = 0; i < T; i++) {
int N = Integer.parseInt(br.readLine());
rankings = new HashMap<>();
for(int j = 0; j < N; j++) {
int[] items = Arrays.stream(br.readLine().split(" ")).mapToInt(s -> Integer.parseInt(s)).toArray();
rankings.put(items[0], rankings.getOrDefault(items[0], 0) + items[1]);
}
int idx = 1;
int count = 1;
for(int k = 2; k < N + 1; k++) {
if(rankings.get(idx) > rankings.get(k)) {
count += 1;
idx = k;
}
}
sb.append(count).append("\n");
}
System.out.println(sb);
}
}-
우선 문제를 읽고 무슨말인지 몰라서 많이 해맸다. 결론적으로 두 점수의 순위 중에서 하나를 기준으로 오름차순 정렬을 하고, 나머지 점수로 도장깨기를 하면 되는 문제였다.
예를 들어 서류 순위(좌)와 면접 순위(우)가 입력 받는다.
그렇다면 서류 순위를 기준으로 정렬을 하고 서류 순위상 1위의 면접 순위를 기준으로 도장깨기를 시작한다고 가정한다.
1 3
2 4
3 2
4 1
5 5
2 4 는 1 3 의 면접 순위보다 낮기 때문에 탈락.
3 2 는 1 3 의 면접 순위보다 높기 때문에 통과. 새로운 기준으로 등록.
3 2
4 1
5 5
4 1 은 3 2 의 면접 순위보다 높기 때문에 통과. 새로운 기준으로 등록.
4 1
5 5
5 5 는 4 1 의 면접 순위보다 낮기 때문에 탈락. 비교 끝
이렇게 총 3명이 통과하게 되는 것이다.(1 3 은 1등이기 때문에 비교하지 않아도 통과 대상자이다) -
이런 식으로 접근하기 위해 맵을 사용하여 처음으로 입력 받는 순위를 키 값으로, 두 번째로 입력받는 순위를 밸류 값으로 두었다.
-
그 다음 키 값이 1인(1등) 이 기준이 되기 때문에 idx 변수를 1로 잡아주고, count도 1부터 세기 시작한다.
-
만약 키 값 1의 밸류보다 낮은 밸류를 가진 키 값이 있다면, idx 변수를 해당 키 값으로 바꿔주고 count를 올려준다. 이 과정을 모든 키 값을 조회할 때까지 반복한다.
-
반복이 끝나면 해당 count를 스트링 빌더에 추가해준다.
-
위 과정을 T번 반복하고 결과가 담긴 sb를 출력해준다.
다른 사람 풀이 & 느낀점
문제를 나름 단계적으로 풀고 있고 당연히 실력적으로 처음보다 향상됬겠지만, 난이도가 상대적으로 낮은 문제를 풀 때 지문을 읽고 이해가 안되서 벙찌는 일이 많아지는 것 같다.
다른 사람의 풀이를 찾아보니 Ranking 객체를 생성하여 객체지향적으로 접근하신 분도 계셨고, 그냥 1차 배열을 생성하여 1차 배열의 인덱스를 키 값으로 잡고, 해당 인덱스의 값을 밸류로 잡아서 더욱 심플하게 접근한 코드도 있었다.
for (int j = 0; j < N; j++){
st = new StringTokenizer(br.readLine());
int rank = Integer.parseInt(st.nextToken());
arr[rank] = Integer.parseInt(st.nextToken());
}이 경우 정렬을 하지 않아도 되므로 속도가 다른 코드에 비해 빨랐다.
