쏘니의 개발블로그

자료들을 반드시 연속적으로 배열시키지 않고 링크(link)를 통해 리스트를 형성

노드(node)는 데이터를 담는 그릇, 링크(link)는 리스트의 순서를 유지할 수 있게 해주는 연결고리의 구조를 가지고있다

스택, 큐, 해시 등의 기본이 됨

장점

• 삽입, 삭제 작업이 용이하다
• 기억공간이 연속적이지 않아도 저장이 가능하다.
• 메모리를 효율적으로 사용
• 데이터 재구성 용이
• 대용량 데이터를 처리하는데 적합

단점

• 접근속도가 느리다.(포인터를 찾아가는 시간이 필요하기 때문에 배열에 비해 접근속도가 느림)
• 중간 노드의 연결이 끊어지면 그 다음 노드를 찾기 힘들다.
• 구성 및 사용방법이 까다로움

배열 vs 링크드리스트 데이터의 삽입/삭제가 거의 없고, 데이터 접근이 빈번하게 이뤄질 경우는 배열이 유리함. 반면 데이터의 삽입/삭제가 빈번하게 이뤄질 경우에는 연결리스트가 유리.

ListNode

ListNode 는 다음 노드를 가리키는 포인터만 존재하므로 data 와 next 를 가진다.

public class ListNode {
	private int data;
    private ListNode next;
    
    ListNode(int data) {
    	this.data = data;
    }
    
    public int getData() {
		return this.data;
	}

	public ListNode getNext() {
		return this.next;
	}

	public void setNext(ListNode nextNode) {
		this.next = nextNode;
	}
}

LinkedList

public class LinkedList {
	private ListNode head; // 현재리스트 노드
	private int size;

	LinkedList() {
		this.head = null;
		this.size = 0;
	}
    
    public ListNode add(ListNode nodeToAdd, int position) {
    	this.size++;
        
        // position 유효성 체크
        if(validatePositionRange(position)) {
        	return null;
        }
        
        // 해당 위치 찾기
        ListNode pre = null, cur = this.head;
        while(--position > 0) {
        	pre = cur;
            cur = cur.getNext();
        }	
        
        // 삽입 위치가 맨 앞인 경우
        if(pre == null) {
        	nodeToAdd.setNext(cur);
            this.head = nodeToAdd;
            return this.head;
        }
        
        // 그 이외에 경우
        pre.setNext(nodeToAdd);
        nodeToAdd.setNext(cur);
        return nodeToAdd;
    }
    
    public ListNode remove(int positionToRemove) {
        // positionToRemove 유효성 체크
        if(validatePositionRange(positionToRemove)) {
            return null;
        }

        // 해당 위치 찾기
        ListNode pre = null, cur = this.head;
        while(--positionToRemove > 0) {
            pre = cur;
            cur = cur.getNext();
        }

        // 연결 리스트의 크기 감소
        this.size--;

        // 삭제 위치가 맨 앞일 경우
        if(pre == null) {
            this.head = cur.getNext();
            return cur;
        }

        // 그 이외의 경우
        pre.setNext(cur.getNext());
        return cur;
	}
	
    public boolean contains(ListNode nodeToCheck) {
        // 순회
        ListNode cur = this.head;
        while(cur != null) {
            // 같은 ListNode라면
            if(cur == nodeToCheck) {
                return true;
            }
            cur = cur.getNext();
        }
        // 끝까지 체크하고도 같은 ListNode가 없다면
        return false;
    }
    
}

정수형 및 값의 범위가 있는 타입의 중간값을 구할때 실수하는 것이 있다.

int mid = (a  + b) /2 

이 경우 a 와 b 가 작은값이면 상관없지만 int 범위 2,147,483,647 가까이 되는 숫자 21억 등의 숫자를 계산할때는 위와 같은 숫자 계산은 오버플로우가 난다.

그러므로 다음과 같이 수정해야 하다.

int start = 2_000_000_000;
int end = 1_000_000_000;

int mid = start + (end - start) / 2;

public int[] solution(int[] prices) {
	int len = prices.length; // 5
	int[] answer = new int[len];
	int i, j;
	for (i = 0; i < len; i++) {
		for (j = i + 1; j < len; j++) {
			answer[i]++;
			if (prices[i] > prices[j])
				break;
		}
	}
	return answer;
}

문제 설명

초 단위로 기록된 주식가격이 담긴 배열 prices가 매개변수로 주어질 때, 가격이 떨어지지 않은 기간은 몇 초인지를 return 하도록 solution 함수를 완성하세요.

제한사항

• prices의 각 가격은 1 이상 10,000 이하인 자연수입니다.
• prices의 길이는 2 이상 100,000 이하입니다.

입출력 예

pricesreturn

입출력 예 설명

• 1초 시점의 ₩1은 끝까지 가격이 떨어지지 않았습니다.
• 2초 시점의 ₩2은 끝까지 가격이 떨어지지 않았습니다.
• 3초 시점의 ₩3은 1초뒤에 가격이 떨어집니다. 따라서 1초간 가격이 떨어지지 않은 것으로 봅니다.
• 4초 시점의 ₩2은 1초간 가격이 떨어지지 않았습니다.
• 5초 시점의 ₩3은 0초간 가격이 떨어지지 않았습니다.

문제 추가 설명. 

첫 번째 배열값 1이 다음 배열값을 순환하면서 값이 커질떄까지의 값을 구한다.

첫번째 1은 4번 반복동안 더 작은값이 없음.

세번째 배열 3은 바로 다음 배열값 2가 작으므로 1초라는 값 가짐.

네번째는 배열값 2는 다음 배열까지 작아지는 값 없으므로 1초

다섯번째 배열값은 마지막이므로 0초

문제 설명

수많은 마라톤 선수들이 마라톤에 참여하였습니다. 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다.

마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수들의 이름이 담긴 배열 completion이 주어질 때, 완주하지 못한 선수의 이름을 return 하도록 solution 함수를 작성해주세요.

제한사항

• 마라톤 경기에 참여한 선수의 수는 1명 이상 100,000명 이하입니다.
• completion의 길이는 participant의 길이보다 1 작습니다.
• 참가자의 이름은 1개 이상 20개 이하의 알파벳 소문자로 이루어져 있습니다.
• 참가자 중에는 동명이인이 있을 수 있습니다.

입출력 예

participant                                                   completion                                                  return

입출력 예 설명

예제 #1
leo는 참여자 명단에는 있지만, 완주자 명단에는 없기 때문에 완주하지 못했습니다.

예제 #2
vinko는 참여자 명단에는 있지만, 완주자 명단에는 없기 때문에 완주하지 못했습니다.

예제 #3
mislav는 참여자 명단에는 두 명이 있지만, 완주자 명단에는 한 명밖에 없기 때문에 한명은 완주하지 못했습니다.

정답

import java.util.HashMap;

class Solution {
    public String solution(String[] participant, String[] completion) {
        String answer = "";
        HashMap<String, Integer> map = new HashMap<>();
        for (String player:participant) {
          map.put(player,map.getOrDefault(player,0)+1);
        }
        for (String player:completion){
          map.put(player,map.get(player)-1);
        }

        for(String key : map.keySet()){
          if(map.get(key) !=0){
            answer = key;
          }
        }
        return answer;
    }
}

map 은 중복을 허용하지 않는 자료구조 이므로 for 문으로 map 에 1차적으로 넣고, 다음 for 문으로 기존에 있었는지에 대해 검사를 해야한다.