메리

한화생명 코테

프로그래머스 난이도 1~1.5 쯤 예상됨

1. 오름차순 정렬

2. 배열 오른쪽부터 m개씩 끊으면 끊은 지점이 그 구간에서 제일 싼가격임..

import java.util.*;

class Solution {
    public int solution(int k, int m, int[] score) {
        Arrays.sort(score);
        int sum = 0;
        for (int i = score.length - m; i >= 0; i -= m) {
            sum += score[i] * m;
        }
        return sum;
    }
}

특정 수의 약수를 구할 때 그 수의 제곱근까지만 나눠보는 이유는 약수는 항상 짝을 이루기 때문

다른 풀이를 보고

for문 라벨링이란걸 처음 해보았다.

class Solution {
    public int solution(int n) {
        int answer = 0;
        
        outer:
        for(int i=2; i<=n; i++){
            for(int j=2; j<=Math.sqrt(i); j++){
                if(i%j == 0){
                    continue outer;
                } 
            }
            answer += 1;
        }
        return answer;
    }
}

1. 첫번째부터 롤러질

2. 어디까지 칠해졌는지 기록 <= checked

3. 칠할 section을 돌면서 checked보다 같거나 작은지 체크(칠해진거)

4. section이 칠해진 지점보다 크면 롤러횟수+1, 어디까지 칠해졌는지 기록.

5. 칠해진 지점이 전체 길이보다 같거나 크면 stop

class Solution {
    public int solution(int n, int m, int[] section) {
        int answer = 0;
        int checked = 0; //checked까지 칠해졌음
        
        
        for(int sec : section){
            if(checked >= sec){
                continue;
            }else{
                checked = sec + (m-1);
                answer += 1;
            }
            
            if(checked >= n) break;
        }
        
        return answer;
    }
}

투 포인터라는 알고리즘을 배웠음!

핵심 원리는 다음과 같음

1. start pointer / end pointer

2. end pointer을 오른쪽으로 옮기면 합이 증가

3. start pointer을 오른쪽으로 옮기면 합이 감소

4. pointer 이동한 뒤 목표합보다 작으면 -> end pointer를 오른쪽으로 옮긴다.

5. pointer 이동한 뒤 목표합보다 크면 -> start pointer를 오른쪽으로 옮긴다.

이제 여기서 문제마다

목표합과 같을때 무슨 액션을 할지 달라지는가 보다.

두번째 문제풀이

import java.util.*;

public class Problem1806 {
    //부분합
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int numsCount = sc.nextInt();
        int targetSum = sc.nextInt();
        sc.nextLine();
        int[] nums = new int[numsCount];
        for(int i=0; i<numsCount; i++){
            nums[i] = sc.nextInt();
        }

        int end = 0;
        int start = 0;
        int sum = 0;
        int minLen = numsCount+1;
        //end 포인터를 오른쪽으로 옮기면 합이 증가
        //start 포인터를 오른쪽으로 옮기면 합이 감소
    
        while(end < numsCount){ //end 포인터가 배열 마지막부분까지 가도록
            if(sum < targetSum){ //합이 목표합보다 작은 경우 : end 포인터를 오른쪽으로 옮긴다.
                sum += nums[end++];
            }
            while(sum >= targetSum){//합이 목표합보다 크거나 같은 경우 : start 포인터를 오른쪽으로 옮긴다.
                sum -= nums[start++];
                minLen = Math.min(minLen, end-start+1);
            }
        }
        
        if(minLen == numsCount + 1){
            System.out.println(0);
        }else{
            System.out.println(minLen);
        }
    }
    
}

첫번째 문제풀이

import java.util.*;

public class Problem1806 {
    //부분합
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int numsCount = sc.nextInt();
        int targetSum = sc.nextInt();
        sc.nextLine();
        int[] nums = new int[numsCount];
        for(int i=0; i<numsCount; i++){
            nums[i] = sc.nextInt();
        }

        int start = 0;
        int sum = 0;
        int minLen = numsCount+1;
        for(int end=0; end<numsCount; end++){
            sum += nums[end]; //end에 있는 수 더하기

            while(sum >= targetSum){//목표합보다 같거나 큰 경우 길이를 기록, start을 오른쪽으로 땡김
                minLen = Math.min(end-start+1,minLen);
                sum -= nums[start++];      
            } 

        }
        minLen = minLen == numsCount+1 ? 0 : minLen;
        System.out.println(minLen);
    }
    
}

아래코드는 다음과 같이 바꿀 수 있음

start += 1; 
sum -= nums[start-1];

=> sum -= nums[start++];

boxed를 해주는 이유

1. Comparator는 객체를 비교하는 인터페이스이다.
2. Instream은 기본 데이터 타입인 int 를 다루는 스트림이므로 Comparator를 사용할 수 없다.
3. 따라서 boxed()를 사용하여 IntStream을 Stream<Integer>로 변환한다.

import java.util.*;

public class Problem10817 {
    // 세 수
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String[] nums = sc.nextLine().split(" ");
        Optional<Integer> num = Arrays.stream(nums)
                                .mapToInt(Integer::parseInt)
                                .boxed()
                                .sorted((a,b) -> b-a)
                                .skip(1)
                                .findFirst();

        System.out.println(num.get());
    }
}

문제 제대로 안 읽고 오름차순인거 캐치 못하고 계속 삽질..

