BangBang's Devlogs

programmers.co.kr/learn/courses/30/lessons/1845?language=java

해결 방안

고를 수 있는 폰켓몬 중 종류의 최댓값을 구하는 문제이다.

따라서 HashMap에 key값을 종류, value 값을 종류의 갯수로 넣고
pick해야하는 갯수보다 map size가 크면 종류의 갯수가 더 많은 것이므로 전체 다 다른 종류를 고를 수 있게 되서 answer = pick이 된다.

pick해야하는 갯수보다 map size가 작으면 종류의 갯수가 더 작으므로 map size 만큼 종류를 고르는게 최댓값이므로 answer = map size가 된다.

코드

import java.util.*;
// 폰켓몬
class Solution {
    public int solution(int[] nums) {
        int answer = 0;
        int pick = nums.length/2;
        Map<Integer, Integer> map = new HashMap<>();
        
        for(int i=0; i<nums.length; i++){
            if(map.containsKey(nums[i])){
                map.put(nums[i], map.get(nums[i])+1);
            }
            else{
                map.put(nums[i], 1);
            }
        }
        
        if(pick <= map.size()){
            answer = pick;
        }
        else{
            answer = map.size();
        }
        
        
        return answer;
    }
}

programmers.co.kr/learn/courses/30/lessons/12987?language=java

해결 방안

문제에서 원하는 것은 B의 최대 승점이므로 A가 최소인 경우부터 차근차근 B가 높을 때의 갯수를 구해준다.

A와 B 배열을 오름차순으로 정렬해준다.

A 작은 수부터 B와 비교를 해주는데 이때 B의 배열을 하나씩 증가하면서 해준다.
이 때 B 배열의 index 시작 값은 A[i] < B[j] 보다 큰 경우가 됬을 때 idx = j+1 이 되게된다.
왜냐하면 해당 A[i]와 매칭 된게 B[j]이기 때문이다. 

코드

import java.util.*;
// 숫자 게임
class Solution {
    public int solution(int[] A, int[] B) {
        int answer = 0;
        
        Arrays.sort(A);
        Arrays.sort(B);
        
        int idx = 0;
        for(int i=0; i<A.length; i++){
            // B의 idx까지는 A팀과 연결이 됬으므로
            for(int j=idx; j<B.length; j++){
                // B가 더 큰 경우
                if(A[i] < B[j]){
                    answer++;
                    idx = j+1;
                    break;
                }
                // B가 더 작거나 같은경우
                else{
                    continue;
                }
            }
        }
        return answer;
    }
}

programmers.co.kr/learn/courses/30/lessons/12980?language=java

해결 방안

 처음에는 문제에서 제시된 해결 방안을 보고 탐색을 이용한 최소 값을 구하려고 하였으나 depth가 정해져 있지 않고 입력으로 주어진 n이 10억이 넘는 것을 보고 다른 방법을 생각해보게 되었다.

n이 정해져 있고 최소 건전지 사용량도 정해져 있다고 생각하게 되었고 문제에서 주어진 5와 6을 이용해 가장 좋은 방법을 생각해보았다.

그 후 n을 이용하여 거꾸로 계산하였다.
짝수일 때 2로 나누고 홀수이면 1을 빼서 다시 돌려본 결과 거꾸로 계산을 하게 되면 stack에서 나중에 계산한 것이 처음 나오는 것처럼 답을 구할 수 있다고 생각하게 되었다.

그 생각에서 나온 코드이다.

코드

import java.util.*;

// 점프와 순간 이동
// k칸 앞으로 점프 - k만큼 건전지 소모
// 현재까지 온 거리 x 2 - 건전지 소모 x
// 건전지 사용량을 줄이기 위해 점프 최소

// 사용해야 하는 건전지 사용량 최솟값 return
public class Solution {
    public int solution(int n) {
        // 최소 건전지 사용량
        int ans = 0;
        
        while(n>0){
            if(n%2==0){
                n/=2;
            }
            else{
                n--;
                ans++;
            }
        }

        return ans;
    }
}

https://programmers.co.kr/learn/courses/30/lessons/49994?language=java

구현 문제이다.

처음 가본 길이를 구하는 알고리즘을 구현하면 된다.

해결 방안

문제를 크게 보면 dirs를 돌면서 게임 캐릭터를 움직여준다.

캐릭터 움직이는 함수는 moveCharacter이다.

1. char형 dir에 의해 nx, ny를 정해준다.

2. nx, ny의 범위를 확인해준다.
2.1 구해진 nx, ny가 -5~5 => 0~10이 되므로 nx, ny 둘 중 하나라도 0~10 범위를 벗어나면 해당 과정은 아무것도 안한다.

2.2. nx, ny가 둘다 0~10 범위 안에 든다면 이동을 하게 되는데 boolean형 4차원 배열을 이용하여 방문하지 않은 경우에 answer값을 +1 해주고 방문 체크를 해준다. cx,cy에서 nx,ny를 갈때 방향성을 가지지 않으므로 visited[cx][cy][nx][ny], visited[nx][ny][cx][cy] 둘다 true로 값을 변경해준다.
그리고 cx, cy를 nx, ny로 변경해준다. 

코드

// 방문 길이
// 캐릭터가 처음 걸어본 길이를 구하려고 함
// 좌표 평면의 경계를 넘어가는 명령어는 무시함
class Solution {
    
    static int answer = 0;
    
    // 현재 시작 위치
    static int cx = 5;
    static int cy = 5;
    static boolean[][][][] visited = new boolean[11][11][11][11];
    
