반응형

그래프 사용이유

1. 여러 객체간의 관계를 논리적이고 시각적으로 표현할 수 있음 
└ 두 개체간의 경로, 연결여부 등을 표시함
2. 경로 탐색이나 최단 경로 계산을 할 수 있음

 

StringTokenizer : 문자열을 구분자(delimiter)로 분리하여 토큰(token)으로 나누는 클래스. 구분자를 지정하지 않으면 기본적으로 공백을 구분자로 사용

hasMoreTokens(): 다음 토큰이 있는지 확인하여 boolean을 반환합니다.
nextToken(): 다음 토큰을 반환하고, 토큰이 없으면 예외를 발생시킵니다.
countTokens(): 남아 있는 토큰의 개수를 반환합니다.

BufferedReader : 문자 데이터를 버퍼에 담아 한 번에 읽고 처리

InputStreamReader : System.in과 같은 콘솔입력 등을 바이트 스트림을 문자 스트림으로 변환

 

BufferedReader는 단순히 데이터를 읽어와 한 줄 단위로 문자열로 반환하는 반면, Scanner는 입력을 토큰화하고 데이터 타입에 맞게 변환

StringBuilder 사용해서 한번 출력하는게 

매번 System.out.print 찍는것보다 미세하게 빠름

 

배열 생성시 정점 개수로 하느냐, 간선 개수로 하느냐 때문에 메모리 초과 떴었음

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    public static int n, m, v; //n=정점의 개수, m=간선의 개수, v=시작 정점 번호
    public static int[][] arr;
    public static boolean[] isVisited;
    public static Deque<Integer> queue = new ArrayDeque<>();
    public static StringBuilder sb = new StringBuilder();

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer strtk = new StringTokenizer(br.readLine());
        n = Integer.parseInt(strtk.nextToken());
        m = Integer.parseInt(strtk.nextToken());
        v = Integer.parseInt(strtk.nextToken());

        arr = new int[n+1][n+1]; //간선 배열
        isVisited = new boolean[n+1]; //정점 방문 여부 배열


        for(int i=0; i<m ; i++){ //간선 읽어서 배열에 저장
            strtk = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(strtk.nextToken());
            int b = Integer.parseInt(strtk.nextToken());
            arr[a][b] = arr[b][a] = 1; //선이 연결된 경우 1
        }

        dfs(v);
        Arrays.fill(isVisited,false);
        System.out.print("\n");
        bfs(v);

    }
    //depth first search
    public static void dfs(int start){
        isVisited[start] = true;
        System.out.print(start + " ");
        for(int i=1; i<= n; i++){
            //간선이 연결되어 있고 방문한적 없는 정점인 경우
            if(arr[start][i] == 1 && !isVisited[i]){
                dfs(i);
            }
        }
    }

    //breadth first search
    public static void bfs(int start){
        isVisited[start] = true;
        queue.offer(start);
        while(!queue.isEmpty()){
            int s = queue.poll();
            System.out.print(s + " ");
            for(int i=1; i<=n; i++){
                if(arr[s][i] == 1 && !isVisited[i]){
                    queue.offer(i);
                    isVisited[i] = true;
                }
            }
        }
    }
}
반응형
반응형

처음 시도 

1. 보석의 무게와 가격을 이중배열에 담는다.
2. 보석 2중배열을 가격을 기준으로 내림차순 정렬
3. 가방 무게 배열을 오름차순 정렬
4. 가방 배열과 보석 배열 이중 for문, 조건 : 보석무게 <= 가방무게인 경우 가격을 +, 값은 -1 세팅
=> 이중 for문으로 모든 가방마다 보석배열을 쭉 돌게 됨

결과 : 시간초과

 

2차 시도

1. 보석의 무게와 가격을 이중배열에 담는다.
2. 보석 2중배열을 가격을 기준으로 내림차순 정렬 무게 기준 오름차순 정렬
3. 가방 무게 배열을 오름차순 정렬
4. 가방 배열 순회 for, 보석 배열 순회 while, 조건 : 보석무게 <= 가방무게인 경우 
가격을 우선수위 큐에 담고 보석배열 인덱스 증가시킴. 보석 배열은 한 번만 순회함.
가방에 담을 수 있는 보석 중 가장 비싼 가격을 뽑아서 +.

