개발자 김수진

[풀이]

우선순위를 기반으로 베스트 앨범에 들어갈 노래를 골라주면 된다.

1. 장르별 총 재생 수 기준 정렬

2. 각 장르별로 상위 2개의 노래 선택

장르별 총 재생 수를 저장하기 위해 totalPlays 라는 map을 선언했다. 

해당 map의  key는 장르, value는 총 재생횟수가 된다.

totalPlays에 값을 넣어줄 때는 getOrDefault 함수를 사용해

현재 genre에 해당하는 값이 존재하면 그 값을 가져오고, 

존재하지 않는다면 defaultValue인 0을 가져와 play 횟수를 더해준 값을 put 하도록 하였다.

또한 각 장르별 play를 관리하기 위해 genreInfo 라는 map을 선언했다.

마찬가지로 해당 map의 key는 genre 값이 되고, value로는 또 하나의 map이 된다.

value로 존재하는 map의 key는 고유 번호인 index 값, value는 해당 노래의 재생 횟수인 play를 저장한다.

이를 통해 genreInfo에서는 각 장르별 재생된 노래의 정보를 관리하고 있다.

genreInfo에 값을 넣어줄 때는 value가 HashMap이기 때문에 

key에 해당하는 값이 존재하는지 확인 후 존재하지 않는다면 새로운 map을 할당하고 put을 수행한다.

장르별 총 재생 횟수를 기준으로 노래를 선발하기 위해

장르별 총 재생횟수 값이 존재하는 totalPlays를 정렬해줘야 한다.

이 때 List와 같은 컬렉션(Collection) 타입 데이터를 정렬하는데 사용되는 Collections.sort를 사용했다.

List<String> keySet = new ArrayList(totalPlays.keySet());
Collections.sort(keySet, (o1 , o2) -> totalPlays.get(o2) - totalPlays.get(o1));

totalPlays.keySet()를 통해 map의 모든 key 값을 가져와 ArrayList 형태로 변환해준다.

• Set은 정렬이 불가능하지만, List는 정렬이 가능하기 때문

Collections.sort는 주어진 List를 특정 조건에 따라 정렬 가능하다.

• 정렬 조건은 map의 두 키 o1과 o2의 value인 (totalPlays.get(o1)과 totalPlays.get(o2))을 기준으로 한다.
• (o1, o2) -> totalPlays.get(o2) - totalPlays.get(o1)는 내림차순 정렬을 나타낸다.
  • totalPlays.get(o2)이 더 크다면 음수를 반환해 o2가 먼저 오도록 정렬.
  • totalPlays.get(o1)이 더 크다면 양수를 반환해 o1이 나중에 오도록 정렬.

Java의 Comparator는 정렬 기준을 정의할 때 조건이 양수를 반환할 경우 o1이 o2보다 뒤에 가게 된다.

정렬된 map을 기반으로 순회하며 앨범에 넣을 곡을 선택한다.

장르 내에서 가장 많이 재생된 노래를 넣기 위해 다시 정렬을 수행한다.

List<Integer> sortedMap = new ArrayList(map.keySet());
Collections.sort(sortedMap, (o1 , o2) -> map.get(o2) - map.get(o1));

여기서의 map 변수에는 genre에 해당하는 곡들의 정보가 존재하는데

key는 곡의 고유번호가 되고, value는 해당 곡의 재생 횟수가 된다.

마찬가지로 key 값에 해당하는 값을 가져와 ArrayList로 변환하여 정렬을 수행한다.

key 값들을 가져와 key에 해당하는 value를 기준으로 map을 내림차순 정렬한다.

정렬된 값을 기반으로 index에 해당하는 map의 key 값을 answer에 넣어주면 된다.

[코드]

import java.util.*;

