흰색기린

알고리즘 풀이 방법입니다.
문제(Problem) -> 생각(Think) -> 해결책(Solution) -> 리뷰(Review) 를 통해서 정리해서 작성합니다.

Problem📄

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

Think🤔

문제 이해
인풋   : 1001110
아웃풋  : 1010011 
인풋의 1의 개수와 아웃풋의 1의 개수가 같음 그럼 반환

Solution✍

class Solution {
    public int solution(int n) {
        int answer = 0;
        
        final int first = oneNumCnt(n);
        while (true) {
            n++;
            if(first == oneNumCnt(n)){
                answer = n;
                break;
            }
        }
        
        return answer;
    }
    
    public static int oneNumCnt(int num){
        int  cnt = 0;
        while(num > 0) {
            if(num % 2 == 1){cnt++;}
            num = num / 2;
        }
        return cnt;
    }
    
}

Review🤩

2진변환 공식을 알면 쉽게 풀 수 있다.

알고리즘 풀이 방법입니다.
문제(Problem) -> 생각(Think) -> 해결책(Solution) -> 리뷰(Review) 를 통해서 정리해서 작성합니다.

Problem📄

https://www.acmicpc.net/problem/15886

Think🤔

문제는 이동해서 EW 이런식으로 +1 , -1 이렇게 되는게 아니라 연결이 되어 있는지를 물어보는 문제

Solution✍

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

public class Back15886 {
    public static void main(String[] args) {
        // String str = "EEWWEW"; 입력 6 
        int cnt = 1;
        try {
            BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
            int mapNum = Integer.parseInt(br.readLine());
            String move = br.readLine();
            for(int i=1; i<mapNum; i++){
                if(move.charAt(i) == 'E' && move.charAt(i-1) == 'W'){
                    cnt++;
                }
            }

            System.out.println(cnt);
        } catch(IOException e){
            System.out.println(e.getMessage());
        }
    }
}

EWWWEWWW

이렇게 굵은 글씨 처럼 WE가 다시 나타나는 부분에서 길은 끊기기 때문에 구사과의 이동패턴에 선물을 둘 수 있다.

Review🤩

문제 이해하는데 거의 하루 ,,, 넘나 어렵 ㅠ

알고리즘 풀이 방법입니다.
문제(Problem) -> 생각(Think) -> 해결책(Solution) -> 리뷰(Review) 를 통해서 정리해서 작성합니다.

Problem📄

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

Think🤔

처음에 재귀함수를 만들어서 반복문으로 돌게했는데 이렇게 하면 계속해서 함수를 타기 때문에

시간 초과가 나온다.

public class pibo {
    public static void main(String[] args) {
        int n = 2000;
        int answer = 0;

        answer = pibo(n-2) + pibo(n-1);

        System.out.println(answer);
    }

    public static int pibo(int num){
        if(num <= 1){return num;}

        return pibo(num-2) + pibo(num - 1);
    }
}

// 시간 초과 재귀적으로 타게 하면

그 다음 방법으로 재귀 말고 배열을 생성해서 캐쉬를 이용해서 풀었다.

반복문은 2부터 시작하게 하고 , 배열 0 , 1은 미리 선언해둔다.

이런식으로 하게 되면

반복문을 돌면서

pibo[10] = pibo[9] + pibo[8] 이렇게 되면 해당 pibo[9]는 그 전 반복문을 이용해서 저장했기 때문에 함수를 다시 타지 않고 풀 수 있다. 

Solution✍

class Solution {
    public int solution(int n) {
        return pibo(n);
    }

    public static int pibo(int num){
        int cache[] = new int[num+1]; // 캐쉬 남겨둠

        if(num <= 1){return num;}

        cache[0] = 0;
        cache[1] = 1;

        for(int i=2; i<=num; i++){
            cache[i] = (cache[i-1] + cache[i-2]) % 1234567;
        }

        return cache[num];
    }
}

Review🤩