결과 : 시간초과

 

3차 시도

1. 보석의 무게와 가격을 담는 이중배열에 담는다.  객체를 만든다.
2. 보석 객체 배열 무게 기준 오름차순 정렬
3. 가방 무게 배열을 오름차순 정렬
4. 가방 배열 순회 for, 보석 배열 순회 while, 조건 : 보석무게 <= 가방무게인 경우 
가격을 우선수위 큐에 담고 보석배열 인덱스 증가시킴. 보석 배열은 한 번만 순회함.

가방에 담을 수 있는 보석 중 가장 비싼 가격을 뽑아서 +.

결과 : 통과

 

* 이중배열과 객체배열을 사용하는 것의 시간 차이가 있는 것으로 보임

* 우선순위 큐 최대 힙

PriorityQueue<Integer> pq = new PriorityQueue<>(Comparator.reverseOrder());

 

* 배열 정렬에 Comparator 사용

Arrays.sort(jewels,Comparator.comparingInt((int[] a)->a[0]));
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        //목적 최대한 비싼 보석 넣기
        Scanner sc = new Scanner(System.in);
        int jewelCnt = sc.nextInt();
        int bagCnt = sc.nextInt();

        //보석 무게와 가격 정보
        Jewelry[] jewels = new Jewelry[jewelCnt];
        for(int i=0; i<jewelCnt; i++){
            Jewelry temp = new Jewelry(sc.nextInt(), sc.nextInt());
            jewels[i] = temp;
        }

        //보석 무게 오름차순
        Arrays.sort(jewels, Comparator.comparingInt(j -> j.mass));

        //가방 정보
        int[] bagInfo = new int[bagCnt];
        for(int i=0; i<bagCnt; i++){
            bagInfo[i] = sc.nextInt();
        }
        //가방 무게 적은 순 정렬
        Arrays.sort(bagInfo);        
        
        long sum = 0;
        int jewelIndex = 0;
        PriorityQueue<Integer> pq = new PriorityQueue<>(Comparator.reverseOrder());
        for (int bag : bagInfo) {
            // 현재 가방 무게에 맞는 모든 보석을 추가
            while (jewelIndex < jewels.length && jewels[jewelIndex].mass <= bag) {
                pq.offer(jewels[jewelIndex].price);
                jewelIndex++;
            }
            // 가장 비싼 보석 선택
            if (!pq.isEmpty()) {
                sum += pq.poll(); // 선택된 보석은 다른 가방에서 사용되지 않음
            }
        }
        
        System.out.println(sum);
    } 
}

class Jewelry {
    int mass; // 무게
    int price; // 가격
 
    Jewelry(int mass, int price) {
        this.mass = mass;
        this.price = price;
    }
}
반응형

'코딩 관련 > 코딩문제풀기' 카테고리의 다른 글

[백준] ATM  (0) 2024.10.29
[백준] 설탕 배달  (0) 2024.10.29
[프로그래머스] Lv1. 실패율  (0) 2024.10.28
[프로그래머스] Lv1. 가장 많이 받은 선물  (0) 2024.10.23
[프로그래머스] Lv1. 모의고사  (0) 2024.10.23
반응형

11399번

제일 앞에서는 사람이 걸리는 시간은 뒤의 사람 수만큼 곱해지므로 오름차순으로 세우면 됨

import java.util.*;

public class Problem11399 {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        int cnt = sc.nextInt(); //사람수
        sc.nextLine();
        String[] temptimes = sc.nextLine().split(" ");
        int[] times = Arrays.stream(temptimes)
                    .mapToInt(Integer::parseInt)
                    .toArray();
        Arrays.sort(times); //오름차순 정렬
        
        int timeTotal = 0;
        for(int time : times){
            timeTotal += time * cnt;
            cnt -= 1;
        }
        System.out.println(timeTotal);
    }
}
반응형
반응형

