다메카솔

https://programmers.co.kr/learn/courses/30/lessons/67256

문제

숫자 배열이 주어집니다. 정해진 규칙에 따라 왼손 혹은 오른속으로 숫자패드를 누르게 되는데, 어떤 손으로 눌렀는지를 출력하세요.

발상

우선 왼쪽라인은 왼손, 오른쪽 라인은 오른손으로 정해져있으니, 먼저 고정값들을 반환하고

그 뒤에 현재 왼손,오른손 검지의 위치와 목표숫자의 거리를 계산하는 것이 포인트였다.

1. 숫자패드가 정해져있으니 숫자패드를 [1,2,~10,11,12] 숫자배열로 추상화하고

2. 엄지와 목표값의 거리를 3x4 배열의 특성을 이용하여 3으로 나눈 몫을 y거리, 3으로 나눈 몫의 나머지를 x거리로 잡아서

3. x와 y의 값을 더하여 각 손의 거리를 구하고 비교하기로 하였다.

의사코드

1. 초기값 세팅(숫자패드, 왼손, 오른손 위치)

2. 입력값 테스트(){

    1. 목표가 0일 경우 추상화한 11로 치환

    2. 손가락판별()

    3. 결과배열 더하기
}
3. 결과배열 반환



손가락판별(){

1.3으로 나누었을때 나머지가 1이면 L

2. 3으로 나누었을때 나머지가 0이고 목표가 0이 아니면 R

3. 왼손과 오른손의 목표와의 거리값 비교

4. 결과값 반환

}



거리값 비교(){

1. 목표와 현재위치 절대값 계산

2. 차이값을 3으로 나눈 몫 = y거리

3. 차이값을 3으로 나눈 몫의 나머지 = x거리

4. y+x 반환

}

개선

테스트케이스 통과 후, 다른사람들이 작성한 코드를 보니 발상은 비슷한데 세부적으로 최적화한 부분이 있었다.

예를들어 주어지는 값 "left","right"를 "L","R"로 새로 할당하여 비교한다던지

나는 각각의 거리를 매 로직마다 계산하게 하였는데, 패드가 작은 것을 이용하여 미리 구해놓은 값을 바로 쓰는 경우도 있었다.

다음부터는 사용하기 편리한 값들을 설정하는 것도 고려하자.

https://leetcode.com/problems/sliding-puzzle/

문제

2 x 3 보드에는 1에서 5까지 레이블이 지정된 5개의 타일과 0으로 표시되는 빈 사각형이 있습니다. 이동은 0과 4방향으로 인접한 숫자를 선택하고 교체하는 것으로 구성됩니다. 보드의 상태는 보드가 [[1,2,3],[4,5,0]]인 경우에만 해결됩니다. 퍼즐 보드 보드가 주어지면 보드의 상태가 해결되도록 필요한 최소 이동 횟수를 반환합니다. 보드의 상태를 해결할 수 없는 경우 -1을 반환합니다.

접근

어렸을때 가지고 놀던 슬라이딩퍼즐을 맞추는 가장 적은 횟수를 구하는 문제이다.

퍼즐의 풀이방법을 구현하여서 푸는 방법도 있을 것 같고https://namu.wiki/w/%EC%8A%AC%EB%9D%BC%EC%9D%B4%EB%94%A9%20%ED%8D%BC%EC%A6%90

빈 공간을 기준으로 이동알고리즘을 작성하는 방법도 있을 것 같았는데, 절차가 잘 떠오르지 않았다.

퍼즐의 배열 상태를 하나의 노드로 보고,

빈공간(0)의 이동 가능 경로의 이동 후 배열상태를 자식노드로 연결하여

전체 경우의 수를 탐색하는 방법을 쓰는 것을 방향으로 잡고 접근하였다.

구현에 사용한 변수는 다음과 같다.

목표 퍼즐상태 String = "123450"

현재 상태 String

방문노드 캐시용 HashSet<String>

탐색노드 저장용 Queue

퍼즐의 위치 별 탐색 가능 방향 배열 int[][]

의사코드

1. 초기값 세팅

2. 탐색용 배열과 캐시에 현재상태 세팅

3. 노드 탐색(큐가 빌 때까지){

    1. 탈출조건 체크 ( 탐색깊이 반환 )

    2. 현재 0의 위치 확인

    3. 가능한 이동방향 퍼즐상태 저장(0 <-> 목표 스왑)

        1. 캐시확인, 방문노드면 큐에 저장X

        2. 미방문 노드면 큐에 저장

    4. 탐색깊이 ++

}

4. 탐색 실패 시 -1 반환

https://www.hackerrank.com/challenges/30-binary-search-trees/problem

이진트리에서, 가장 깊은 depth를 구하는 문제이다.

    int heightLeft = 0;
    int heightRight = 0;

    if (root.left != null) {
        heightLeft = getHeight(root.left) + 1;
    }
    if (root.right != null) {
        heightRight = getHeight(root.right) + 1;
    }

  return (heightLeft > heightRight ? heightLeft : heightRight);
}

https://www.hackerrank.com/challenges/30-generics/problem

인티즈배열과, 스트링배열 양쪽 모두 받아서 출력할수있는 제네릭함수를 작성하는 문제이다.

