프로그래머스(멀쩡한 사각형, 쇠막대기) - Java

[멀쩡한 사각형]

https://programmers.co.kr/learn/courses/30/lessons/62048

코딩테스트 연습 - 멀쩡한 사각형

 

* 로직

• 최대 공약수를 통해 대각선을 그었을 때 구할 수 있는 사각형 비율을 구할 수 있다
• 해당 비율의 사각형에서 대각선에 닿는 사각형의 개수는 (가로 비율 + 세로 비율) - 1 개이다
• 비율에 따라 자를 수 있는 사각형의 개수는 최대 공약수의 값이 된다
• 즉, 전체 개수 - ((가로 비율 + 세로 비율) -1) * 최대 공약수가 된다

 

//멀쩡한 사각형
public class Problem_NormalSquare {

    public static void main(String[] args) {
        int w = 8;
        int h = 12;
        long answer = solution(w, h);

        System.out.println(answer);
    }

    public static long solution(int w,int h) {
        long answer = 1;

        //최대 공약수
        long W = Long.valueOf(w);
        long H = Long.valueOf(h);
        long gcd = W >= H ? getGcd(W, H) : getGcd(H, W);

        long total = W * H;
        long crop_w = W / gcd;
        long crop_h = H / gcd;

        //최대 공약수만큼 사각형이 잘림
        answer = total - (crop_w + crop_h - 1) * gcd;

       return answer;
    }

    private static long getGcd(long a, long b) {
        if(a % b == 0){
            return b;
        }
        return getGcd(b, a%b);
    }
}

 

 

[쇠막대기]

https://programmers.co.kr/learn/courses/30/lessons/42585

코딩테스트 연습 - 쇠막대기

 

* 로직

• 괄호가 바로 열고 닫히는 부분이 레이저이기 때문에 해당 부분들을 모두 1로 변환한다
• 변환된 문자열을 하나씩 꺼내어 비교한다
  
  • 만약 "(" 라면 => 스택에 추가한다
  • 만약 ")" 라면 => 쇠막대기 하나가 끝나기 때문에 answer += 1을 해주고, 스택을 pop한다
  • 만약 "1" 이라면
    • 스택 사이즈가 0이면 => 아무 효능 x
    • 스택 사이즈가 >= 1이면 => answer += 스택 사이즈

 

//쇠막대기
import java.util.Stack;

public class Problem_IronBar {

    public static void main(String[] args) {
        String arrangement = "()(((()())(())()))(())";
        int answer = solution(arrangement);

        System.out.println(answer);
    }

    public static int solution(String arrangement) {
        int answer = 0;
        arrangement = arrangement.replace("()", "1");

        Stack<String> stack = new Stack<>();
        for(int s=0; s<arrangement.length(); ++s){
            String word = arrangement.substring(s, s+1);

            //레이져를 만났다면
            if(word.equals("1")){

                //만약 스택에 아무것도 없다면 -> 쇠막대기가 없다 -> pass
                if(stack.size() > 0) answer += stack.size();
            }

            else if(word.equals("("))
                stack.add(word);

            //닫힌 괄호를 만났다면 쇠막대기 한개 제거
            else if(word.equals(")")){
                answer += 1;
                stack.pop();
            }
        }

        return answer;
    }
}