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 "";
    }
}

 

저작자표시 비영리

'알고리즘 문제 > Programmers' 카테고리의 다른 글

[프로그래머스] 체육복 (Java)  (1) 2020.03.27
[프로그래머스] 위장 (Java)  (0) 2019.11.26
[프로그래머스] 전화번호 목록 (Java)  (0) 2019.11.26
2018 KAKAO BLIND 캐시 (Java)  (0) 2019.09.06
2018 KAKAO BLIND 비밀지도 (Java)  (0) 2019.09.06

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;
    }
}


저작자표시 비영리

'알고리즘 문제 > Programmers' 카테고리의 다른 글

[프로그래머스] 체육복 (Java)  (1) 2020.03.27
[프로그래머스] 위장 (Java)  (0) 2019.11.26
[프로그래머스] 전화번호 목록 (Java)  (0) 2019.11.26
[프로그래머스] 완주하지 못한 선수 (Java)  (0) 2019.11.26
2018 KAKAO BLIND 비밀지도 (Java)  (0) 2019.09.06

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;
    }
}


저작자표시 비영리

'알고리즘 문제 > Programmers' 카테고리의 다른 글

[프로그래머스] 체육복 (Java)  (1) 2020.03.27
[프로그래머스] 위장 (Java)  (0) 2019.11.26
[프로그래머스] 전화번호 목록 (Java)  (0) 2019.11.26
[프로그래머스] 완주하지 못한 선수 (Java)  (0) 2019.11.26
2018 KAKAO BLIND 캐시 (Java)  (0) 2019.09.06

+ Recent posts

티스토리툴바