class Solution {
    public int[] solution(String[] genres, int[] plays) {
        ArrayList<Integer> answer = new ArrayList<>();

        int len = genres.length;
        Map<String, Integer> totalPlays = new HashMap<>();
        //key : genre, value < Key : idx, value : play>>
        Map<String, HashMap<Integer , Integer>> genreInfo = new HashMap<>();

        for(int idx =0 ; idx<len ; idx++){
            String genre = genres[idx];
            int play = plays[idx];
            if(!genreInfo.containsKey(genre)) {
                HashMap<Integer, Integer> map = new HashMap<>();
                map.put(idx, play);
                genreInfo.put(genre, map);
            } else {
                genreInfo.get(genre).put(idx , play);
            }
            totalPlays.put(genre, totalPlays.getOrDefault(genre, 0) + play);
        }

        List<String> keySet = new ArrayList(totalPlays.keySet());
        //  map을 value 기준으로 정렬
        Collections.sort(keySet, (o1 , o2) -> totalPlays.get(o2) - totalPlays.get(o1));

        for(String key : keySet) {
            Map<Integer, Integer> map = genreInfo.get(key);

            List<Integer> sortedMap = new ArrayList(map.keySet());
            Collections.sort(sortedMap, (o1 , o2) -> map.get(o2) - map.get(o1));

            answer.add(sortedMap.get(0));
            if(sortedMap.size() > 1) {
                answer.add(sortedMap.get(1));
            }
        } 
        return answer.stream().mapToInt(i -> i).toArray();
    }
}

[문제]

https://school.programmers.co.kr/learn/courses/30/lessons/42579

[풀이]

문제는 각 선수 간의 경기 결과를 통해 명확히 순위를 알 수 있는 선수의 수를 구하는 것이다.

플로이드 워셜 알고리즘을 이용해 모든 선수 간의 관계를 구하고, 승패 관계를 기반으로 순위를 계산해준다.

아래 3단계를 통해 순위를 알 수 있는 선수의 수를 구했다.

1. 승패 관계 초기화

• graph 라는 2차원 배열을 선언해 선수 간의 승패 여부를 관리
• i가 j를 이기면 graph[i][j]가 1, 지면 graph[i][j]가 -1

2. 플로이드 워셜 알고리즘

• 중간 노드를 거쳐 갈 수 있는 승패 관계를 업데이트 한다.
• 예를 들어, A → B, B → C라면 A → C 관계를 유추할 수 있다.

3. 순위 확정

• 한 선수에 대해 승리한 선수와 패배한 선수의 합이 n-1이면 해당 선수의 순위를 알 수 있다.

[코드]

class Solution {
    public int solution(int n, int[][] results) {
        int[][] graph = new int [n+1][n+1];
        int answer = 0;
        for(int [] res : results) {
            int winner = res[0];
            int loser = res[1];
            graph[winner][loser] = 1;
            graph[loser][winner] = -1;
        }

        for (int k = 1; k <= n; k++) {
            for (int i = 1; i <= n; i++) {
                for (int j = 1; j <= n; j++) {
                    if (graph[i][k] == 1 && graph[k][j] == 1) {
                        graph[i][j] = 1;
                    } else if (graph[i][k] == -1 && graph[k][j] == -1) {
                        graph[i][j] = -1;
                    }
                }
            }
        }

        for(int i=1;i<=n;i++){
            int cnt=0;
            for(int j=1;j<=n;j++){
                if(graph[i][j] == 1 || graph[i][j] == -1)   cnt++;
            }
            if(cnt == n-1)  answer++;
        }
        return answer;
    }
}

[문제]

https://school.programmers.co.kr/learn/courses/30/lessons/49191

[풀이]

이 문제는 이진 탐색(Binary Search)을 활용하여 효율적으로 해결할 수 있다.

문제의 핵심은 각 심사관의 처리 속도(times 배열)와 사람 수(n)를 고려하여, 모든 사람이 심사를 받을 수 있는 최소 시간을 계산하는 것이다.

최소 시간을 구하기 위해서 시간의 범위를 탐색해야 한다.

이 때 시간을 직접 하나씩 늘려가며 확인하는 완전 탐색은 비효율적이다.

심사를 받는데 걸리는 최소/최대 시간을 아래와 같이 설정할 수 있으므로 탐색의 범위가 좁혀진다.

따라서 이진 탐색을 생각하게 된다.

• 최소 시간: 1분 (최소한의 시간)
• 최대 시간: 가장 느린 심사관이 모든 사람을 처리하는 경우 n×max(times)

이진 탐색은 정렬된 범위에서 특정 조건을 만족하는 최적의 값을 찾는 문제에 적합하다.

이진 탐색 알고리즘에 대한 자세한 설명은 아래 링크를 통해 확인할 수 있습니다.

https://tnwlswkd.tistory.com/112

