[TIL#20] Study] 코딩 테스트 9

금일의 풀이 전반에 걸쳐서 오타에 관한 이슈가 많이 발생했다. 그로 인해 불필요한 과정이 많았다. 오류가 발생하면 오타를 먼저 확인해야겠다.

 

1. 햄버거 만들기

오전 3시간을 잡아먹은 문제이다. 검증 로직을 구현하는 과정에서 시행착오가 많이 발생했다. 코드는 다음과 같다.

 

public int solution(int[] ingredient) {
    int answer = 0;
    Stack<Integer> ingredi = new Stack<>();             // 재료를 받아올 Stack
    Stack<Integer> supervise = new Stack<>();           // 재료 순서를 검증할 Stack
    int[] hamburger = {1, 3, 2, 1};                     // 햄버거를 완성하기 위한 재료의 순서

    for (int make : ingredient) {                       // 재료를 받아옴
        ingredi.push(make);
        if (ingredi.size() >= 4 && ingredi.peek() == hamburger[0]) {    // 검증하기 위한 조건
            boolean success = true;                     // 재료 검증 결과 태그

            for (int j : hamburger) {                   // 재료 검증 실패 조건
                if (j != ingredi.peek()) {
                    success = false;
                    break;
                }
                supervise.push(ingredi.pop());          // 각 재료의 검증 완료 시
            }
            if (success) {                              // 모든 재료의 검증 완료 시
                answer++;
                supervise.clear();
            } else {
                while (!supervise.isEmpty()) {          // 재료 검증 실패시 공정과정
                    ingredi.push(supervise.pop());
                }
            }
        }
    }
    return answer;
}

 

1. 검증 과정 구현
   • 재료 순서를 검증하기 위한 로직을 구현할 때 가장 많이 고민한 부분은 '어떻게 Stack 내부의 값을 확인해서 이용할 수 있을까?' 였다. Stack 이 가지고 있는 함수들을 구글링하여 사용해보려 했지만 구현할 방법이 떠오르지 않았고 만약 떠올랐더라도 코드가 지저분해질 것 같았다.
   • 그러다 문득 '그냥 값을 넣기 전에 검증하면 되잖아?' 라는 생각이 들었고 그렇게 구현하였다.
     1,2,3,1 이 완성의 조건이라면 스택의 특성상 1,3,2,1 순서로 스택에 들어가야 하기에 그렇게 검증식을 정했다.
2. 검증 결과 구분
   • 완성 후 로직을 작동시키니 엉뚱하게 작동했다. 하여 조건식이 잘못되었는가 확인을 계속하다가 선생님 포지션의 팀원분께 도움을 요청했다.
   • 원인은 조건식으로 구한 검증 결과에 상관없이 answer++ 가 실행되고 있었다. 하여 검증의 결과를 구분하는 boolean 을 생성하고 검증 결과의 태그로 사용하니 문제가 해결되었다.
   • 다른 부분들은 큰 문제없이 30분(???)만에 완성하였다.

문제들 대부분이 반복문의 영역 안에서 벌어지고 있다. 반복문에 대한 이해도 부족 혹은 서른안이 문제의 원인이라고 생각한다. 전자는 반복문을 첨삭할 때 느리더라도 꼼꼼하게 읽어나가는 연습을 해야겠다. 후자는 현재로서는 루테인 밖에 해답이 없다.

 

2. 문자열을 정수로 바꾸기

 

    public int solution(String s) {
        return Integer.parseInt(String.valueOf(s));
    }

 

 딱히 어려울 것 없는 문제였지만, 다른 사람의 풀이를 확인하던 도중에 '알고리즘 문제인데 못 풀어서 함수를 사용했다 ㅠㅠㅠ' 이런 뉘앙스의 댓글을 봤다.

 그것을 보고 뭐가 잘못된 것인지 모르겠다. 결국 문제를 빠르고 간결하게 해결하기 위한 연습이 알고리즘 문제의 목적이고 그에 부합한 코드를 작성하고도 반성하고 있었다. 필자가 모르는 무언가 더 있는 것인가 싶다.

 하지만 지금의 필자가 생각하는 알고리즘의 문제의 목적은 '빠르고 간결하게 해결하기 위한 좋은 코드를 짜는 것'이라고 생각한다.

 

3. 정수 제곱근 판별

 

 발견하기 까다로운 반례를 가지고 있었던 문제이다. 또한 지금까지 필자가 long 과 float 을 동일시하고 있던 잘못을 바로잡은 문제이다.

 필자는 long 타입이 소수점을 가지는 타입이라고 알고 있었다. 아찔하다. 하여 오류를 품은 초기의 식을 구현했다.

//		오류를 품은 식
        long root = (long) Math.sqrt(n)+1;
        return n/root == root? (long) Math.pow(root + 1, 2) : -1;

• 정수의 제곱근은 n과 root를 나눈 값이 root가 나오면 된다. ex) 4 / 2 = 2
  알다시피 대부분의 숫자에 루트를 씌우면 소수점을 가진 값들이 나온다. 이 코드에서 root는 소수점을 가지지 않은 정수의 값이다. 그렇기에 정수의 제곱근 여부를 정확하게 파악할 수 없다.
• 반례는 101이다. √ 101의 값은 10.049~~ 이다. 필자는 long이 소수점을 가지는 타입이라 착각했지만 소수점을 버리는 타입이었고 그 결과 long으로 변환하면 10이 된다. 10은 100의 제곱근이다. 이러한 오류를 수정한 코드는 다음과 같다.

    public long solution(long n) {

        long root = (long) Math.sqrt(n);
        return Math.sqrt(n)%1 == 0 ? (long) Math.pow(root + 1, 2) : -1;
        
//     위의 삼항연산자는 아래와 같은 의미이다.
//        if (Math.sqrt(n) % 1 == 0) {
//            return = (long) Math.pow(root+1, 2);
//        } else {
//            return -1;
//        }
    }