명예의 전당
이 프로그램에서는 매일 "명예의 전당"의 최하위 점수를 발표합니다. 예를 들어, k = 3이고, 7일 동안 진행된 가수의 점수가 [10, 100, 20, 150, 1, 100, 200]이라면, 명예의 전당에서 발표된 점수는 아래의 그림과 같이 [10, 10, 10, 20, 20, 100, 100]입니다.명예의 전당 목록의 점수의 개수 k, 1일부터 마지막 날까지 출연한 가수들의 점수인 score가 주어졌을 때, 매일 발표된 명예의 전당의 최하위 점수를 return하는 solution 함수를 완성해주세요.
대충 주마다 1명씩 등장하는 경연 프로그램의 랭킹 시스템인가보다. 주마다 k등을 리턴하는 문제인데, queue로 풀 수 있을까 했다가 2등에 새로운 사람이 등록되는 문제 때문에 다른 방식으로 고민했다.
풀이 방법
배열 크기만큼 반복하면서 반복문 내부에 이런 방법으로 알고리즘을 구현하였다.
- String 리스트에 하나씩 추가한다.
- 리스트를 내림차순 정렬한다.
- k개가 넘어가면 마지막 값을 리스트에서 제거한다. (k+1등부터 랭킹 X)
- 리스트의 끝 값을 저장한다.
스택의 느낌으로 요소를 넣고 정렬해서 끝의 값을 빼는 방식으로 구현하였다. 중간에 정렬할때 실행시간이 늘어날 것이 걱정되긴 했다.
import java.util.Arrays;
import java.util.Collections;
import java.util.ArrayList;
class Solution {
public int[] solution(int k, int[] score) {
ArrayList<Integer> rank = new ArrayList<>(); // rank의 꼬리를 리턴
ArrayList<Integer> result = new ArrayList<>();
for(int i = 0; i < score.length; i++){
rank.add(score[i]); // 당일 점수 추가
Collections.sort(rank, Collections.reverseOrder()); // 오름차순 정렬
if(rank.size() > k){
rank.remove(k);
}
result.add(rank.get(rank.size()-1)); // 꼬리 저장
}
return result.stream().mapToInt(Integer::intValue).toArray();
}
}풀고나서 다른 사람의 풀이를 봤는데 우선순위 큐(PriorityQueue)를 사용한 것이 보였다.
Queue에 값을 넣으면 이진 트리로 저장하면서 알아서 정렬해준다고 하는데, 코드가 훨씬 간결해질 것 같았다.
[1] 비밀지도
네오는 평소 프로도가 비상금을 숨겨놓는 장소를 알려줄 비밀지도를 손에 넣었다. 그런데 이 비밀지도는 숫자로 암호화되어 있어 위치를 확인하기 위해서는 암호를 해독해야 한다. 다행히 지도 암호를 해독할 방법을 적어놓은 메모도 함께 발견했다.
지도는 한 변의 길이가 n인 정사각형 배열 형태로, 각 칸은 "공백"(" ") 또는 "벽"("#") 두 종류로 이루어져 있다.
전체 지도는 두 장의 지도를 겹쳐서 얻을 수 있다. 각각 "지도 1"과 "지도 2"라고 하자. 지도 1 또는 지도 2 중 어느 하나라도 벽인 부분은 전체 지도에서도 벽이다. 지도 1과 지도 2에서 모두 공백인 부분은 전체 지도에서도 공백이다.
"지도 1"과 "지도 2"는 각각 정수 배열로 암호화되어 있다.
암호화된 배열은 지도의 각 가로줄에서 벽 부분을 1, 공백 부분을 0으로 부호화했을 때 얻어지는 이진수에 해당하는 값의 배열이다.
문제에 첨부된 사진을 보면 이해가 한번에 가는 문제이다.
입력받은 값을 이진수로 변환해서 0이면 공백, 1이면 #이 되게 출력하라는 것 같다. 문제는 두개의 배열을 곂쳐야 하는 것인데, 잠깐 고민하다가 1만 남으면 되니까 or 연산자로 처리했다.
import java.util.*;
class Solution {
public String[] solution(int n, int[] arr1, int[] arr2) {
ArrayList<String> binaryArr = new ArrayList<>();
for(int i = 0; i < n; i++){
String binary = Integer.toBinaryString(arr1[i] | arr2[i]);
binary = "0".repeat(n-binary.length()) + binary; // 지도의 크기에 맞춰야함
String map = "";
for(int j = 0; j < n; j++){
map = map + (binary.charAt(j) == '0' ? " " : "#");
}
binaryArr.add(map);
}
return binaryArr.toArray(new String[0]);
}
}연산자 찾아보면서 Integer.toBinaryString()도 함께 찾아서 사용해보았다. 이전에 이진수 연산 때문에 고민이 많았는데 꽤 간단하게 풀리니 신기했다.
