알고리즘 문제풀이 2-3

문제 1 / Bracket

목표 : (, ), {, }, [, ], <, > 4가지 종류 괄호가 서로 교차하지 않은 형태로 짝이 맞게 이루어진 문자열이면 1, 틀리면 0을 반환

해결방법 : 문자가 열린 괄호면 stack에 채워주고 다음 들어오는 괄호가 stack에 있는 마지막 괄호의 닫는 괄호이면 제거해서 stack이 비어있으면 짝이 맞는 문자열이다.

public int solution(String S) {
    int answer = 0;
    Stack<Character> stack = new Stack<>();

    for(char c : S.toCharArray()) {
        if(c=='(' || c=='{' || c=='[' || c=='<') {
            stack.push(c);
        } else {
            if(c==')' && stack.peek()=='(') {
                stack.pop();
            } else if(c=='}' && stack.peek()=='{') {
                stack.pop();
            } else if(c==']' && stack.peek()=='[') {
                stack.pop();
            } else if(c=='>' && stack.peek()=='<') {
                stack.pop();
            }
        }
    }
    answer = stack.isEmpty() ? 1 : 0;
    return answer;
}

문제 2 / RepeatAlphabet

목표 : 문자열을 확인하여 2회 연속 동일한 문자가 나타나면 해당 두 문자를 소거한다. 완전히 소거되어 빈 문자열이면 1, 남아있으면 0을 반환

해결방법 : 이 또한 위와 같은 형식으로 풀었다.

public int solution(String S) {
    int answer = 0;
    Stack<Character> stack = new Stack<>();

    for(char c : S.toCharArray()) {
        if(!stack.isEmpty() && stack.peek()==c) {
            stack.pop();
        } else {
            stack.push(c);
        }
    }
    answer = stack.isEmpty() ? 1 : 0;
    return answer;
}

문제 3 / FoodBj

목표 : 사람이 음식을 다 먹을시 상금 150만원을 받는다. 이는 1그릇 or 2그릇 이상은 먹고 3그릇 먹는 사람이 우승자이므로 우승자를 형식에 맞게 출력.
출력 형식 : xxx만원(성명)

해결방법 : one이 1그릇 two가 2그릇 먹은 사람 이름이 있어 bj명이 저 두 배열에 없다면 우승자로 생각하고 총 금액을 구해서 해결했다.

public String solution(String[] bj, String[] one, String[] two) {
    String answer = "";
    int oneCnt = one.length;
    int twoCnt = two.length;
    ArrayList<String> list = new ArrayList<>(Arrays.asList(bj));

    for(String s : one) {
        if(list.contains(s)) list.remove(list.indexOf(s));
    }

    for(String s : two) {
        if(list.contains(s)) list.remove(list.indexOf(s));
    }
    answer = (150*oneCnt+300*twoCnt+450)+"만원("+list.get(0)+")";
    return answer;
}

문제 4 / AsciiToString

목표 : 정수 배열은 ASCII Code로 치환 후 문자열로 출력

해결방법 : 정수 배열엔 영문자 대/소문자의 ASCII Code만이 들어있어서 a와 z사이 A와 Z사이면 char로 변경해 문자열을 만들었다.

public String solution(int[] arr) {
    String answer = "";
    for(int num : arr) {
        if(num>=65 && num<=90 || num>=97 && num<=122) {
            char c = (char)(num);
            answer += c;
        }
    }
    return answer;
}

문제 5 / Calculator

목표 : 문자열로 이루어진 계산식의 계산 결과를 출력

해결방법 : 숫자와 연산을 따로 배열로 만들어 계산식 구현. 테스트 케이스의 처음 숫자가 음수였어서 연산과 숫자의 갯수가 같다고 생각해서 틀린 코드를 구현했지만 생각하다 보니 첫 숫자가 상수이면 ArrayIndexOutOfBoundsException 에러가 발생할 거 같아 테스트 케이스를 추가해서 확인해보니 역시나 에러가 발생했다.

그래서 처음 숫자가 음수인 경우와 상수인 경우를 구분해서 문제를 해결할 수 있었다.

맞긴 했지만 틀린 코드
(처음이 상수이면 ArrayIndexOutOfBoundsException 에러 발생)

public int solution(String s) {
    int answer = 0;
    String[] nums = s.replaceAll("[^0-9]+", " ").trim().split(" ");
    String[] operation = s.replaceAll("[^-+]+", " ").trim().split(" ");
    boolean isMinus = false;
    
    for(int i=0; i<nums.length; i++) {
        if(operation[i].equals("+")) isMinus=false;
        if(operation[i].equals("-")) isMinus = true;
        if(isMinus) {
            answer -= Integer.parseInt(nums[i]);
        } else {
            answer += Integer.parseInt(nums[i]);
        }
    }
    return answer;
}

정답코드

public int solution(String s) {
    int answer = 0, result = 0;
    String[] nums = s.replaceAll("[^0-9]+", " ").trim().split(" ");
    String[] operation = s.replaceAll("[^-+]+", " ").trim().split(" ");
    
    int idx=0;
    if(nums.length>operation.length) {
        result = Integer.parseInt(nums[idx++]);
        answer = calculation(operation, nums, idx, result);
    }
    else {
        answer = calculation(operation, nums, idx, result);
    }
    return answer;
}
static int calculation(String[] operation, String[] nums, int idx, int result) {
    boolean isMinus = false;
    for(int i=0; i<operation.length; i++) {
        if(operation[i].equals("+")) isMinus=false;
        if(operation[i].equals("-")) isMinus = true;
        if(isMinus) {
            result -= Integer.parseInt(nums[idx++]);
        } else {
            result += Integer.parseInt(nums[idx++]);
        }
    }
    return result;
}