Problem

마라톤에 참여한 선수들의 명단과 완주한 선수들의 명단이 주어졌을 때

 

완주하지 못한 선수의 이름을 구하는 문제입니다.

 

단, 동명이인이 존재할 수 있습니다.

 

 

Solution

HashMap 을 사용하면 됩니다.

 

{ "이름": "인원수" } 의 key-value 형식을 갖게 선언해서 완주한 사람들을 전부 넣습니다.

 

그리고 participant 를 순회하면서 key 값이 존재하면 인원수를 하나씩 빼줍니다.

 

만약 인원수가 음수가 된다면 그 사람이 완주하지 못한 선수입니다.

 

 

Java Code

import java.util.*;

class Solution {
    public String solution(String[] participant, String[] completion) {
        HashMap<String, Integer> map = new HashMap<>();
        
        for (String person : completion) {
            map.put(person, map.getOrDefault(person, 0) + 1);
        }
        
        for (String person : participant) {
            map.put(person, map.getOrDefault(person, 0) - 1);
            
            if (map.get(person) < 0)
                return person;
        }
        
        return "";
    }
}

 

Problem


LRU 캐시 교체 알고리즘(Least Recently Used)을 구현하면 됩니다.



Solution

LRU 알고리즘이란 가장 오랫동안 사용되지 않은 데이터를 교체하는 겁니다.


크기가 3 인 캐시에 [1, 2, 3, 1] 순서로 데이터가 들어갔다면 1 이 가장 오래된 데이터지만 가장 오랫동안 사용되지 않은 데이터는 2 입니다.


따라서 새로운 데이터 4 가 들어간다면 2 를 삭제하고 [3, 1, 4] 가 남게 됩니다.


LinkedHashSet 자료구조를 사용하여 구현하였습니다.


LinkedHashSet 은 HashSet 과 동일하게 삽입/검색/삭제 시간복잡도가 O(1) 이지만 내부적으로 연결리스트를 사용하여 순서가 보장됩니다.


캐시 안에 이미 도시 이름이 존재하면 기존에 있는 걸 삭제 후 다시 add 하여 갱신해줍니다.


캐시 안에 도시 이름이 존재하지 않으면 새로 추가합니다.


set.size() 가 cacheSize 를 넘어버린다면 가장 오랫동안 사용되지 않은 값을 삭제합니다.


삽입/삭제 구현 방식에 따라서 LinkedHashSet 의 첫번째 인덱스가 사용되지 않은 값이므로 set.iterator().next() 를 통하여 데이터를 가져와 삭제합니다.



Java Code

import java.util.*;

class Solution {
    public int solution(int cacheSize, String[] cities) {
        int answer = 0;
        
        if (cacheSize == 0) {
            return cities.length * 5;
        }
        
        Set<String> cache = new LinkedHashSet<>();
        
        for (String city : cities) {
            city = city.toLowerCase();
            
            if (cache.contains(city)) {
                cache.remove(city);
                answer += 1;
            } else {
                answer += 5;
            }
            
            cache.add(city);
            
            if (cache.size() > cacheSize) {
                String oldest = cache.iterator().next();
                cache.remove(oldest);
            }
        }

        return answer;
    }
}


Problem


주어지는 두개의 지도를 겹친 결과를 출력하는 문제입니다.



Solution

그림만 봐도 알수 있듯이 겹치는 부분은 # 겹치지 않은 부분은 빈칸으로 나옵니다.


친절하게 비트로 풀라고 안내까지 해주고 있으니 Integer.toBinaryString 함수를 사용하여 계산을 해줍니다.


1 과 0 으로 이루어진 String을 replaceAll로 전부 바꿔주면 됩니다.


한 가지 주의할 점이 하나 있습니다.


1111(2) 처럼 자릿수가 작은 글자는 n이 5일때 01111로 바꿔주어야 합니다.


여기서는 자리수를 맞춰주는 String.format 함수를 사용하여 n 자리만큼 공백으로 채워줍니다.



Java Code

class Solution {
    static public String[] solution(int n, int[] arr1, int[] arr2) {
        String[] answer = new String[n];

        for (int i=0; i<n; i++) {          
            String temp = Integer.toBinaryString(arr1[i] | arr2[i]);  
            temp = String.format("%" + n + "s", temp);
            temp = temp.replaceAll("1", "#");
            temp = temp.replaceAll("0", " ");
            answer[i] = temp;
        }

        return answer;
    }
}


+ Recent posts