나는 왜그럴까.. 

import java.io.File;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Deque;
import java.util.List;
import java.util.Scanner;

public class Main {
    static boolean[][] isChecked; //체크여부
    static int[][] map;           //지도
    static int mapSize;           //지도의 크기
    static Deque<int[]> queue = new ArrayDeque<>();   //방문할 좌표
    static int[] xmove = new int[]{-1, 1, 0, 0};           //상하좌우
    static int[] ymove = new int[]{0, 0, -1, 1};           //상하좌우
    static int townCnt = 0;
    public static void main(String[] args) throws Exception{
        Scanner sc = new Scanner(System.in);
        mapSize = Integer.parseInt(sc.nextLine());
        map = new int[mapSize][mapSize];
        isChecked = new boolean[mapSize][mapSize];

        //map 저장
        for(int i=0; i<mapSize; i++){
            String row = sc.nextLine();
            for(int j=0; j<row.length(); j++){
                map[i][j] = row.charAt(j) - '0';
            }
        }

        for(int i=0; i<mapSize; i++){
            for(int j=0; j<mapSize; j++){
                if(!isChecked[i][j] && map[i][j] == 1){ //방문체크 안되어있는 1값인 경우 시작
                    townCnt += 1; //단지 카운트
                    bfs(i, j);
                }
            }
        }
        System.out.println(townCnt);
        Collections.sort(townSizes);
        for(Integer cnt : townSizes){
            System.out.println(cnt);
        }
    }
    static List<Integer> townSizes = new ArrayList<>();
    public static void bfs(int x, int y){
        int townSize = 1;
        queue.add(new int[]{x, y});
        isChecked[x][y] = true;
        while(!queue.isEmpty()){
            int[] position = queue.poll();
            for(int i=0; i<4; i++){
                int newx = position[0] + xmove[i];
                int newy = position[1] + ymove[i];
                if(newx >= 0 && newy >= 0 && newx < mapSize && newy < mapSize
                    && map[newx][newy] == 1
                    && !isChecked[newx][newy]
                ){
                    queue.add(new int[]{newx, newy});
                    isChecked[newx][newy] = true;
                    townSize += 1;
                }
            }
        }

        townSizes.add(townSize);    
        
    }
}

DFS 사용

import java.io.File;
import java.util.Scanner;

public class Problem2606 {
    static int[][] map; //연결망
    static boolean[] isChecked; //체크여부
    static int computerCnt; //컴퓨터 개수
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        computerCnt = Integer.parseInt(sc.nextLine());
        int lineCnt = Integer.parseInt(sc.nextLine());
        isChecked = new boolean[computerCnt+1];
        map = new int[computerCnt+1][computerCnt+1];

        //map에 연결여부 넣기
        for(int i=1; i<=lineCnt; i++){
            String[] line = sc.nextLine().split(" ");
            int a = Integer.parseInt(line[0]);
            int b = Integer.parseInt(line[1]);
            map[a][b] = map[b][a] = 1;
        }

        dfs(1);
        System.out.println(virusCnt);
    }

    static int virusCnt = 0;
    public static void dfs(int start){
        isChecked[start] = true;
        for(int i=1; i<=computerCnt; i++){
            if(map[start][i] == 1 && !isChecked[i]){ //방문한 적 없고 연결1이면
                virusCnt+=1;
                dfs(i);
            }
        }
    }
}

(1, 1)에서 출발하여 (N, M)의 위치로 이동할 때 지나야 하는 최소의 칸 수를 구하기

필요한 변수

로직

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

public class Main {
    public static int n,m;
    public static int[][] map;
    public static int[] xmove = {-1,1,0,0}; //상 하 좌 우
    public static int[] ymove = {0,0,-1,1};
    public static Deque<int[]> queue = new ArrayDeque<>();
    public static boolean[][] isChecked;
    public static int[][] cnt;
    
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] nm = br.readLine().split(" ");
        n = Integer.parseInt(nm[0]); //행 개수
        m = Integer.parseInt(nm[1]); //열 개수
        map= new int[n][m]; //지도
        isChecked = new boolean[n][m]; //방문 여부
        cnt = new int[n][m];

        //지도 저장
        for(int i=0; i<n; i++){
            String row = br.readLine();
            for(int j=0; j<m; j++){
                map[i][j] = row.charAt(j) - '0';
            }
        }
        bfs();
        System.out.println(cnt[n-1][m-1]);

    }

    public static void bfs(){
        cnt[0][0] = 1;
        queue.offer(new int[]{0,0});

        while(!queue.isEmpty()){
            int[] position = queue.poll();
            int x = position[0];
            int y = position[1];

            //2. 상화좌우의 이동 가능 좌표 탐색
            for(int i=0; i<4 ;i++){
                int newx = x + xmove[i];
                int newy = y + ymove[i];

                //값이 1이어야 하며, check 안된 곳, 범위를 벗어나지 않아야 함.
                if(newx >= 0 && newy >= 0 && newx < n && newy < m
                && map[newx][newy] == 1
                && !isChecked[newx][newy]){
                    queue.offer(new int[]{newx,newy}); //3. 큐에 넣기
                    isChecked[newx][newy] = true; //방문여부 체크
                    cnt[newx][newy] = cnt[x][y] + 1; //다음 위치 cnt 기록
                }
            }

        }
    }

}

처음 시도 

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