이진 탐색을 구현하기 위해 

low 값을 최소 시간, high 값을 최대 시간으로 설정해두었다.

그리고  calcPersonCount에서  mid에 해당하는 시간에 총 몇명을 심사할 수 있는지 계산했다.

이 때 아래 사진과 같은 문제를 해결하기 위해 심사 가능한 사람이 이미 n명을 넘었다면 반복문을 빠져나오도록 했다.

mid 시간에 해결할 수 있는 사람이 n명 보다 많으면 더 짧은 시간을 탐색하기 위해 high 값을  mid -1로 업데이트 하고

n명보다 적으면 더 긴시간을 탐색하기 위해 low 를 mid + 1 로 업데이트 해주었다.

personCnt == n인 경우에도 탐색을 계속하는 이유는 더 작은 시간에서 조건을 만족하는지를 확인하기 위해서이다.

위의 과정을 반복하며 모든 사람을 심사하기 위한 최소시간을 계산해주었다.

[시간 복잡도]

[코드]

import java.util.Arrays;

class Solution {
    public long solution(int n, int[] times) {
        long low = 1;
        long high = (long) Arrays.stream(times).max().getAsInt() * n; 
        long answer = high;

        while(low <= high) {
            long mid = (low + high) / 2;
            long personCnt = calcPersonCount(mid,n,times);
            if(personCnt >= n) {
                answer = mid;
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }
        return answer;
    }

    public long calcPersonCount(long curTime ,int n, int[] times){
        long personCnt = 0;
        for(int time : times) {
            personCnt += curTime / time;
            if(personCnt > n)   break;
        }
        return personCnt;
    }
}

[문제]

https://school.programmers.co.kr/learn/courses/30/lessons/43238

[풀이]

해당 문제는 모든 섬들을 최소 비용으로 연결하는 문제이므로 크루스칼 알고리즘을 사용해 풀 수 있다.

크루스칼 알고리즘이란 모든 노드들을 최소 비용으롤 연결하는 알고리즘이다.

아래 링크에서 크루스칼 알고리즘에 대해 자세한 설명을 볼 수 있다.
https://tnwlswkd.tistory.com/42

최소 비용을 계산하기 위해 우선 두 섬을 연결하는 다리를 건설할 때 드는 비용을 기준으로 오름차순 정렬을 해주었다.

이 때 각 비용은 cost 배열의 2번째 배열에 존재하기 때문에 Arrays.sort 메서드와 Comparator를 사용했다.

연결을 하기 전엔 각자의 부모를 자기 자신으로 초기화한다.

그리고 최소 비용부터 cost를 순회하며 현재 섬의 부모가 같은 지 확인 후 

다를 경우 섬을 연결해준다.

[코드]

import java.util.Arrays;

class Solution {
    static int[] parent;
	
    public int solution(int n, int[][] costs) {
        int answer = 0;
    
    	Arrays.sort(array, (a, b) -> Integer.compare(a[1], b[1]));

        for(int idx=0;idx<n;idx++) { 
            parent[idx]=idx;
        }
        for(int[] cost : costs) {
            int from  = cost[0];
            int to = cost[1];
            int len = cost[2];

            if(Find(from) == Find(to)) continue;
            Union(from, to);
            answer+=len;
        }

        return answer;
    }
    
    public int Find(int idx) {
        if(parent[idx] == idx)  return idx;
        else {
            return Find(parent[idx]);
        }
    }

