🧮 [프로그래머스] 명예의 전당(1) (JAVA)
문제
https://school.programmers.co.kr/learn/courses/30/lessons/138477
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
문제 이해 && 풀이
이 문제는 게임에서 원하는 순위만큼 점수를 저장하는 것이 중요하다.
k 는 순위를 저장하는 갯수
- 예를 들어 k가 3이라면 우리가 보는 순위는 1위, 2위, 3위가 되는것이다.
발표점수
- 순위안에 들어가있는 사람들 중 가장 낮은 점수
이렇게만 이해해도 문제를 푸는데는 문제가 없다. 발표점수는 나올때 마다 answer라는 배열에 집어넣을것이다.
풀이 1
가장 먼저 그냥 무대뽀로 풀었다. 다른분들은 ArrayList 를 사용했지만 나는 어차피 순위의 갯수가 정해져있기 때문에 List 로 구현하지 않아도 된다고 생각했다.
가장 먼저 순위를 다루는 배열 arr 를 만들어주고 각 배열에 Integer의 최대 숫자를 넣어주었다. 왜냐하면 나는 배열에 숫자를 막 넣을것인데 정렬은 된 상태여야 하기 때문에 0으로 기준이 잡혀있으면 처음에 들어간 숫자가 발표점수로 안나왔기 때문이다.
처음에 k개까지의 숫자를 그냥 순서대로 넣어주었다. 여기서 넣어줄때 마다 정렬을 해주고 가장 앞에 있는 값을 발표점수 배열에 넣어주었다. 여기서 중요한건 이렇게 하면 가장 낮은 점수는 자연스레 맨 앞인 arr[0]에 위치하고 그 값을 발표점수에 넣었다.
그리고 임의의 변수 j 가 k와 같아지면 이때부터 들어오는 점수는 가장 낮은 점수 arr[0]과 자리를 바꿔주기만 하면 된다.
여기서 변수는 기존의 가장 낮은 점수보다 낮은 점수인데 이는 그냥 arr[0]의 숫자를 다시 넣어주고 반복문으로 돌아가게 만들었다.
풀이 2
사실 이 문제는 보자마자 큐를 너무 사용하고 싶었다. 딱 보면 어느한 고정된 크기의 통이 있고 그곳으로 값이 들어오고 빠져나가고 있다. 심지어 가장 밑의 숫자가 빠져나가고 가장 큰 수는 맨 위에 있다. 그래서 더욱 사용하고 싶었다.
들어오는 구멍과 나가는 구멍이 다른 자료구조 큐를 사용하는 로직이다. 하지만 우리의 목적은 단순히 먼저 들어온 숫자를 빼내는 것이 아니라 우선순위를 두어야 하는 우선순위큐를 사용했다. 기본적으로 우선순위 큐는 작은 값을 가장 먼저 뽑아낸다.
때문에 주의할 점은 peek() 과 poll() 의 차이점을 주의하고 큐의 사이즈가 k의 값을 넘으면 가장 작은 값은 사라져야한다는 것이다.
peek() - 현재 가장 먼저 나오는 값을 출력
poll() - 현재 가장 먼저 나오는 값을 출력하고 삭제