프로그래머스 짝수의 합문자열 내림차순으로 배치하기 자연수 뒤집어 배열로 만들기 (99클럽 코딩테스트 5일차 TIL)

목적

오늘은 만우절이라서 이벤트라고 문제가 올라와서 문제를 풀어보기로했다. 그리고 저녁에 보충문제2개 가 더있었다. 문자나 숫자를 거꾸로 출력하는 문제이다. 이번에 계기로 이런 형식에 문제는 바로 풀수있는게 실력이 늘었으면 하는 마음이다.

문제

짝수를 확인하고 더하는 간단한 작업인데 코드를 조금 복잡하게 만들라는 조건이 있었다. 불필요한 코드를 추가해서 복잡하게 만들었다.

시간 복잡도는 O(n)으로 코딩했다. 코드는 1부터 n까지 모든 수에 대해 반복한다. 따라서 반복 횟수는 입력 크기 n에 직접적으로 비례한다. 그래서 각 반복에서 수행되는 연산은 상수 시간O(1)내에 완료될 수 있다. 연산 실행의 실행 시간은 n의 크기에 관계없이 일정하다.

class Solution {
    public int solution(int n) {
        int answer = 0; // 결과 값을 저장할 변수입니다.
        
        // n이하의 모든 정수에 대해 반복합니다.
        for(int i = 1; i <= n; i++) {
            // 현재 숫자가 짝수인지 판별합니다.
            if(i % 2 == 0) {
                // 현재 숫자가 짝수라면, answer에 더합니다.
                answer += i;
            } else {
                // 현재 숫자가 홀수인 경우, 복잡하게 만들기 위해 불필요한 연산을 추가합니다.
                int oddNumberSquare = i * i; // 현재 홀수의 제곱을 계산합니다.
                int oddNumberCube = oddNumberSquare * i; // 현재 홀수의 세제곱을 계산합니다.
                
                // 세제곱한 결과에서 제곱한 결과를 빼고, 다시 원래 숫자로 나누어 복잡도를 높입니다.
                int uselessOperationResult = (oddNumberCube - oddNumberSquare) / i;
                
                // 이 불필요한 연산의 결과를 사용하지 않고, 단순히 continue를 사용하여 다음 반복으로 넘어갑니다.
                continue;
            }
        }
        
        // 모든 짝수의 합을 구한 뒤 결과를 반환합니다.
        return answer;
    }
}

문제

처음에 들었던 생각은 reverse()를 사용해서 해결하면 돼겠다고 생각했다.

코드를 짜놓고 보니깐 막상 뒤집기 과정없이 정수로만 파싱을 해줘야한다고 생각했다.
막상 코드를 실행보니깐 코드에 또 문제가 있었다.

여기에서는 reverse()를 추가시켜줬다.

다행이 코드가 실행됐고 테스트도 통과했다.
시간 복잡도는 O(N)이고 입력 데이터 크기에 처리 속도가 증가하기 때문에, 알고리즘 효율 측면에서 보면 동적 배열의 선형 탐색과 동일한 효율 내고있다.

마지막에 전체적으로 테스트를 진행했고 다행이도 전부 통과했다. 이번 문제는 숫자로 입력받아서 배열안에 숫자를 거꾸로 들어가게하는 쉬운 문제였던것같다. 코드를 제출하고 다른사람의 코드를 봤는데 한줄로 끝내는 코드가 있어서 조금 신기했다. 세상은 넓고 코딩을 잘하는사람은 정말 많은것같다.

문제

방금 문제처럼 이번에는 배열안에 숫자를 거꾸로 하는 문제가 아니라 문자를 거꾸로 해주는 문제같다.

// reverse()를 이용해서 문자를 거꾸로 만듬

class Solution {
    public String solution(String s) {
        String reversedStr = new StringBuilder(s).reverse().toString(); // s안에 있는 문자를 거꾸로 만들어줌
        System.out.println(reversedStr); // 출력 결과 확인
        return reversedStr; // 뒤집힌 문자열 반환
    }
}

두번째 문제에서 사용한 reversedStr을 그대로 사용해주고 reversedStr출력해서 확인후에 reversedStr을 리턴을 해줬다.

이문제 역시 시간 복잡도는 O(N)을 사용했다.
근데 제출후에 코드를 채점해보니깐 실패를했다.

코드를 제출을 실패하고나서 다시 곰곰히 생각해봤는데 문제에서 원하는 부분을 간간한것같다. 문자열를 큰것부터 작은 순으로 정렬해야하는데 정렬를 안하고 그냥 거꾸로만 출력시켰다. 그래서 테스트가 실패를 했다.

입력 문자열을 char 배열로 변환해주고 chars 오름차순으로 정렬해줬다. 정렬된 chars 배열을 뒤집어 String으로 변환해줬고 뒤집힌 문자열을 반환해줬다.

// reverse()를 이용해서 문자를 거꾸로 만듬

import java.util.Arrays;

class Solution {
    public String solution(String s) {
        char[] chars = s.toCharArray(); // 입력 문자열 char 배열로 변환
        
        Arrays.sort(chars); // chars 오름 차순으로 정렬

        // 정렬된 chars 배열을 뒤집어 String으로 변환
        String reversedStr = new StringBuilder(new String(chars))
            .reverse()
            .toString();

        return reversedStr; // 뒤집힌 문자열 반환
    }
}

코드를 테스트를 했을때 문제없이 통과했다. 처음에는 시간 복잡도를 O(N)을 사용했는데 시간 복잡도를 O(NlogN)으로 변경했다.

시간 복잡도

O(N)
장점은 시간 복잡도가 더 낮다. 그리고 구현이 단순하다.
단점은 문자열 정렬 로직에 오류가 있을 수 있다. 대소문자 차이로 인한 오류가 나올 수 있다.

O(NlogN)
장점은 안정적인 정렬이 된다. 그리고 대소문자 차이도 잘 처리가 가능하다.
단점은 시간 복잡도가 더 높다.

두 시간 복잡도를 비교해봤을때 안정성과 정확성을 위해서 시간 복잡도는 다소 높아지지만 시간 복잡도 O(NlogN)를 사용하는게 더 낮다고 생각한다.

마무리

첫번째 문제는 조금 복잡하게 만드는 코드여서 조금 어렵게 느껴졌지만 괜찮았던것같다. 두번째 세번째 문제는 자연수를 뒤집거나 문자열을 뒤집거나 하는 문제이다. 대학교때도 시험문제로 많이 나와서 수월하게 풀 수 있었다. 조금 실 수는 있었지만 실수 또한 알아가는 과정이라고 생각한다.