알고리즘 문제풀이 2-2

문제 1 / ReverseSentence

목표 : 구분자인(.), (,), (!), (?), ( )를 기준으로 단어를 구분해 각 단어를 거꾸로 뒤집어 모은 문자열 배열을 출력하는 프로그램 작성

해결과정 : s.replaceAll("["+regex+"]", " ") 이 부분은 regex에 포함된 문자 하나하나를 정규식으로 " "로 변경해주는 코드이다. 그러고 마지막 문자 뒤 공백이 있을 수 있어서 제거해주고 StringBuffer에 공백이 아닌 문자들만 추가해 reverse()를 통해 거꾸로 뒤집어 구할 수 있었다.

public String[] solution(String s) {
    StringBuffer sb = new StringBuffer();
    String regex = ".,!? ";
    s = s.replaceAll("["+regex+"]", " ").trim();
    String[] strs = s.split(" ");
    int len=0, idx=0;;
    for(String str : strs) {
        if(!str.equals("")) len++;
    }
    String[] answer = new String[len];
    for(int i=0; i<strs.length; i++) {
        if(strs[i].equals("")) continue;
        // 현재 단어 이전에 값이 있다면 삭제해줌
        sb.delete(0, sb.length());
        for(int j=0; j<strs[i].length(); j++) {
            sb.append(strs[i].charAt(j));
        }
        answer[idx++] = sb.reverse().toString();
    }
    return answer;
}

문제 2 / GreatestCommonFactor

목표 : 정수 배열 A에 0보다 큰 숫자 N개의 모든 숫자의 최대 공약수를 구하기

해결과정 : 가장 기본인 최대공약수 구하는 방법으로 해결할 수 있었다.

public int solution(int[] A) {
    int answer = 0;
    if(A.length==1) return A[0];

    answer = A[0];
    for(int i=1; i<A.length; i++) {
        answer = findGcd(answer, A[i]);
    }
    return answer;
}
static int findGcd(int num1, int num2) {
    if(num1%num2==0) return num2;
    return findGcd(num2, num1%num2);
}

문제 3 / NthCanceledOrder

목표 : 주문 번호는 주문 순서대로 1부터 1씩 증가, 주문 취소될 경우 주문 번호는 주문 내역에서 제외됨. orders는 주문 내역이고 n번 째 주문 취소된 번호 구하기

해결과정 : 이 문제는 만약 orders의 가장 큰 값이 마지막 주문 내역이라고 생각하고 풀어서 처음엔 틀렸었다. 왜 틀렸을까 생각을 하다 orders에 가장 큰 값 이후 취소된 경우가 있을 수 있겠다라는 생각을 해 그 경우를를 추가해줘서 구할 수 있었다.

public int solution(int[] orders, int n) {
    int answer=0, idx=0, cnt=0;
    for(int i=1; i<=orders[orders.length-1]; i++) {
        if(orders[idx]==i) {                
            idx++;
        } else {
            cnt++;
        }
        if(cnt==n) {
            answer=i;
            break;
        }
    }
    if(cnt<n) {
        answer = orders[orders.length-1]+n-cnt;
    }
    return answer;
}

문제 4 / MostClosestNumberToZero

목표 : 0에 가장 가까운 수를 출력

해결 방법 : 배열의 제한 사항이 0이상으로 되어있어서 정렬 후 가장 앞에 있는 값을 받아와 출력했다.

public int solution(int[] arr) {
    Arrays.sort(arr);
    return arr[0];
}

문제 5 / RemoveDuplicatedWord

목표 : 문자열에 연속한 2개의 같은 문자가 존재하지 않도록 만들기

해결과정 : 처음엔 "aaabbabaabbb"로 입력이 들어오면 "aabb" 처럼 연속 2개씩인 경우만 제외해서 출력해야 되는 줄 알았다.

그래서 연속되는 같은 문자의 갯수를 구해서 홀수일 경우만 추가해서 출력하는 코드를 만들었다. 예를 들면 "aa"이면 삭제했고 "aaa"이면 연속된 2개인 "aa"를 지우고 "a"를 추가해주는 방식이었다. 제대로 구현했지만 틀린 코드였기에 왜 틀리는 거지라고 계속 생각하며 문제를 계속해서 반복해 읽었다. 그리고 왜 틀렸는지 알게 되었다.

이 문제는 연속으로 2개 중복되는 문자가 나오면 이를 지우고 추가하는 작업을 반복하라고 되어있었다. 즉, "aaabbabaabbb"를 입력시 "a" -> "" -> "a" -> "ab" -> "a" 다음 a가 들어오게 되면 이 또한 연속으로 중복되는 문자로 인식되서 ""로 되어야 되는 것이었다. 그래서 Stack을 사용하면 되겠구나라는 생각이 들었고 Stack을 이용해서 문제를 해결했다.

문제 난이도는 낮지만 문제에 대한 이해를 제대로 못했던 바람에 시간이 꽤나 걸렸던... 문제이다.

틀린코드

public String solution(String s) {
    StringBuffer sb = new StringBuffer();

    if(s.length()==1) return s;

    int cnt=1;
    for(int i=0, idx=1; i<s.length()-1; i++, idx++) {
        if(s.charAt(i)==s.charAt(idx)) {
            cnt++;
        } else {
            if(cnt%2==1) {
                sb.append(s.charAt(i));
            } 
            cnt=1;
        }
    }
    if(cnt%2==1) {
        sb.append(s.charAt(s.length()-1));
    } 
    return sb.toString();
}

정답코드

public String solution(String s) {
    if(s.length()==1) return s;

    Stack<Character> stack = new Stack<>();
    StringBuffer sb = new StringBuffer();

    for(char c : s.toCharArray()) {
        if(!stack.isEmpty() && stack.peek()==c) {
            stack.pop();
        } else {
            stack.push(c);
        }
    }

    while(!stack.isEmpty()) {
        sb.append(stack.pop());
    }
    return sb.reverse().toString();
}