% 1234567을 하게 되어있는데, 이는 피보나치 수로 더하게 되면 값이 기하급수적으로 커져서, int의 범위를 빠르게 넘어갈 수 있기 때문... int의 범위는 –2,147,483,648 ~ 2,147,483,647 이렇게 되어 있는데 2,147,483,647 에서 1바이트만 커져도

– 2,147,483,648 가 될 수 있기 때문!! 

더 자세한 설명은 찾아보시길..

알고리즘 풀이 방법입니다.
문제(Problem) -> 생각(Think) -> 해결책(Solution) -> 리뷰(Review) 를 통해서 정리해서 작성합니다.

Problem📄

https://www.acmicpc.net/problem/11558

Think🤔

문제 이해 3일 걸림..

첫 줄에 테스트 케이스 T 존재 [ 문제에서는 1로 나와있지만 2일 경우 두번의 결과값이 나오게 하면 됨 ]

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

public class Back11558 {
    public static void main(String[] args) throws IOException{
        try {
            BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
            int T = Integer.parseInt(bf.readLine());    // 테스트 케이스 숫자 T
            int ret = Integer.parseInt(bf.readLine());  // 플레이어 숫자, 주경이

            while(T-- > 0){
                int[] player = new int[ret+1];
                for(int i=0; i<ret; i++){
                    player[i+1] = Integer.parseInt(bf.readLine());
                }

                int point = player[1];

                int cnt = 0;
                for(int i=1; i<ret; i++){
                    if(player[i] == ret){
                        break;
                    }
                    cnt++;
                    point = player[i];
                }
                int answer = (cnt+1 == ret ? 0 : point);
                System.out.println(answer);
            }

        } catch (IOException e){
            System.out.println(e.getMessage());
        }

    }
}

이 코드의 문제점은 희현이가 주경이를 걸리게 했을 때 도달하지 못하는게 아니라 마지막에 도달할 수 있으므로
플레이어의 수와 카운트로 반복문을 다 돌게 하는 방법은 옳지 않다. 마지막에 도달하는 테스트 케이스는 다 탈락할 것
방문했을때를 체크해주는 visits을 배열로 하나 더 둬서 체크하게 해줘야 한다.

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

public class Back11558 {
    public static void main(String[] args) throws IOException{
        try {
            BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
            int T = Integer.parseInt(bf.readLine());    // 테스트 케이스 숫자 T

            while(T-- > 0){
                int ret = Integer.parseInt(bf.readLine());  // 플레이어 숫자, 주경이
                int[] player = new int[ret+1];
                boolean[] visits = new boolean[ret+1];

                // player[0] = 0; 배열 생성 시 0으로 초기화 하기 때문에 굳이 필요없음
                for(int i=1; i<=ret; i++){
                    player[i] = Integer.parseInt(bf.readLine());
                }

                int status = 0;
                int point = 1;
                int cnt = 0;

                while(true){
                    if(player[point] == ret){
                        cnt++;
                        break;
                    }

                    if(visits[player[point]] == true){
                        status = 1;
                        break;
                    }else{ // 첫 방문
                        point = player[point]; // 다음 방문할 곳
                        visits[point] = true;
                        cnt++;
                    }
                }
                if(status == 1){
                    System.out.println("0");
                }else{
                    System.out.println(cnt);
                }
            }

        } catch (IOException e){
            System.out.println(e.getMessage());
        }

    }
}

Status 변수 필요 없이 cnt로 제출해도 통과

물론 제출할때는 catch 부분 삭제 catch다음에 필요한 로직이 없으므로..

Solution✍

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

public class Main {
    public static void main(String[] args) /* throws IOException try-catch 했으므로 필요 없음 없을 시 예외를 발생시킨다 선언*/{

        try {
            BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
            int T = Integer.parseInt(bf.readLine()); 

            while(T-- > 0){
                int ret = Integer.parseInt(bf.readLine()); 
                int[] player = new int[ret+1];
                boolean[] visits = new boolean[ret+1];

                for(int i=1; i<=ret; i++){
                    player[i] = Integer.parseInt(bf.readLine());
                }

                int point = 1;
                int cnt = 0;
                
                while(true){
                    if(player[point] == ret){
                        cnt++;
                        break;
                    }

                    if(visits[player[point]] == true){
                        cnt = 0;
                        break;
                    }else{ // 첫 방문
                        point = player[point]; 
                        visits[point] = true;
                        cnt++;
                    }
                }
                System.out.println(cnt);
            }

        } 

    }
}

