java 알고리즘 문제입니다.

Question

java 알고리즘 문제입니다.

조회수 1261회

algorithm

java

0

싫어요

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

위 문제입니다. 맨 처음 노드갯수를 입력받고 노드 안의 데이터 값을 입력받아 입력받은 데이터값을 최종 출력하는 문제인 것 같습니다.

Class Node {
    int data;
    Node next;
    Node(int d) {
        data = d;
        next = null;
    }
}

class Solution { public static  Node insert(Node head,int data) {

        Node node = new Node(data);

        if (head == null)
            return node;

        Node start = head;
        while (start.next != null) {
            start = start.next;
        }

        start.next = node;

        return head;
    }
    public static void display(Node head) {
        Node start = head;
        while(start != null) {
            System.out.print(start.data + " ");
            start = start.next;
        }
    }

    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        Node head = null;
        int N = sc.nextInt();

        while(N-- > 0) {
            int ele = sc.nextInt();
            head = insert(head,ele);
        }
        display(head);
        sc.close();
    }
}

위가 최종 답이고 Solution 클래스 안이 채워야 하는 부분입니다. 이게 Node 클래스에 data가 들어가고 맨 처음 입력하는 노드를(start)를 head라고 선언한 뒤 head가 없으면 node 반환?? 제가 말하면서도 뭔 말인지 모르겠네요... python으로 풀 땐 두줄짜리라서 java로 풀면 너무 헷갈립니다. 어느 부분에서 입력받은 만큼의 노드를 생성한건지 모르겠습니다..ㅠㅠㅠ 아니면 next가 있어서 노드 입력이 필요 없는건지... 저 함수에서 왜 맨 처음 입력받은 값은 안나오고 그 다음 값인 data들만 출력되는지가.. 궁금합니다.

(•́ ✖ •̀)
알 수 없는 사용자

댓글 입력

score 1 · Accepted Answer

안녕하세요. 저는 java를 거의 모르지만 답변이 없어서 적어봅니다. 부디 작성자분을 더 혼란스럽게 만들지 않았으면 좋겠네요.

1 - Linked List (연결 리스트)란? 먼저 이런 데이터 구조물을 Singly Linked List라고 하는데 이는 한줄로 연결된 방식으로 데이터를 저장하는 자료 구조입니다. 그리고 자료 구조에서 자주 나오는 node란 각 데이터를 저장하는 공간인데 두 선을 연결하는 연결 지점이라고 생각하시면 편합니다.

2 - 그럼 왜 연결 리스트라고 하느냐? 그건 각 node가 다른 노드의 포인터, 즉 주소를 가지고 있다는 말이 됩니다.

(출처: 위키)

여기 이미지를 보시면 각 검은 상자가 node이고 왼쪽 보라색은 데이터, 저장하고 싶은 값을 나타내고 오른쪽 파란색은 다음 node의 포인터를 나타냅니다. 자바는 아마 포인터가 없고 전부 reference (참조자)지만 기본 구조는 이미 만드신 것과 같이 비슷합니다.

추가로 여기서 head 머리란 가장 앞에 있는 node입니다. 왜 이게 필요하냐 물어보시면 사진을 다시 봐주세요. 처음 node를 현재 노드(node)라고 하겠습니다. 그리고 두번째 노드를 다음 노드 (node.next), 그리고 세번째 노드를 다음 다음 노드 (node.next.next)라고 하겠습니다.

두번째 있는 노드 (다음 노드 node.next) 를 찾기 위해서는 그 전 노드 (현재 노드 node)를 찾아야합니다. 세번째 노드를 찾으려면? 현재 노드 (node)를 찾고, 그 다음 노드를 찾아야 (node.next) 그 안에 있는 (node.next.next)가 나옵니다. head는 여기서 연결리스트를 게임이라고 치면 모든 다른 노드 (고위 게임 레벨)를 찾기위한 가장 처음 게임 단계, 1레벨 지역이라고 이해하시면 됩니다.

3 - 그럼 노드는 어떻게 생성되나요?

어느 부분에서 입력받은 만큼의 노드를 생성한건지 모르겠습니다

