개발자 Lim

<풀기 전 생각>

1. 필요한 튜플에 대한 정보가 주어진 문자열이 {}로 둘러싸인 구조 임으로 String의 indexOf() 함수를 사용하여 "{", "}" 중괄호의 인덱스를 일일이 구한 뒤 문자열의 배열로 분리

2. 그렇게 분리된 문자열 들을 Stream 클래스의 sort() 메서드를 통해 길이 순으로 정렬

3. Set을 사용하여 중복을 체크 하면서 튜플 생성

<중간 문제점>

 프로그래머스에서 Stream.toList() 메서드를 인식을 하지 않아서 고민 했었는데

import java.util.stream.Collectors;

import java.util.*;
import java.util.stream.Collectors;

class Solution {
    // 시간 복잡도 O(n*m) 공간 복잡도 O(n)
    public int[] solution(String s) {
        ArrayList<String> units = new ArrayList<String>();
        // 업 캐스팅 자식 타입 객체가 부모 객체로 형변환
        List<String> sortedUnits = new ArrayList<String>();
        String tmp = s.substring(1,s.length()-1);
        // 괄호를 제거한 튜플의 각 원소들을 리스트 형태로 추출
        units = getUnits(tmp);
        // 문자열 길이에 따른 정렬
        sortedUnits=units.stream().sorted(Comparator.comparing(String::length)).collect(Collectors.toList());

        return makeTuple(sortedUnits);
    }
    // 시간 복잡도 O(1) 공간 복잡도 O(n)
    private ArrayList<String> getUnits(String s){
        ArrayList<String> ans = new ArrayList<String>();
        int frontBraCapIndex = 0;
        int beforeBraCapIndex = 0;
        while(true){
            frontBraCapIndex=s.indexOf("{",frontBraCapIndex);
            beforeBraCapIndex=s.indexOf("}",beforeBraCapIndex);
            if(frontBraCapIndex==-1||beforeBraCapIndex==-1) break;
            ans.add(s.substring((frontBraCapIndex++)+1,beforeBraCapIndex++));
        }
        return ans;
    }
    // 시간 복잡도 O(n*m) 공간 복잡도 O(n)
    private int[] makeTuple(List<String> sortedUnits){
        int tuple[] = new int[sortedUnits.size()];
        HashSet<Integer> duplicateChecker = new HashSet<Integer>();
        int tupleIndex = 0;
        for (String unit:sortedUnits) {
            String numArray[] = unit.split(",");
            for (String num: numArray) {
                int transNum = Integer.parseInt(num);
                if(!duplicateChecker.contains(transNum))
                    tuple[tupleIndex++]=transNum;
                duplicateChecker.add(transNum);
            }
        }
        //System.out.println("test");
        return tuple;
    }
}

        String[] arr = s.replaceAll("[{]", " ").replaceAll("[}]", " ").trim().split(" , ");
        Arrays.sort(arr, (a, b)->{return a.length() - b.length();});

<풀기 전 생각>

중복을 허용하지 않는 다는 점에서 HashSet 자료구조를 사용하면 어떨까 생각이 들어 해당 자료구조를 사용하여

Set 을 사용
	if 기존에 없는 요소 접근
		if Set의 사이즈가 지정 크기를 벗어나면
    			맨앞의 요소를 삭제 Set에 해당 요소 추가
        	ans+5
	else 기존에 있는 요소 접근
		Set에 추가 ans+1

다음과 같은 방식으로 문제의 알고리즘을 생각했다. 

<결과 코드 (실패)>

import java.util.*;

class Solution {
    // 시간 복잡도 O(n) 공간 복잡도 O(1)
    private void deleteFirstFail(HashSet<String> cash){
        Iterator<String> it = cash.iterator();
        cash.remove(it.next());
    }
    public int solutionFail(int cacheSize, String[] cities) {
        int answer = 0;
        HashSet<String> cash = new HashSet<String>();
        for (String citie:cities) {
            String city = citie.toUpperCase();
            // 캐쉬에 없는 요소 접근
            if(!cash.contains(city)){
                if(cash.size()!=0&&cash.size()>=cacheSize)
                    deleteFirstFail(cash);
                answer+=5;
            }
            // 캐쉬에 있는 요소 접근
            else {
                cash.remove(city);
                answer++;
            }
            // 공통되는 부분이므로 밖으로 빼냄
            cash.add(city);
        }
        return answer;
    }
}

<중간 문제점>

Set은 순서를 보장해주지 않는다는 것을 순서를 보장해주는 것으로 착각한 상태 였기 때문에 해당 풀이는 완전히 틀린 풀이가 되었다. 그래서 위에서 고안한 Set을 가장 오래 사용되지 않던 도시를 캐쉬에서 제거한다는 문제의 설명이 떠올라 자료구조 Queue을 Set과 대신 사용하는 방식으로 다시 접근 하게 되었다.

<최종 코드>

import java.util.*;

class Solution {
    // 시간 복잡도 O(n^2) LinkedList.contains의 시간 복잡도는 O(n)이기 때문
    // 공간 복잡도 O(1)
    public int solution(int cacheSize, String[] cities) {
        // 캐쉬 사이즈 0일 때의 예외 처리
        if(cacheSize==0)
            return cities.length*5;

        int answer = 0;
        Queue<String> cash = new LinkedList<String>();
        for (String citie:cities) {
            String city = citie.toUpperCase();
            // 캐쉬에 없는 요소 접근
            if(!cash.contains(city)){
                if(cash.size()!=0&&cash.size()>=cacheSize)
                    cash.remove();
                answer+=5;
            }
            // 캐쉬에 있는 요소 접근
            else
                answer++;
			// 공통적인 부분이므로 바깥으로 빼냄
            cash.offer(city);
        }
        return answer;
    }
}

 <메모>

다른 사람들의 풀이를 살펴본 결과 해당 방식으로 애초에 해당 문제에 최적화된 자료구조를 만들어서 풀이 한 걸 볼 수 있었는데 참고 해둘 필요가 있어 보인다.

class LRU<K, V> extends LinkedHashMap<K, V>