전에 공부할때 간단히 보고 넘어갔었는데

보통 ArrayList에 있는 <>에 넣는 용도로만 쓰다가 직접 메서드를 작성하려고 보니

제네릭클래스를 만들어야 되서 다시 한번 책을 찾아봤다.

메서드를 작성할때, 메서드 안에 배열을 제네릭 타입으로 지정해놓아야 하는데

그러려면 클래스를 제네릭 클래스로 만들어야 했다.

https://www.hackerrank.com/challenges/30-sorting/problem

BubbleSort를 구현하고, 주어진 배열을 정렬하는데 걸리는 횟수를 카운트해서 출력하는 문제이다.

https://www.hackerrank.com/challenges/30-interfaces/problem

인터페이스를 구현하고, 약수들의 합을 구하는 문제이다.

상속과 추상클래스 문제가 나올때 같이 나왔던것 같은데, 다시 확인해보니 그때 안나왔었다.

중간에 있던 코드중 getClass().getInterfaces();라는 내용이 있었는데

getClass는 컬렉션에 넣었을때 확인할때 쓸 수 있을 것 같은데

getInterfaces는 어디다 쓰는걸까??

약수는, for 문을 1부터 시작해서, 나머지가 0이 아닌것들을 제외하여서 구하였다.

약수를 구하는 알고리즘을 검색하면, 몇가지 더 효율적인 방법이 나오는데

생각보다 알고리즘 대회등에서 많이 나오는 문제인듯 하다.

기본적이면서, 생각의 깊이에 따라 더 효율적이고 성능을 향상 시킬 수 있어서 그런가?

최대공약수를 구하는 알고리즘중에 유클리드 호제법이라는게 있는데 원리가 잘 이해가 안되서

공부좀 더 해야겠다.

https://ko.wikipedia.org/wiki/%EC%9C%A0%ED%81%B4%EB%A6%AC%EB%93%9C_%ED%98%B8%EC%A0%9C%EB%B2%95

https://www.hackerrank.com/challenges/30-queues-stacks/problem

스택과 큐를 이용해서 앞뒤가 똑같은 문자열을 확인하는 문제이다.

하루에 한문제씩 풀 예정이였는데, 한번 더 복습하려고 생각했던 자료구조 문제가 나와서

복습진도를 맞추느라 좀 늦어지게 되었다.

문제 자체는 자바에 구현되있는 스택과, 큐를 구현한 컬렉션을 사용해서 간단하게 풀 수 있지만

실제로 스택과 큐가 어떤 코드로 동작하는지 추가적인 공부를 하였다.

지금의 이해도와, 나중에 더 학습하고 나서의 이해도를 비교하기 위해 내용정리를 해봐야 겠다.

Stack은 jvm에 있는 콜스택등을 구현할때 쓰는, 선입후출방식의, 카드더미같은 자료구조이다.

사용할 만한 곳은 콜스택도 있고 할일 뭉터기 카드나, 인터넷 브라우져에서 뒤로, 앞으로등도 스택으로 구현할 수 있다.

그리고 재귀함수등도 스택으로 처리할테고, 어떤 길을 지나간뒤, 다시 돌아오는 등의 형태에서도 사용할 수 있을듯 하다.

큐는 파이프, 혹은 대기줄같은 선입선출방식의 자료구조이다.

순서대로 처리해야 하는 일들, 음식주문이나 고객센터 문의사항 처리, 대기표 발급이나 게임이나 프로그램의 예약명령어등이 있겠다.

내가 공부했던 자바책에선, 스택과 큐 둘다 linkedlist로 구현했다고 한다.

linkedlist는 순서가 없고, 각 노드가 이전이나 다음노드를 가지고 있는 연결된 줄같은 자료구조인데

뒤로만 연결되있는 형태가 기본형 LinkedList이고

앞의 노드도 가지고 있어서 앞뒤로 이동할 수 있는 형태가 doubleLinkedList이며

제일 처음과 끝을 연결한 형태는 CircularLinkedList라고 한다.

자바는 그중 doubleLinkedList로 LinkedList를 구현하였고, 처음과 끝을 모두 바로 접근할 수 있어서 Stack과 Queue 양쪽에 적합하다고 한다.

https://www.hackerrank.com/challenges/30-more-exceptions/problem

Day 16과 같은 예외처리 문제이다.

다만 차이점은, 강제로 예외를 발생시켜서, 함수를 호출한 쪽에서 처리하도록 보내는 문제이다.

배웠던 기억이 있는데, 안쓰다보니 떠오르지 않아서, 다시 찾아보고나서 풀었다.

https://www.hackerrank.com/challenges/30-exceptions-string-to-integer/problem

스트링값을 입력받아서, int로 변환시키고 출력할때 예외처리를 하는 문제이다.

try-catch문만 입력하면 된다.

https://www.hackerrank.com/challenges/30-linked-list/forum

연결리스트 자료구조를 구현하는 문제이다.

기본 Node클래스는 주어져있고, 삽입시 사용할 메서드만 완성하면 된다.

 if(head == null)
        return new Node( data);
    else if(head.next == null){
            head.next = new Node(data);
        }
    else{
        insert(head.next,data);
    }


        return head;