    public void Union(int idx1, int idx2) {
        int parent1 = Find(idx1);
        int parent2 = Find(idx2);

        parent[parent2] = parent1;
    }
}

[문제]

https://school.programmers.co.kr/learn/courses/30/lessons/42861

[풀이]

야근 피로도를 최소화 하는 문제다.

야근 피로도는 남은 작업량을 제곱하여 더한 값이기 때문에

남은 작업량 중에서 작업량이 가장 큰 값부터 빼주면 된다.

따라서 우선순위 큐를 사용했는데 reverseOrder를 사용해 내림차순이 되도록 하였다.

해당 큐에 남은 작업량들을 넣어주어 가장 큰 값부터 1씩 빼주도록 하였다

해당 작업을 퇴근까지 남은 시간인 N번만큼 수행하도록 하였다.

위의 작업들을 마무리 하고 큐에 남은 값들을 제곱들하여 다 더해주었다.

[코드]

import java.util.Collections;
import java.util.PriorityQueue;

class Solution {
    public long solution(int n, int[] works) {
        long answer = 0;
        PriorityQueue<Integer> leftWork = new PriorityQueue<>(Collections.reverseOrder());
        for(int work : works) {
            leftWork.offer(work);
        }
        for(int idx=0;idx<n;idx++){
            if(leftWork.size() == 0)    break;
            int work = leftWork.poll() - 1;
            if(work > 0) {
                leftWork.offer(work);
            }
        }
        for(int work : leftWork){
            answer += work*work;
        }
        return answer;
    }
}

[문제]

https://school.programmers.co.kr/learn/courses/30/lessons/12927

[풀이]

문제 조건에서 이모티콘의 최대 개수가 7개밖에 되지 않기 때문에 안심하며 완전탐색을 사용해 풀었다.

각 이모티콘별 할인율을 저장하기 위한 discountRate 변수를 선언했다.

setDiscountRate 함수를 통해 각 이모티콘별 할인율을 10프로에서 40프로까지 모든 경우의 수를 돌리도록 지정해줬다.

해당 함수를 통해 각 이모티콘별 할인율을 정해주고 , 모든 이모티콘에 대해 할인율이 정해졌으면 calcPrice 함수를 호출한다.

calcPrice 함수에서는 각 사용자마다 이모티콘 총 구매 금액을 계산했다.

각 사용자들은 자신의 기준에 따라 일정 비율 이상 할인하는 이모티콘들에 할인 가격을 계산하여 price 변수에 더해준다.

모든 이모티콘들에 대해 계산이 끝나면 

각 사용자들은 자신의 기준에 따라 이모티콘 구매 비용의 합이 일정 가격 이상이 된다면 

emoticonPlus(이모티콘 플러스 구매한 사용자 수)에 1을 더해주고 

일정 가격 이상이 되지 않는다면 emoticonPrice에 이모티콘 구매 가격을 더해주었다.

1. 이모티콘 플러스 사용자 수 최대

2. 이모티콘 판매액 최대

위의 우선순위를 기준으로 이모티콘 플러스 사용자 수와 구매 가격을 계산해주었다.

[시간 복잡도]

주어진 문제의 조건을 기반으로 시간 복잡도를 계산해보면 

1. 완전 탐색

• 각 이모티콘은 4가지 할인율(10%, 20%, 30%, 40%) 중 하나를 선택할 수 있다.
• 이모티콘 개수를 N이라고 하면, 할인율 조합의 경우의 수는 

2. calcPrice 함수

• 모든 유저에 대해 반복 (users.length = M)
• 각 유저에 대해 이모티콘 개수 만큼 반복 (emoticons.length = N)

따라서 calcPrice의 시간 복잡도는 

𝑂(𝑀×𝑁)

3. 전체 시간 복잡도

[코드]

class Solution {
    static final int MAX_EMOTICON = 7;
    static int MAX_USER = 0;
    static int MAX_PRICE = 0;
    static int[] discountRate = new int[MAX_EMOTICON];

    public int[] solution(int[][] users, int[] emoticons) {

        setDiscountRate(0,users, emoticons);
        int[] answer = {MAX_USER ,MAX_PRICE};
        return answer;
    }

    public void setDiscountRate(int curIdx, int[][] users, int[] emoticons) {
        if(curIdx == emoticons.length) {
            calcPrice(users,emoticons);
            return;
        }
        for(int i = 10; i<= 40 ; i+=10) {
            discountRate[curIdx] = i;
            setDiscountRate(curIdx+1, users, emoticons);
        }
    }