백준 그리디 알고리즘 중 설탕배달

5kg짜리를 최대로 잡고  5kg 짜리를 줄이고 3kg짜리를 늘려가면서 맞춰보는 방식

import java.util.Scanner;

public class Problem2839{
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        int total = sc.nextInt();
        int count5 = total/5;

        while(count5 >= 0){
            int remain = total - count5 * 5;
            if(remain % 3 == 0){
                System.out.println(count5 + remain/3);
                return;
            }
            count5 -= 1;
        }

        System.out.println(-1);

    }
}
반응형
반응형

중첩 for문 안 쓰고 싶었는데 이게 제일 깔끔하고 쉬웠음 ㅠ

stage 총 이용자 수를 stage.length로 잡고 다음단계로 못 간 이용자를 제외시키면서 진행하는 걸 생각해내는데 어려움이 있었음..

 

연습해 본것

이중배열을 stream을 이용해 정렬하기

sorted( Comparator ) : 스트림의 요소를 정렬하는 데 사용됨

reversed() : 정렬 순서 뒤집기

Double[][] sortedArray = Arrays.stream(failRate)
                                .sorted(Comparator.comparingDouble((Double[] a) -> a[1]).reversed())
                                .toArray(Double[][]::new);

Comparator.naturalOrder() : 자연 정렬

Comparator.reverseOrder() : 역순 정렬

Comparator.nullsFirst(Comparator.naturalOrder()) : null을 맨 앞에 두고 정렬

Comparator.comparingInt(String::length) : 길이에 따라 정렬

 

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

class Solution {
    public int[] solution(int N, int[] stages) {
        Double[][] failRate = new Double[N][2];
        int totalPlayers = stages.length; 
        
        for(int stage = 1; stage <= N ; stage++){
            int challengers = 0; //해당 스테이지의 이용자 수
            for(int s : stages){
                if(s == stage){
                    challengers += 1;
                }
            }
            
            failRate[stage-1][0] = (double) stage;
            //실패율 = challengers / totalPlayers;
            if(totalPlayers == 0){
                failRate[stage-1][1] = 0.0;
            }else{
                failRate[stage-1][1] = (double)challengers / (double)totalPlayers;
            }        
            
            //다음 단계로 못 간 이용자 제외
            totalPlayers -= challengers;
        }
        
        Double[][] sortedArray = Arrays.stream(failRate)
                                .sorted(Comparator.comparingDouble((Double[] a) -> a[1]).reversed())
                                .toArray(Double[][]::new);

        
        int[] answer = new int[N];
        for(int i=0; i<sortedArray.length; i++){
            answer[i] = sortedArray[i][0].intValue();
        }

        return answer;
    }
}
반응형
반응형

stream 연습 또했네~

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

class Solution {
    public int solution(int[] nums) {
        int[] newNum = Arrays.stream(nums)
                        .distinct()
                        .toArray();
        int answer = newNum.length > nums.length/2 ? nums.length/2 : newNum.length;
        return answer;
    }
}

 

반응형
반응형
class Solution {
    public int solution(String[] friends, String[] gifts) {
        int[][] giftCount = new int[friends.length][friends.length];
        long[] giftIndex = new long[friends.length];

        //주고받은 관계 입력
        for(int i = 0 ;i< friends.length;  i++ ){
            for(int j = 0; j<friends.length; j++){
                String gift = friends[i] + " " + friends[j];
                for(String temp : gifts){
                    if(temp.equals(gift)){
                        giftCount[i][j] += 1;
                    }
                }

            }
        }

        //선물지수 입력
        for(int i=0;i< friends.length;i++){
            for(String temp : gifts) {
                String giver = temp.split(" ")[0];
                String receiver = temp.split(" ")[1];

                if (giver.equals(friends[i])) {
                    giftIndex[i] += 1;
                }

                if(receiver.equals(friends[i])){
                    giftIndex[i] -= 1;
                }
            }
        }

        int maxGift = 0;
        //선물 받을 개수 계산
        for(int i=0;i< friends.length;i++){
            int giftCnt = 0;
            for(int j =0;j< friends.length;j++){
                //자기거는 제외
                if(i==j){
                    continue;
                }
                
                //주고받은 내역 없는 경우
                if(giftCount[i][j] == giftCount[j][i]){
                    if(giftIndex[i] > giftIndex[j]){
                        giftCnt += 1;
                    }
                    
                }else{
                    //비교
                    if(giftCount[i][j] > giftCount[j][i]){
                        giftCnt += 1;
                    }
                }
                

            }
            
            if(giftCnt>maxGift) {
                maxGift = giftCnt;
            }
        }
        
        return maxGift;
    }
    
}
반응형
반응형

