BangBang's Devlogs

문제

그리디 문제이다.

해결 방안

처음에 R과 B의 갯수를 각각 세어서 rCnt, bCnt에 저장해준다.

그리디 문제로 볼을 이동하는 4가지 방법 중 최소 이동횟수를 구하면 된다.

1. R공을 모두 왼쪽으로 이동
문제의 그림1을 볼때 RRRRBBBB로 나열하기 위해서는 첫번째 R을 제외하고는 다 옮겨줘야 한다.
따라서 왼쪽에 R이 계속 있을경우 cnt를 세어준다음 Rcnt-cnt는 이동해야하는 R공의 갯수가 된다.
ex) RBBBRBRRR인 경우 첫번째 R이 있으므로 cnt = 1이된다. 따라서 Rcnt(5)-cnt(1)=4가 되고 실제로 왼쪽으로 이동해야하는 R공의 갯수가 된다.

2. R공을 모두 오른쪽으로 이동

3. B공을 모두 왼쪽으로 이동

4. B공을 모두 오른쪽으로 이동

2,3,4번도 뒤에서부터 세야되나 B공을 세야되나에 따라 각각 코드가 조금씩 달라지는거 외에는 같은 원리이다.
자세한 것은 코드를 보면 충분히 이해 가능하다.

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;

// 한국정보올림피아드
// KOI 2019 2차대회 초등부
// 볼 모으기
public class Main {

	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		String colors = br.readLine();
		int result = N;
		int rCnt = 0;
		int bCnt = 0;
		
		for(int i=0; i<N; i++) {
			if(colors.charAt(i)=='R') 
				rCnt ++;
			else
				bCnt ++;
		}
		
		int cnt = 0;
		// 4가지 경우
		// 1. R만 움직여서 RRRBBB(R을 다 왼쪽으로)
		for(int i=0; i<N; i++) {
			if(colors.charAt(i)=='R')
				cnt++;
			else
				break;
		}
		result = Math.min(result, rCnt-cnt);
		
		// 2. R만 움직여서 BBBRRR
		cnt = 0;
		for(int i=N-1; i>=0; i--) {
			if(colors.charAt(i)=='R')
				cnt++;
			else
				break;
		}
		
		result = Math.min(result, rCnt-cnt);
		
		// 3. B만 움직여서 BBBRRR
		cnt = 0;
		for(int i=0; i<N; i++) {
			if(colors.charAt(i)=='B')
				cnt++;
			else
				break;
		}
		result = Math.min(result, bCnt-cnt);
		
		// 4. B만 움직여서RRRBBB
		cnt = 0;
		for(int i=N-1; i>=0; i--) {
			if(colors.charAt(i)=='B')
				cnt++;
			else
				break;
		}
		
		result = Math.min(result, bCnt-cnt);
		
		System.out.println(result);
		
	}

}

www.acmicpc.net/problem/17614

문제

 369 규칙에 맞게 1~N까지 나왔을때 N까지 박수의 총 횟수를 출력하는 것이다.

해결 방안

1~N까지 완전 탐색을 해주며 각 수의 자릿수들이 3,6,9인경우 result 변수를 하나씩 증가해주었다.

ex) 13 이면 박수 한번 33이면 박수 두번 가 되야 하므로

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

// 한국정보올림피아드
// KOI 2019 2차대회 초등부
// 369
public class Main {

	public static void main(String args[]) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		String sN = "";
		int result = 0;
		
		char n;
		for(int i=1; i<=N; i++) {
			sN = Integer.toString(i);
			
			for(int j=0; j<sN.length(); j++) {
				n = sN.charAt(j);
				if(n=='3' || n=='6' || n=='9') {
					result++;
				}
			}
		}
		System.out.println(result);
	}
	
}

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

그냥 구현 문제 입니다. 문제에 주어진 조건에 맞춰 풀면 되는 문제이다.

해결 방안

키패드의 위치를 x, y로 생각해주었다.
00~02
..
30~32

1. 일단 문제의 조건4에서 2,5,8,0 숫자 키패드가 나온경우 두 엄지손가락의 현재 키패드 위치에서 더 가까운 엄지 손가락을 사용한다고 하였으므로 왼손, 오른손 엄지의 위치를 저장할 변수를 선언해주었다.(lLoc, rLoc)
(이때, lLoc(왼손 엄지 위치)의 초깃값은 * 키패드의 위치인 {3,0}으로 rLoc(왼손 엄지 위치)의 초깃값은 # 키패드의 위치인 {3,2}로 설정해주었다.)

2. 각 숫자 패드의 위치를 ArrayList<int[]> locList에 저장해주었다. (locList.get(i) 하면 i 키패드의 위치가 나올 수 있게)

3. 조건2, 조건3과 같이 147, 369가 나온경우 각각 왼손 위치, 오른손 위치를 저장해주고 answer에는 L, R을 추가해준다.

4. 조건 4같이 2580이 나온경우 왼, 오른손과의 거리를 구해주고 더 가까운 손을 answer에 추가해준다.
이때 같으면 hand에 영향을 받도록 구현하였다.

(자세한 것은 코드의 주석 참고!)

코드

import java.util.*;
// 키패드 누르기
class Solution {
    
    // 00~02
    // ..
    // 30~32
    static int[] lLoc = {3, 0}; // 왼 엄 위치(*)
    static int[] rLoc = {3, 2}; // 오 엄 위치(#)
    static List<int[]> locList = new ArrayList<>();
    
    public String solution(int[] numbers, String hand) {
        String answer = "";
        
        int x = 0;
        int y = 0;
        // 0~9 키패드 위치 저장
        for(int i=0; i<=9; i++){
            if(i==0) 
                locList.add(new int[]{3,1});
            else{
                locList.add(new int[]{x, y});
                y++;
                if(y % 3 == 0){
                    y = 0;
                    x++;
                }
            }
        }
        
        // 가운데 패드와 왼, 오른 엄지손가락 거리
        int lDistance = 0;
        int rDistance = 0;
        StringBuilder sb = new StringBuilder();
        for(int i=0; i<numbers.length; i++){
            // 147
            if(numbers[i] == 1 || numbers[i] == 4 || numbers[i] == 7){
                sb.append("L");
                lLoc = locList.get(numbers[i]);
            }
            // 369
            else if(numbers[i] == 3 || numbers[i] == 6 || numbers[i] == 9){
                sb.append("R");
                rLoc = locList.get(numbers[i]);
            }
            // 2580
            else{
                // 거리 계산
                lDistance = Math.abs(lLoc[0]-locList.get(numbers[i])[0]) + Math.abs(lLoc[1]-locList.get(numbers[i])[1]);
                rDistance = Math.abs(rLoc[0]-locList.get(numbers[i])[0]) + Math.abs(rLoc[1]-locList.get(numbers[i])[1]);
                
                // 거리가 같으면 손잡이 따라감
                if(lDistance == rDistance){
                    if(hand.equals("right")){
                        sb.append("R");
                        rLoc = locList.get(numbers[i]);
                    }
                    else if(hand.equals("left")){
                        sb.append("L");
                        lLoc = locList.get(numbers[i]);
                    }
                }
                // 왼쪽
                else if(lDistance < rDistance){
                    sb.append("L");
                    lLoc = locList.get(numbers[i]);
                }
                // 오른쪽
                else if(rDistance < lDistance){
                    sb.append("R");
                    rLoc = locList.get(numbers[i]);
                }
            }
            
        }
        answer = new String(sb);
            
        return answer;
    }
}

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