Review🤩

반복 숙달.... 실행 ....

알고리즘 풀이 방법입니다.
문제(Problem) -> 생각(Think) -> 해결책(Solution) -> 리뷰(Review) 를 통해서 정리해서 작성합니다.

Problem📄

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

Think🤔

1. 0 먼저 제거
2. 남은 숫자 2진법으로 변환

String으로 주어졌으니 일단 replaceAll을 이용해서 0을 전부 ""(공백)으로 바꿔준 후
그 자릿수 length를 변수에 받고 2진 변환을 한다.
2진 변환한 결과를 가지고 계속해서 반복한 후 "1" 이 되면 멈춘다.

반복문 돈 횟수를 배열의 0번째 인덱스에 넣어주고, 1번째 인덱스에 0을 제거한 값을 넣어준다.

Solution✍

public class Main {
    public static void main(String[] args) {
        String s = "110010101001"; // 정답 [ 3,8 ]
        // 01110 [ 3,3 ]      1111111 [ 4,1 ]
        // s가 1이 되면 2진변환 종료

        // 110010101001 -> 시작
        // 111111 -> 6
        // 110
        // 11 -> 2
        // 10
        // 1  -> 종료
        int zeroCnt = 0;
        int changeCnt = 0;

        int[] answer = new int[2];
        while(!s.equals("1")){
            for(int i=0; i<s.length(); i++){
                if(s.charAt(i) == '0'){
                    zeroCnt++;
                }
            }
            s = binaryChange(s);
            changeCnt++;
        }
        System.out.println(zeroCnt);
        System.out.println(changeCnt);

    }

    public static String binaryChange(String num){
        int binaryNum = num.replaceAll("0","").length(); // 6
        String tmp = "";

        while(binaryNum > 0){
            tmp += String.valueOf(binaryNum % 2);
            binaryNum = binaryNum / 2;
        }

        return tmp;
    }
}

프로그래머스용 제출 코드

class Solution {
    public int[] solution(String s) {
        
        int zeroCnt = 0;
        int changeCnt = 0;
        
        while(!s.equals("1")){
            for(int i=0; i<s.length(); i++){
                if(s.charAt(i) == '0'){
                    zeroCnt++;
                }
            }
            s = binaryChange(s);
            changeCnt++;
        }
        int[] answer = {changeCnt,zeroCnt};
        return answer;
    }
    
    public static String binaryChange(String num){
        int binaryNum = num.replaceAll("0","").length(); // 6
        String tmp = "";

        while(binaryNum > 0){
            tmp += String.valueOf(binaryNum % 2);
            binaryNum = binaryNum / 2;
        }

        return tmp;
    }
}

Review🤩

갑자기 다시 푸니깐 풀림 ~ 흠흠

알고리즘 풀이 방법입니다.
문제(Problem) -> 생각(Think) -> 해결책(Solution) -> 리뷰(Review) 를 통해서 정리해서 작성합니다.

Problem📄

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

Think🤔

스택을 이용한 구현

Solution✍

import java.util.Stack;

class Solution {
    boolean solution(String s) {
        boolean answer = true;
        
		Stack<Character> st = new Stack<>();
		
		for(int i=0; i<s.length(); i++){
            if(s.charAt(i) == ')' && st.isEmpty()){
				return false;
			}else if(s.charAt(i) == '('){
				st.push('(');
			}else {
				st.pop();
			}
			

		}
		
		if(st.size() > 0){
			answer = false;
		}
			
        return answer;
    }
}

Review🤩

괄호가 안남고 잘 닫히면 성공!