연결 리스트가 배열 (Array)와 다른 점은 배열은 기본적으로 절대적인 크기가 필요하고 그 크기를 바꿀 수 없습니다. 자바에서도 마찬가지라고 알고있습니다. 하지만 연결 리스트는 이미 각 노드가 다음 노드를 가지고 있기 때문에 null인 아무것도 없는 다음 노드의 값만 다시 설정해주면 끊임없이 새로운 노드를 만들 수 있습니다. 즉, 쉽게 말하면 무한(하게 커질 수 있는) 배열이죠.

// intege 배열에 숫자 정의하기
arry_data[0] = 5;
// linked list에 값을 추가하기
linkedlist.insert(5);

// 새로운 노드를 형성
Node node = new Node(data);
...
// 이런 식으로 head 혹은 head 다음 노드에 연결시킵니다
// 올바른 저장 지점에 대해서는 4번에서 설명하겠습니다.
head = node; 
head.next = node;

4 - 실질적 코드 설명 빠 빠라밤 빠밤...

새로운 노드를 생성합니다. 꼭 필요한건 아니지만 최소 2번은 쓰기 때문에 그냥 만들어두는 편이 편합니다.

Node new_node = new Node(data);

만약 head (머리)가 비어있다면, 리스트가 비어있다는 뜻입니다. 그럼 다음 노드를 찾을 필요없이 그 머리 노드에 데이터를 추가시키면 (새로 만든 노드를 연결시키면) 됩니다.

if (head == null)
{
    head = new_node;
}

만약 이 연결 리스트에 node가 1개 이상이라 마지막 노드를 찾아야한다면, 임시 head를 만들어줍시다. 이건 다음 데이터를 마지막에 연결한다는 전제하에 이런겁니다. 이걸 만드는 이유는, 마지막 노드를 찾는 루프 방법에 있습니다. 잠시후에 설명하겠습니다.

else
{
    Node temp_head = head;

while문을 이용해서 언제까지 찾아야하죠? 현재 노드의 그 다음 노드 (next)가 비어있을 때까지 입니다. 이 아래를 보시면 그 다음 노드들을 찾기 위해 head 노드를 그냥 그 다음 노드로 만들어버립니다. 그럼 head를 찾을 수 없기 때문에 임시 head 노드를 만들어버리게 된 거죠. 계속 현재 노드 (임시 head 노드)를 바꾸다보면 (당연하게도) 그 값이 null, 즉 아직 생성하지 않은 노드가 나옵니다.

    while(temp_head.next != null)
    {
         temp_head = temp_head.next;  
    }

다음에는 그냥 if (head == null)에서 처럼 연결만 해주시면 됩니다.

    temp_head.next = new_node;
}

output은 제가 return 문장을 가능한 1개만 쓰는걸 좋아해서 마지막에 두었습니다. 그리고

return node; // 가 아니라
return head; // 이게 맞습니다.

node라고 쓰셔서 설명하는데 문제에서도 가능한 head를 리턴하라고 하라고 합니다.

your insert function should return a reference to the head node of the linked list

여기서 node를 반환해도 처음 값이 나오는 이유는 지금 리스트와 head가 비어있어서 그렇습니다. head도 노드이고 메인에서 리턴 값을 head에 넣어주니까요. 결과가 1개의 값만 가지면 되니, 그냥 현재 받은 데이터로 노드를 만들어서 리턴해도 상관은 없겠죠. 하지만 그렇게되면 여러 return 장소가 나타나고 결국 실제로 insert 함수 안에서 리스트를 만드는게 아니라 추천하지는 않습니다. 당연히 else... 부분에서 새로 만든 node를 사용하면 안되고요.

5 - 추가 질문 설명

저 함수에서 왜 맨 처음 입력받은 값은 안나오고 그 다음 값인 data들만 출력되는지...

이건 위에 분도 자세히 대답을 해주셨는데 문제에서도 나옵니다.

The first line contains T, the number of test cases.

처음 입력한 값은 테스트하는 값들의 수입니다. 즉 4, 2, 3, 4, 1이면 4는 2, 3, 4, 1로 몇번 테스트해야 하는지만 알려줍니다.