    public void calcPrice(int[][] users, int[] emoticons) {

        int emoticonPlus=0;
        int emoticonPrice=0;

        for(int[] user : users) {
            // 각 유저의 이모티콘 구매 금액
            int price=0;
            int userDiscountRate = user[0];
            int userPlusPrice = user[1];
            for(int idx=0; idx<emoticons.length; idx++) {
                if(discountRate[idx] >= userDiscountRate) {
                    price += (emoticons[idx]/100) * (100-discountRate[idx]); 
                }
            }
            if(price >= userPlusPrice) {
                emoticonPlus++;
            } else {
                emoticonPrice += price;
            }
        }

        if(emoticonPlus > MAX_USER) {
            MAX_USER = emoticonPlus;
            MAX_PRICE = emoticonPrice;
        } 
        else if ( emoticonPlus == MAX_USER && emoticonPrice >= MAX_PRICE)   MAX_PRICE = emoticonPrice;
    }
}

[문제]

https://school.programmers.co.kr/learn/courses/30/lessons/150368

[풀이]

먼저 각 그래프의 특징을 파악하면 된다.

막대 그래프의 경우 다른 그래프에서는 존재하지 않는 

나가는 간선이 없고 들어오는 간선은 1개 이상인 정점이 한개 존재한다.

size가 1인 경우에도 새로 추가한 정점으로부터 나온 간선이 들어오기 때문에 

들어오는 간선은 무조건 1개 이상 존재하게 된다.

8자 그래프의 경우는 나가는 간선 2개 그리고 들어오는 간선이 2개

따라서 총 4개의 간선이 존재하는 정점 한개가 존재한다.

사실 8자 그래프의 경우, 8자 그래프에만 존재하는 특징을 따로 찾을 수 없었다.

하지만 다행히 문제에서 기존의 그래프가 존재하는 상황에서 이 그래프와 무관한 정점을 하나 추가하고, 

정점에서 각 그래프로 향하는 간선들을 연결했다.

이 말에 의하면 새로 추가한 정점의 나가는 간선 수가 총 그래프의 개수가 된다.

따라서 8자 그래프의 개수 = 새로 추가한 정점의 나가는 간선 개수 - (도넛 그래프 수 + 막대 그래프 수) 가 된다.

또한 문제 제한 사항에서 아래와 같이 주어졌기 때문에

도넛 모양 그래프, 막대 모양 그래프, 8자 모양 그래프의 수의 합은 2이상입니다.

정점 중에서 나가는 간선만 2개 이상 존재하고, 들어오는 간선이 없는 정점을 발견한다면 해당 정점이 새로 추가한 정점이 된다.

그리고 해당 정점의 나가는 간선 개수가 전체 그래프 개수가 되는 것이다.

위의 정보들을 기반으로 코드를 구현했다.

나가는 간선, 들어오는 간선 정보를 저장하기 위해 output, input 배열을 선언했다.

edges 정보를 기반으로 각 정점별 output, input 간선들을 count 했다.

그리고 각 정점들의 input, output 간선들의 개수를 기반으로 

8자 그래프 , 막대 그래프, 새로 추가된 정점의 번호를 알 수 있었다.

이를 기반으로

새로 추가한 정점의 나가는 간선 개수 - (도넛 그래프 수 + 막대 그래프 수)  값을 계산하여 도넛 그래프의 개수도 알 수 있었다.

[코드]

class Solution {
    static final int MAX = 1_000_000;