    // U D R L 순
    static int[] dx = {0, 0, 1, -1};
    static int[] dy = {1, -1, 0, 0};
    
    public int solution(String dirs) {
        
        for(int i=0; i<dirs.length(); i++){
            char dir = dirs.charAt(i);
            
            moveCharacter(dir);
        }
        
        return answer;
    }
    
    // 경계 넘어가는지 체크(true면 경계 안)
    // 0~10
    static boolean inBoundary(int x, int y){
        if(x<0 || x>10 || y<0 || y>10)
            return false;
        
        return true;
    }
    
    static void moveCharacter(char dir){
        int nx = 0;
        int ny = 0;
        // 1. nx, ny 구해주기
        switch (dir){
            case 'U' :
                nx = cx + dx[0];
                ny = cy + dy[0];
                break;

            case 'D' :
                nx = cx + dx[1];
                ny = cy + dy[1];
                break;

            case 'R' :
                nx = cx + dx[2];
                ny = cy + dy[2];
                break;

            case 'L' :
                nx = cx + dx[3];
                ny = cy + dy[3];
                break;
        }

        // 2. nx, ny가 경계 넘어가는지 확인
        if(inBoundary(nx,ny)){

            // 3. 경계 안넘어가면 이동
            // 방문 안한 곳 이면 방문 체크 하고 answer++;
            if(!visited[nx][ny][cx][cy] && !visited[cx][cy][nx][ny]){
                visited[cx][cy][nx][ny] = true;
                visited[nx][ny][cx][cy] = true;
                answer++;
            }
            // 이동
            cx = nx;
            cy = ny;
        }
        
    }
}

https://programmers.co.kr/learn/courses/30/lessons/62048?language=java

최대 공약수를 이용해서 구할 수 있을 거라고까지 밖에 생각 하지 못해서 다른 사람의 코드를 참고하였다.

해결 방안

간단하게 말해서 전체에서 선이 그어지는 구간(흰색 부분)을 빼는 문제이다.

하지만 선이 그어지는 부분을 알아내는 방법이 어려웠다. 

세로와 가로를 보고 각각 3칸 2칸 간격으로 일정하게 잘려지는 것을 보고 최대공약수의 영향을 받는다고 생각하였다.

한 패턴당 선이 그어지는 부분은 (w/gcd + h/gcd -1), 반복되는 패턴 갯수는 gcd 만큼이다.

참고
https://velog.io/@ajufresh/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-%EB%A9%80%EC%A9%A1%ED%95%9C-%EC%82%AC%EA%B0%81%ED%98%95-%EB%AC%B8%EC%A0%9C%ED%92%80%EC%9D%B4-Java

* gcd 함수가 있다는 것을 발견하였다.

import java.math.* 라이브러리를 추가해주고
BigInteger.valueOf(int n1).gcd(BigInteger.valueOf(int n2))를 이용하여 gcd(최대공약수)를 구할 수 있다.

나중에 BigInteger로 구해진 값을 BigInteger변수.intValue()로 int형으로 바꿔줄 수 있다.

코드

import java.math.*;

// 멀쩡한 사각형
class Solution {
    public long solution(int w, int h) {
        long answer = 1;
        
        BigInteger num1 = BigInteger.valueOf(w);
        BigInteger num2 = BigInteger.valueOf(h);
        
        // 최대 공약수 구하는 함수
        int gcd = num1.gcd(num2).intValue();
        
        answer = ((long) w * (long) h) - ((((long) w / gcd) + ((long) h / gcd) - 1) * gcd);
        
        return answer;
    }
}

https://programmers.co.kr/learn/courses/30/lessons/12928?language=java

해결 방안

1~n 사이 숫자로 나눴을 때 나머지가 0이 되는 경우는 모두 약수이다.

코드

class Solution {
    public int solution(int n) {
        int answer = 0;
        
        for(int i=1; i<=n; i++){
            if(n%i==0) answer+=i;
        }
        return answer;
    }
}

https://programmers.co.kr/learn/courses/30/lessons/12921?language=java

해결 방안

주어진 숫자 n의 1~n 까지의 소수 갯수를 찾는 문제이다.

에라토스테네스의 체를 사용하여 i 가 소수인지 확인하였다.

코드

class Solution {
    public int solution(int n) {
        int answer = 0;
        
        for(int i=2; i<=n; i++){
            if(i==2){
                answer++;
                continue;
            }
            
            // 소수 아님
            if(i%2==0) continue;
            
            // 소수 아님
            boolean flag = true;
            for(int j=3; j<=(int)(Math.sqrt(i)); j+=2){
                if(i%j==0) {
                    flag = false;
                    break;
                }
            }
            if(flag){
                answer++;
            }
                
        }
    
        return answer;
    }
}

https://programmers.co.kr/learn/courses/30/lessons/12906?language=java

해결 방안

standard라고 기준을 만들고 기준과 같으면 중복된 숫자이므로 넘어가고 다른 숫자가 나오면 list에 넣어준다.

그 후 list를 int 배열에 옮겨준다.

코드

import java.util.*;

public class Solution {
    public int[] solution(int []arr) {
        int[] answer;
        List<Integer> list = new ArrayList<>();
        
        int standard = arr[0];
        list.add(arr[0]);
        for(int i=1; i<arr.length; i++){
            if(arr[i] == standard){
                continue;
            }
            else{
                standard = arr[i];
                list.add(arr[i]);
            }
        }
        
        answer = new int[list.size()];
        for(int i=0; i<list.size(); i++){
            answer[i] = list.get(i);
        }
        
        return answer;
    }
}