또 써본 mapToInt();

학생들 점수산출은 어렵지 않았는데 그 다음에

제일 큰 점수 구하기 -> 제일 큰 점수 가진 학생 구하기 -> 배열 만들기

이게 너무 싫음..

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

class Solution {
    public int[] solution(int[] answers) {
        int[] student1 = {1, 2, 3, 4, 5}; //len 5
        int[] student2 = {2, 1, 2, 3, 2, 4, 2, 5}; //len8
        int[] student3 = {3, 3, 1, 1, 2, 2, 4, 4, 5, 5}; //len10
        
        int[] scores = new int[3];
        for(int i=0;i<answers.length;i++){
            int answer = answers[i];
            
            //학생1정답
            if(student1[i%student1.length] == answer) scores[0] += 1;
            //학생2정답
            if(student2[i%student2.length] == answer) scores[1] += 1;
            //학생3정답
            if(student3[i%student3.length] == answer) scores[2] += 1;
        }
        
        int max = Arrays.stream(scores).max().orElse(0);
        
        List<Integer> students = new ArrayList<>();
        for(int i=0;i<scores.length;i++){
            if(scores[i] == max){
                students.add(i+1);
            }
        }
        
        return students.stream()
            .mapToInt(Integer::intValue)
            .toArray();
    }
}
반응형
반응형

사실 중간에 순서 뒤집기 때문에..

그냥 단순히 나눈 순서대로 Math.pow() 해도 될텐데

진법 변환을 다 해보았다..

n진법 변환시 나머지를 어떻게 쌓는지 순서를 파악하면 간단할듯.

import java.util.*;

class Solution {
    public int solution(int n) {
        return getNumFormatTen(getNumFormatThree(n));
    }
    
    public String getNumFormatThree(int n){
        Deque<String> deque  = new ArrayDeque<>();
        while(true){
            deque.offer(Integer.toString(n % 3));
            int share = n / 3;
            if(share == 0){
                break;
            }else{
                n = share;
            } 
        }        
        StringBuilder formatThree = new StringBuilder();
         while (!deque.isEmpty()) {
            formatThree.append(deque.poll()); //넣은 순 꺼내기.
        }
        return formatThree.toString();
    }
    
    public int getNumFormatTen(String n){
        int num=0;
        for(int i=0;i<n.length();i++){
            num += Math.pow(3,i) * (n.charAt(n.length()-1-i)-'0');
        }
        return num;
    }
}
반응형
반응형

최대공약수는 영어로 The Greatest Common Factor...  혹은 Divisor...

최소공배수는 영어로 The Least Common Multiple..

최대공약수 구할 때 재귀함수 호출을 해보았다.

class Solution {
    public int[] solution(int n, int m) {
        int[] answer = new int[2];
        answer[0] = getGreatestCommonFactor(n,m);
        answer[1] = getLeastCommonMultiple(n,m,answer[0]);
        return answer;
    }
    
    //둘중의 한 쪽의 수를 나머지로 계속 나눈다..
    public int getGreatestCommonFactor(int n, int m){
        if(m == 0) return n;
        return getGreatestCommonFactor(m,n%m);
    }
    
    public int getLeastCommonMultiple(int n, int m, int gcf){
        return n*m/gcf;
    }
}

 

반응형

+ Recent posts