2022.09.24 알고리즘 공부

프로그래머스

(스택/큐) 올바른 괄호

class Solution {
    boolean solution(String s) {
        boolean result = false;
        
        int count = 0;
        
        // '('일때 + ')'일때 - 한 후 마지막 0이되면 됨
        // 중간에 ')'가 먼저나와서 count가 음수가 되면 false
        
        for (int i=0; i<s.length(); i++) {
            if (s.charAt(i) == '(') {
                count++;
            } else if (s.charAt(i) == ')') {
                count--;
            }
            if (count < 0) {
                break;
            }
        }
        
        if (count == 0) {
            result = true;
        }
        
        
        return result;
    }
}

 

(연습문제) 숫자의 표현

class Solution {
    public int solution(int n) {
       
        // 주어진 숫자만큼 for문을 돌리면서
        // 1부터 다음숫자를 하나씩 더해가면서 주어진 숫자를 찾음
        // 주어진 숫자보다 작으면 계속 더하고
        // 주어진 숫자와 같아지면 count를 올리고 break
        // 주어진 숫자보다 커지면 count하지않고 break
        
        int count = 0;
        
        for (int i=1; i<=n; i++) {
            int sum = 0;
            for (int j=i; j<=n; j++) {
                // i부터 더하기 시작하니까 sum=0으로 시작하는게 맞음
                sum += j;
                if (sum == n) {
                    count++;
                    break;
                } else if (sum > n) {
                    break;
                } 
            }
        }
        
        return count;
        
    }
}

(연습문제) 다음 큰 숫자

class Solution {
    public int solution(int n) {
        
        int n_cnt = Integer.bitCount(n); // 2진수 변환 후 포함된 1의 개수를 카운트 하는 메서드
        
        int result = 0;
        
        n++; 
        
        while (true) {
            result = Integer.bitCount(n);
            if (n_cnt == result) {
                result = n;
                break;
                
            } else {
                n++;
            }
        }
        
        return result;
    }
}

 

(연습문제) 카펫

class Solution {
    public int[] solution(int brown, int yellow) {
        int[] answer = new int[2];
        
        // 결과값의 곱 = brown + yellow
        int area = brown + yellow;
        
        //가로 >= 세로
        
        for (int i=3; i<=area; i++) {
            int heigth = area/i; //세로
            int weigth = i; //가로
            
            if ((heigth-2)*(weigth-2) == yellow) {
                answer[1] = weigth;
                answer[0] = heigth;
                return answer;
            }
        }
        
        
        return answer;
    }
}

(2017 팁스타운) 짝지어 제거하기

import java.util.*;

class Solution
{
    public int solution(String s)
    {
        int answer = -1;
        
        Stack<Character> stack = new Stack<>();
        char[] arr = s.toCharArray();
        
        for(int i=0; i<s.length(); i++) {
            char c = arr[i];
            if (stack.isEmpty()) {
                stack.push(c);
            } else if (stack.peek() == c) {
                stack.pop();
            } else {
                stack.push(c);
            }
            
        }
        
        if (stack.isEmpty()) {
            answer = 1;
        } else {
            answer = 0;
        }
            

        return answer;
    }
}

(HashMap) 영어 끝말잇기

import java.util.*;

class Solution {
    public int[] solution(int n, String[] words) {
        int[] answer = new int[2];
        
        int gameCount = 1; // 몇번째 게임인지
        int peopleCount = 0; // 몇번째 사람인지
        
        String prev = "";
        Map<String, Integer> map = new HashMap<>();
        
        for (int i=0; i<words.length; i++) {
            String now = words[i];
            peopleCount++; // 차례
            
            if (i>0) {
                char prevChar = prev.charAt(prev.length()-1);
                // 두번째부터는 이전 단어의 마지막 글자 확인
                char nowChar = now.charAt(0); // 첫글자 확인
                if (prevChar != nowChar || map.containsKey(now)) {
                    // 일치하지 않거나 중복된 단어를 말하면 게임이 끝난거니까 결과값에 저장
                    answer[0] = peopleCount;
                    answer[1] = gameCount;
                    break; // 게임 종료
                }
            }
            // 게임이 끝나지 않은 경우
            map.put(now, 0);
            prev = now;
            
            if (peopleCount == n) {
                // 마지막사람의 차례가 온 경우 다시 처음부터하고 게임의 턴은 증가
                peopleCount = 0;
                gameCount++;
            }
            
        }
        
        return answer;
    }
}