*Practice 1 : 올바른 괄호

 

괄호가 바르게 짝지어졌다는 것은 '(' 문자로 열렸으면 반드시 짝지어서 ')' 문자로 닫혀야 한다는 뜻입니다. 예를 들어

  • ()() 또는 (())() 는 올바른 괄호입니다.
  • )()( 또는 (()( 는 올바르지 않은 괄호입니다.

'(' 또는 ')' 로만 이루어진 문자열 s가 주어졌을 때, 문자열 s가 올바른 괄호이면 true를 return 하고, 올바르지 않은 괄호이면 false를 return 하는 solution 함수를 완성해 주세요.

 

s answer
()() true
(())() true
)()( false
(()( false
class Solution {
    boolean solution(String s) {
        boolean answer = false;
        int count = 0;
        for(int i = 0; i<s.length();i++){
            if(s.charAt(i) == '('){
                count++;
            }
            if(s.charAt(i) == ')'){
                count--;
            }
            if(count < 0){
                break;
            }
        }
        if(count == 0){
            answer = true;
        }
        return answer;
    }
}

 

 

*Practice 2 : 스킬트리

 

선행 스킬이란 어떤 스킬을 배우기 전에 먼저 배워야 하는 스킬을 뜻합니다.

예를 들어 선행 스킬 순서가 스파크 → 라이트닝 볼트 → 썬더일때, 썬더를 배우려면 먼저 라이트닝 볼트를 배워야 하고, 라이트닝 볼트를 배우려면 먼저 스파크를 배워야 합니다.

위 순서에 없는 다른 스킬(힐링 등)은 순서에 상관없이 배울 수 있습니다. 따라서 스파크 → 힐링 → 라이트닝 볼트 → 썬더와 같은 스킬트리는 가능하지만, 썬더 → 스파크나 라이트닝 볼트 → 스파크 → 힐링 → 썬더와 같은 스킬트리는 불가능합니다.

선행 스킬 순서 skill과 유저들이 만든 스킬트리1를 담은 배열 skill_trees가 매개변수로 주어질 때, 가능한 스킬트리 개수를 return 하는 solution 함수를 작성해주세요.

 

skill skill_trees return
CBD [BACDE, CBADF, AECB, BDA] 2
import java.util.*;

class Solution {
    public int solution(String skill, String[] skill_trees) {
        int answer = 0;
        ArrayList<String> skillTrees = new ArrayList<String>(Arrays.asList(skill_trees));
        //ArrayList<String> skillTrees = new ArrayList<String>();
        Iterator<String> it = skillTrees.iterator();

        while (it.hasNext()) {
            if (skill.indexOf(it.next().replaceAll("[^" + skill + "]", "")) != 0) {
                it.remove();
            }
        }
        answer = skillTrees.size();
        return answer;
    }
}

 

 

*Practice 3 : 큰 수 만들기

 

어떤 숫자에서 k개의 수를 제거했을 때 얻을 수 있는 가장 큰 숫자를 구하려 합니다.

예를 들어, 숫자 1924에서 수 두 개를 제거하면 [19, 12, 14, 92, 94, 24] 를 만들 수 있습니다. 이 중 가장 큰 숫자는 94 입니다.

문자열 형식으로 숫자 number와 제거할 수의 개수 k가 solution 함수의 매개변수로 주어집니다. number에서 k 개의 수를 제거했을 때 만들 수 있는 수 중 가장 큰 숫자를 문자열 형태로 return 하도록 solution 함수를 완성하세요.

 

 

number k return
1924 2 94
1231234 3 3234
4177252841 4 775841
import java.util.Stack;
class Solution {
    public String solution(String number, int k) {
        char[] result = new char[number.length() - k];
        Stack<Character> stack = new Stack<>();

        for (int i=0; i<number.length(); i++) {
            char c = number.charAt(i);
            while (!stack.isEmpty() && stack.peek() < c && k-- > 0) {
                stack.pop();
            }
            stack.push(c);
        }
        for (int i=0; i<result.length; i++) {
            result[i] = stack.get(i);
        }
        return new String(result);
    }
}

 

*Practice 4: 카펫

 

Leo는 카펫을 사러 갔다가 아래 그림과 같이 중앙에는 빨간색으로 칠해져 있고 모서리는 갈색으로 칠해져 있는 격자 모양 카펫을 봤습니다.

Leo는 집으로 돌아와서 아까 본 카펫의 빨간색과 갈색으로 색칠된 격자의 개수는 기억했지만, 전체 카펫의 크기는 기억하지 못했습니다.

Leo가 본 카펫에서 갈색 격자의 수 brown, 빨간색 격자의 수 red가 매개변수로 주어질 때 카펫의 가로, 세로 크기를 순서대로 배열에 담아 return 하도록 solution 함수를 작성해주세요.

 

brown red return
10 2 [4, 3]
8 1 [3, 3]
24 24 [8, 6]
class Solution {
    public int[] solution(int brown, int red) {
        int[] answer = new int[2];
        int red_x, red_y;
        for(int i = 1; i<=red; i++){
            if(red % i == 0){
                red_y = i;
                red_x = red/i;
                if(brown == 4 + red_x * 2 + red_y * 2){
                    answer[0] = red_x + 2;
                    answer[1] = red_y + 2;
                    return answer;
                }
            }
        }
        return answer;
    }
}
class Solution {
    public int[] solution(int brown, int red) {
        for(int i=1; i<=red; i++) {
            if(red%i==0 && (red/i+i)*2+4==brown) {
                return new int[] {red/i+2, i+2};
            }
        }
        return null;
    }
}

 

*Practice 5: 짝지어 제거하기

 

짝지어 제거하기는, 알파벳 소문자로 이루어진 문자열을 가지고 시작합니다. 먼저 문자열에서 같은 알파벳이 2개 붙어 있는 짝을 찾습니다. 그다음, 그 둘을 제거한 뒤, 앞뒤로 문자열을 이어 붙입니다. 이 과정을 반복해서 문자열을 모두 제거한다면 짝지어 제거하기가 종료됩니다. 문자열 S가 주어졌을 때, 짝지어 제거하기를 성공적으로 수행할 수 있는지 반환하는 함수를 완성해 주세요. 성공적으로 수행할 수 있으면 1을, 아닐 경우 0을 리턴해주면 됩니다.

예를 들어, 문자열 S = baabaa 라면

b aa baa → bb aa → aa 

의 순서로 문자열을 모두 제거할 수 있으므로 1을 반환합니다.

 

 

s result
baabaa 1
cdcd 0
import java.util.*;

class Solution
{
    public int solution(String s)
    {
        // 문자열을 캐릭터 배열로 변환
       char[] c = s.toCharArray();
       ArrayList<Character> list = new ArrayList<>();

       // 캐릭터를 하나씩 리스트에 삽입
       for(char _c : c){
           Add(list, _c);
       }

       // 만약 리스트가 비었다면 짝지거 제거 완료
       if(list.isEmpty()){
           return 1;
       }
       else {
           return 0;
       }
    }

     // 리스트에 캐릭터 하나씩 삽입하는 함수
    public static void Add(ArrayList _list, char _c){
        _list.add(_c);

        // 만약 리스트의 길이가 2보다 크고 && 마지막 두 원소가 같은 캐릭터라면
        if(_list.size() > 1 && (_list.get(_list.size() - 2) == _list.get(_list.size() - 1))){
                // 마지막 두 원소 제거
                _list.remove(_list.size() - 1);
                _list.remove(_list.size() - 1);
        }
    }
}

 

 

*Practice 6: 숫자의 표현

 

Finn은 요즘 수학공부에 빠져 있습니다. 수학 공부를 하던 Finn은 자연수 n을 연속한 자연수들로 표현 하는 방법이 여러개라는 사실을 알게 되었습니다. 예를들어 15는 다음과 같이 4가지로 표현 할 수 있습니다.

  • 1 + 2 + 3 + 4 + 5 = 15
  • 4 + 5 + 6 = 15
  • 7 + 8 = 15
  • 15 = 15

자연수 n이 매개변수로 주어질 때, 연속된 자연수들로 n을 표현하는 방법의 수를 return하는 solution를 완성해주세요.

 

n result
15 4
public class Expressions {

    public int expressions(int num) {
        int answer = 0;
        int result = 0;

        for(int i = 1; i<=num; i++){
            for(int j = i; j<=num; j++){
                result += j;
                if(result == num){
                    ++answer;
                } else if(result > num){
                    result = 0;
                    break;
                }
            }
        }

        return answer;
    }

    public static void main(String args[]) {
        Expressions expressions = new Expressions();
        // 아래는 테스트로 출력해 보기 위한 코드입니다.
        System.out.println(expressions.expressions(6));
    }
}

 

 

 

*Practice 7: 가장 큰 정사각형 찾기

 

1와 0로 채워진 표(board)가 있습니다. 표 1칸은 1 x 1 의 정사각형으로 이루어져 있습니다. 표에서 1로 이루어진 가장 큰 정사각형을 찾아 넓이를 return 하는 solution 함수를 완성해 주세요. (단, 정사각형이란 축에 평행한 정사각형을 말합니다.)

 

 

0 1 1 1
1 1 1 1
1 1 1 1
0 0 1 0

가 있다면 가장 큰 정사각형은 넓이는 9가 되므로 9를 반환해 주면 됩니다.

 

 

board answer
[[0,1,1,1],[1,1,1,1],[1,1,1,1],[0,0,1,0]] 9
[[0,0,1,1],[1,1,1,1]] 4
class Solution
{
    public int solution(int [][]board) {
        int answer = 0;
        if(board.length==1 && board[0].length==1) {
            if(board[0][0]==1) return 1;
            else return 0;
        }
        for(int y=1; y<board.length; y++) {
            for(int x=1; x<board[0].length; x++) {
                if(board[y][x]==1) {
                    board[y][x] = Math.min(board[y-1][x-1], Math.min(board[y][x-1], board[y-1][x])) + 1;
                }
                if(board[y][x]>answer) {
                    answer=board[y][x];
                }
            }
        }

        return answer*answer;
    }
}

class Solution
{
    public int solution(int [][]board)
    {
        int answer = 1;

        int[][] dp = new int[board.length+1][board[0].length+1];

        int maxLen = 0;
        for(int i=1;i<=board.length;i++){
            for(int j=1;j<=board[0].length;j++){
                if(board[i-1][j-1]==0){
                    dp[i][j]=0;
                }else{
                    dp[i][j] = Math.min(Math.min(dp[i-1][j-1],dp[i-1][j]),dp[i][j-1]) + 1;
                    maxLen = Math.max(maxLen,dp[i][j]);
                }
            }
        }

        answer = maxLen*maxLen;
        return answer;
    }
}

올바른 괄호

+ Recent posts