    public int[] solution(int[][] edges) {
        int MAX_IDX =0;
        int[] input, output;

        input = new int[MAX+1];
        output = new int[MAX+1];

        for(int[] edge : edges) {
            output[edge[0]]++;
            input[edge[1]]++;
            MAX_IDX = Math.max(MAX_IDX, Math.max(edge[0],edge[1]));
        }

        int totalGraph = 0;
        // 각 그래프 개수
        int stickGraph = 0;
        int donutGraph = 0;
        int eightGraph = 0;
        // 새로 추가된 노드 번호
        int edgeIdx = 0;
        for(int idx = 1; idx<= MAX_IDX; idx++) {
            if(input[idx] >= 2 && output[idx] >= 2) eightGraph++;
            else if(output[idx] == 0 && input[idx] > 0)   stickGraph++;
            else if(output[idx] >= 2 && input[idx] == 0) {
                edgeIdx = idx;
                totalGraph=output[idx];
            }
        }
        donutGraph =totalGraph-(eightGraph+stickGraph);
        int[] answer = {edgeIdx, donutGraph, stickGraph, eightGraph};
        return answer;
    }
}

[문제]

https://school.programmers.co.kr/learn/courses/30/lessons/258711

[풀이]

2024년 카카오 겨울인턴십 코테 문제이다.

문제의 조건을 잘 읽고 , 조건에 맞게 구현하면 되는 단순 구현 문제이다.

모두 map을 사용해서 각각의 데이터들을 관리했다.

먼저 선물을 주고받은 내용을 기록하기 위해 2차원 map인 gift_record라는 변수를 선언했다.

key 값에 선물을 준 사람의 이름을 넣고, 2번째 map에는 누구에서 몇개의 선물을 줬는지에 대한 데이터를 저장한다.

첫번째 예시를 기준으로 보면 아래와 같이 gift_record가 존재하게 된다.

{'muzi', {'frodo',2}}

{'ryan', {'muzi',3}}

{'frodo', {{'muzi',1}, {'ryan',1}}}

{'neo', {'muzi',1}}

그리고 각 사람들의 선물 지수를 기록하기 위해 gift_score 라는 1차원 map을 선언했다.

key 값을 사람의 이름이 되고 , value는 선물 지수 값이 된다.

선물 지수는 (준 선물의 개수 - 받은 선물의 개수) 이므로 

사실상 선물을 줄 때는 현재 선물 지수에 +1을 해주고

선물을 줄 때는 현재 선물 지수에 -1을 해주면 된다. 

따라서 gift_record, gift_score 의 값을 동시에 채워줬다.

Java에서 Map 인터페이스의 getOrDefault 메서드를 사용해 map의 value 값을 할당해줬다.

특정 키를 조회할 때, 해당 키가 존재하면 해당 키 값을 / 존재하지 않을 경우 기본값(default value)을 반환해준다.

마지막으로 gift_record를 기반으로 다음 달에 받을 선물을 계산했다.

1. 서로 선물을 주고 받은 경우 선물을 적게 준 사람이 더 많이 준 사람에게 담달에 선물을 하나 주고 

2. 하나도 주고 받지 않았거나 , 주고 받은 개수가 같을 경우에는 선물 지수를 기반으로 담달 선물을 준다

2-1 선물 지수가 작은 사람이 큰 사람에게 담달에 선물 1개를 주면 된다.

여기서는 선물을 받는 사람을 기준으로만 계산을 했다. 

따라서 위의 조건을 만족하여 선물을 받는 사람일 경우 gift_cnt에서 받는 사람에 해당하는 value에 1을 더해줬다.

마지막으로 Collections을 사용해 gift_cnt의 value중 최대값을 구하였다.

Collections는 java.util 패키지에 포함된 유틸리티 클래스로, 컬렉션(Collection) 객체를 쉽게 조작하고 관리할 수 있도록 sort, search, min, max와 같이 다양한 정적 메서드를 제공한다.

[코드]

import java.util.Map;
import java.util.HashMap;
import java.util.Collections;

class Solution {
    
    static int[][] gift_cnt = new int [50][];


    public int solution(String[] friends, String[] gifts) {
        int answer = 0;
        //선물 기록 관리
        Map<String, Map<String, Integer>> gift_record= new HashMap<>();
        // 선물 지수
        Map<String, Integer> gift_score = new HashMap<>();
        // 받을 선물 개수
        Map<String, Integer> gift_cnt = new HashMap<>();
    


        for(String friend : friends) { 
            gift_record.put(friend, new HashMap<>());
            gift_score.put(friend,0);
            gift_cnt.put(friend,0);
        }
            
        for (String gift : gifts) {
            String person[] = gift.split(" ");
            String from = person[0];
            String to = person[1];

            gift_record.get(from).put(to, gift_record.get(from).getOrDefault(to, 0) + 1);
            gift_score.put(from, gift_score.get(from) + 1);
            gift_score.put(to, gift_score.get(to) - 1);
        }

        for(String from : friends) { 
            for(String to : friends) { 
                if(!from.equals(to)) {
                    int from_cnt = gift_record.get(from).getOrDefault(to, 0); //from이 to에게 준 선물의 개수
                    int to_cnt = gift_record.get(to).getOrDefault(from, 0); //to가 from에게 준 선물의 개수
                    if(from_cnt > to_cnt) {
                        gift_cnt.put(from, gift_cnt.get(from) + 1);
                    } else if (from_cnt == to_cnt && gift_score.get(from) > gift_score.get(to)) {
                            gift_cnt.put(from, gift_cnt.get(from) + 1);
                    } 
                }
            }
        }


        return Collections.max(gift_cnt.values());
    }
}

[문제]

https://school.programmers.co.kr/learn/courses/30/lessons/258712