[01] 리스트, 해시테이블, 정렬, two pointer

[1] 리스트 (Array) 

◈ 동적 배열 Dynamic Array

- 동적 배열은 배열의 크기 변경 가능한 배열

- 선언시에 배열의 크기를 정하지 않아도 됨

- List 인터페이스와 ArrayList 클래스 사용

-  List<타입명> 리스트명 = new ArrayList<>();

// List<Type> listName = new ArrayList<>();
List<Integer> list = new ArrayList<>();

- list 라는 이름의 Integer 타입을 저장하는 ArrayList 선언

// 크기가 3인 List를 선언 후 각 원소를 1, 2, 3으로 초기화
// List<T> listName = new ArrayList<>(List.of(value1, value2, ...);
List<Integer> list = new ArrayList<>(List.of(1, 2, 3));

- list 라는 이름의 Integer 타입을 저장하는 ArrayList를 선언함과 동시에 초기화

- List<T> listName = new ArrayList<>(List.of(value1, value2, ...);

 

◈ ArrayList의 원소 접근

- 리스트명.get(idx); 

// i번째 원소 접근하기
list.get(i);

 

◈ ArrayList의 원소 수정

- 리스트명.set(idx, el);

// i번째 원소 3으로 수정하기
list.set(i, 3);

 

◈ ArrayList의 원소 추가

- 마지막에 원소 추가: 리스트명.add(el);

// 리스트 마지막에 원소 1 추가
list.add(1);

 

- 중간에 원소 추가: 리스트명.add(idx, el);

// list[2] 에 원소 10 삽입
list.add(2, 10);

- 원소 삽입 후 뒤의 원소 하나씩 미뤄야 해서 O(n) 시간 복잡도 가짐

 

◈ ArrayList의 원소 삭제

- 마지막 원소 삭제: 리스트명.remove(integerList.size() - 1);

list.remove(integerList.size()-1);

- O(1) 의 시간 복잡도

 

- 중간 원소 삭제: 

• i번째 인덱스 값 삭제하고 리턴: 리스트명.remove(idx);

• // list[2] 삭제 후 반환
  list.remove(2);

•  
• 가장 앞에 있는 원소 el 삭제:
  • 리스트명.remove(el);

  • // list에서 가장 앞에 있는 "item" 삭제
    list.remove("item");

  • ArrayList<Integer>의 경우 리스트명.remove(Integer.valueOf(el)); 

  • // list에서 가장 앞에 있는 2 삭제
    list.remove(Integer.valueOf(2));

◈ ArrayList의 정렬

• 리스트 오름차순 정렬

• list.sort(Integer::compareTo);

•  
• 리스트 내림차순 정렬

• list.sort(Comparator.reverseOrder());

◈ [참고] 정렬

- 정적 배열 정렬: Arrays.sort() 

- List, Vector 등  : Collections.sort()

- Stream : stream.sorted();

 

◈ ArrayList 복제

• ArrayList 생성자에 원본 넣어 복제
•  
• List<Integer> destList = new ArrayList<>(sourceList);

 

◈ 2차원 ArrayList

List<List<Integer>> doubleList = new ArrayList<>();

for (int i = 0; i < 10; i++) {
    List<Integer> newRow = new ArrayList<>(); // 새 열을 추가
    for (int j = 1; j <= 10; j++) {
        newRow.add(i * 10 + j);
    }
    doubleList.add(newRow);
}

System.out.println(doubleList);

- 크기가 초기화되어있지 않아 for문으로 새 행 추가하면서 사용해야

 

◈ 2차원 배열의 복제

List<List<Integer>> doubleList = new ArrayList<>();
// .. doubleList 초기화

List<List<Integer>> copyList = new ArrayList<>();
for (List<Integer> row : doubleList) {
    copyList.add(new ArrayList<>(row));
}

copyList.get(0).set(0, 9999); // 복제본 수정

System.out.println(doubleList);

- 각 행 따로 복제해야

---

[2] 해시테이블 (Hash Table)

◈ 해시 테이블

- key - value 쌍 데이터 입력 받아 효율적인 탐색 가능하게 함

- 저장, 삭제, 검색 시간복잡도 모두 O(1)

- 공간효율성이 떨어짐

=> 빠른 시간, 메모리 제한 없는 경우에 사용 추천

 

◈ HashMap

- 해시테이블은 Map 인터페이스와 HashMap 구현 클래스로 구현

 

◈ HashMap 선언

• hashtable 이라는 이름의 key(Integer), value(String) 쌍을 저장하는 HashMap 선언

• // Map<K, V> map = new HashMap<>();
  Map<Integer, String> hashtable = new HashMap<>();

• 선언과 동시에 초기화

• Map<Integer, String> hashtable = new HashMap<>() {{
      put(10, "짱구");
      put(22, "짱아");
  }};

◈ key-value 쌍 추가하기

hashtable.put(13, "흰둥이");

 

◈ key에 해당하는 value 접근하기

hashtable.get(10); // "짱구"

 

◈ key에 해당하는 value 수정하기

hashtable.replace(10, "노진구");

 

◈ key-value 쌍 제거 (삭제)

hashtable.remove(13); // "흰둥이" 삭제

 

◈ 해당 key 존재하는지 확인

- containsKey() 는 시간복잡도 O(1)

// key 13이 존재하면 값을 출력하는 예제
if(hashtable.containsKey(13)) {
    System.out.println(hashtable.get(13));
} else {
    System.out.println("해당 키는 존재하지 않습니다.");
}

 

◈ 커스텀 클래스 생성

- value 에 여러 조합의 값을 저장해야 하는 경우 => 클래스로 해결

- ex) 가중치 그래프 간선 저장

class Edge {
    public int dest;
    public int weight;
    
    public Edge(int dest, int weight) {
        this.dest = dest;
        this.weight = weight;
    }
}

- 도착 노드와 가중치 조합을 위처럼 클래스로 저장

Map<Integer, Edge> graph = new HashMap<>() {{
    put(1, newEdge(3, 5)); // 1 -> 3 가중치 5 간선추가
    put(2, newEdge(1, 1)); // 2 -> 1 가중치 1 간선 추가

- 해시맵에서 사용

 

◈ Key로 사용하는 커스텀 클래스

- 클래스를 해시맵의 key로 사용하기 위해선 equals() 와 hashCode() 메소드 오버라이드해야 함

• equals() : 파라미터로 받은 오브젝트가 자신과 같은지 리턴
• hashCode() : 이 오브젝트의 해시코드 리턴

- ex) 특정 좌표 (x, y) 를 key로 사용하는 경우

class Point {
    public int x;
    public int y;
    
    public Point(int x, int y) {
        this.x = x;
        this.y = y;
    }
    
    @Override
    public boolean equals(Object obj) {
        if(obj instanceOf Point) {
            Point other = (Point)obj;
            return other.x == this.x && other.y == this.y;
        }
    }
    
    @Override
    public int hashCode() {
        return Objects.hash(this.x, this.y);
    }
}

 

Map<Point, Integer> s = new HashMap<>();

s.put(new Point(1, 2), 5);
s.put(new Point(3, 4), 3);
s.put(new Point(1, 2), 10); // 기존 값이 교체됨

s.containsKey(new Point(1, 2)); // true

s.size(); // 2

 

◈ Map 의 단점

- 정렬 불가 => Key, Value 만은 정렬 가능

- ex) key 값 정렬하여 접근하기

Map<String, Integer> map = new HashMap<>();

// Map 의 key만 저장
List<String> keyList = new ArrayList<>(map.keySet());

// key 정렬
Collections.sort(keyList);

// 정렬된 key 로 Map 접근
for (String key : keyList ) {
    Integer value = map.get(key);
}

---

[3] 해시셋 (Hash Set)

◈ 해시셋 (Hash Set)

- 해시 테이블과 유사하지만 key-value가 아닌 key 만 저장

 

◈ 해시셋의 선언

// Set<T> setName = new HashSet<>();
Set <String> hashset = new HashSet<>();

- hashset이라는 이름의 String 타입 key를 저장하는 HashSet 선언

Set<String> hashset = new HashSet<>() {{
    add("짱구");
    add("짱아");
}};

- HashSet 선언 후 값 초기화

 

◈ key 추가하기

hashset.add("흰둥이");

 

◈ key 제거하기

hashset.remove("짱아");

 

◈ 해당 key 존재하는지 확인

hashset.contains("짱아"); // false

 

◈ 커스텀 클래스 생성

- key를 클래스로 사용하는 경우 해시맵과 마찬가지로 equals(), hashCode() 메소드 오버라이드 해야함

---

[4] Queue

◈ 큐 (Queue)

 

- 먼저 저장한 데이터를 먼저 출력하는 선입 선출(FIFO) 자료구조

- enqueue : queue의 rear(뒤)에 데이터 추가

- dequeue: queue의 front(앞)에 데이터 삭제

 

◈ LinkedList 기반 Queue 구현

// Queue<T> q = new LinkedList<>();
Queue<Integer> q = new LinkedList<>();

 

◈ Deque(double-ended queue) 기반 Queue 구현

- 투 포인터 이용 => 앞부분의 샆입 삭제를 O(1) 시간복잡도로 수행 가능

// Queue<T> q = new ArrayDeque<>();
Queue<Integer> q = new ArrayDeque<>();

- 일반적으로 ArrayDeque 가 빠르므로 이를 이용하는 것이 유리

 

◈ Queue 연산

- 삽입(enqueue) : q.add(x);

- 삭제(dequeue) : q.remove();

- front 확인 : q.peek();

- 비었는지 확인: q.isEmpty();

import java.util.ArrayDeque;
import java.util.Queue;

public class ArrayDequeExample {
    public static void main(String[] args) {
        Queue<Integer> q = new ArrayDeque<>();

        // enqueue
        q.add(1); // q: [1]
        q.add(2); // q: [1, 2]
        q.add(3); // q: [1, 2, 3]

        // front, dequeue
        System.out.println(q.peek()); // 출력: 1 // q: [1, 2, 3]
        System.out.println(q.remove()); // 출력: 1 // q: [2, 3]
        System.out.println(q.remove()); // 출력: 2 // q: [3]

        // enqueue
        q.add(4); // q: [3, 4]
        q.add(5); // q: [3, 4, 5]

	      // empty
        while (!q.isEmpty()) {
            System.out.println(q.remove());
        }
    }
}

 

◈ 활용 예제

- BFS 구현

- 큐의 투 포인터 사용

- FIFO 활용

---

[5] Stack

◈ 스택 (Stack)

- 후입 선출 (LIFO) 방식의 자료구조

- push: top에 데이터 추가

- pop: top에서 데이터 추출

 

◈ LinkedList 기반 Stack 구현

// Deque<T> stack = new LinkedList<>();
Deque<Integer> s = new LinkedList<>();

 

◈ Deque(double-ended queue) 기반 Stack 구현

// Deque<T> stack = new ArrayDeque<>();
Deque<Integer> s = new ArrayDeque<>();

- 가장 추천하는 방식

 

◈ Stack 클래스

- 성능이 좋지 않아 권장 방법은 아님

 Stack<Integer> s = new Stack<>();

 

◈ Stack 연산

- 삽입(push) : s.push(x)

- 삭제(pop) : s.pop()

- top 값 출력: s.peek()

- 스택 비었는지 확인: stack.isEmpty()

 

◈ 활용 예제

- 짝 맞추기 (스택에서 하나씩 꺼내서 확인)

- 되돌리기 (최근에 push 한 값 확인)

- DFS

---

[6] 문자열

◈ String 생성

• String.valueOf(x) : 숫자 타입(x)를 문자열로 변경
• new String(charArray) : char 타입 배열 charArray로부터 문자열 생성

char[] helloArray = { 'h', 'e', 'l', 'l', 'o', '.' };
String helloString = new String(helloArray);
System.out.println(helloString); // hello.

◈ 문자열 더하기

•  + 연산자 이용하여 연결

• String world = "world";
  String greeting = "hello, " + world;
  System.out.println(greeting); // hello, world

   

◈ 문자열 길이 구하기

- .length();

 

◈ 특정 위치의 문자 구하기

- charAt(idx);

 

◈ 문자의 인덱스 찾기 

- indexOf(char c);

- lastIndexOf(char c);

 

◈ 문자 변경하기

- replaceAll(String regex, String replacement)

- 정규표현식에 매치되는 부분 문자열을 새로운 문자열로 교체

- 매치된 문자열 모든 부분 교체함

String str = "apple";
String replaced = str.replaceAll("[ap]", "z");
System.out.println(replaced);

 

◈ 문자열 포함 여부 확인

- contains(String str)

 

◈ 문자열 쪼개서 배열로 반환

- split(String regex)

- regex: 쪼갤 기준

 

◈ 문자열 앞 뒤 공백 제거

- trim();

 

◈ 대문자/소문자로 변경

- toUpperCase()

- toLowerCase()

 

◈ 문자열을 문자의 배열로 변경

- toCharArray()

 

◈ 문자열이 특정 문자열로 시작하거나 끝나는지 확인

- startsWith(String str)

- endsWith(String str)

 

◈ 문자열 숫자로 변경

- Integer.parseInt(String str);

- Double.parseDouble(String str);

---

[7] StringBuilder

◈ StringBuilder

- 수정 가능한 문자열 클래스

=> 문자열 수정하면 새로운 인스턴스 생성x, 기존 값 수정

StringBuilder sb = new StringBuilder();
// 선언과 동시에 초기화
StringBuilder sb = new StringBuilder("initial String");

 

◈ StringBuilder 메소드

메소드명	설명
append(String str)	기존 문자열 뒤에 새 문자열 추가
insert(int idx, String str)	지정한 인덱스 위치에 문자열 삽입
delete(int start, int end)	start 부터 end-1 까지 문자 삭제
deleteCharAt(int idx)	idx 위치에 있는 문자 하나 삭제
setCharAt(int idx, char c)	idx 위치에 있는 문자를 c 로 교체
reverse()	기존 문자열 뒤집기
setLength(int len)	문자열 길이 변경 - 새로운 문자열 길이가 기존보다 작으면 나머지 잘리고,  크면 빈 공간은 /u0000으로 채워짐

 

◈ append(String str)

StringBuilder sb = new StringBuilder("Hello, ");
sb.append("World!");
System.out.println(sb); // Hello, World! 출력됨

 

◈ insert(int idx, String str)

StringBuilder sb = new StringBuilder("Hello, World!");
sb.insert(6, " JAVA");
String.out.println(sb); // Hello, JAVA World! 출력

 

◈ delete(int start, int end)

StringBuilder sb = new StringBuilder("Hello, JAVA World!");
sb.delete(6, 11);
String.out.println(sb); // Hello, World! 출력

 

◈ deleteCharAt(int idx)

StringBuilder sb = new StringBuilder("Helloo, World!");
sb.deleteCharAt(5);
String.out.println(sb); // Hello, World! 출력

 

◈ setCharAt(int idx, char c)

StringBuilder sb = new StringBuilder("Hello, World!");
sb.setCharAt(7, 'w');
String.out.println(sb); // Hello, world! 출력

 

◈ reverse()

StringBuilder sb = new StringBuilder("Hello, world!");
sb.reverse();
System.out.println(sb); //!dlrow ,olleH

 

◈ setLength(int len)

StringBuilder sb = new StringBuilder("Hello, world!");
sb.setLength(5);
System.out.println(sb); // Hello

 

◈ String 과의 비교

• 동일한 메서드

• 메서드	설명
  length()	문자열 길이 반환
  charAt(int idx)	특정 인텍스의 문자 반환
  indexOf(String str)	특정 문자열이 처음 나타나는 인덱스 반환
  substring(int start, int end)	지정된 범위의 부분 문자열 반환

• String에만 있는 메서드

• 메서드	설명
  concat(String str)	문자열 연결
  equals(Object obj)	두 문자열 같은지 비교
  toUpperCase()	대문자로 변환
  toLowerCase()	소문자로 변환
  trim()	문자열 앞뒤 공백 제거
  replace(target, replacement)	문자열 내의 특정 문자/문자열을 다른 문자/문자열로 교체

 

---

★ 예제

1. Two Sum

문제 파악

• input 배열(nums)에서 두 수의 합이 target이 되는 두 수의 인덱스 값을 리스트로 출력

접근 방법

• target-nums[i] 가 nums 배열에 존재하는지 확인
  • 탐색의 효율성을 위해 nums를 해시맵에 저장
• 문제의 조건 중 동일한 수는 사용이 불가함을 주의
  • target - nums[i] 의 인덱스와 i 는 서로 달라야 한다는 조건 필요함

코드 구현

package week01.twoSum;

import java.util.HashMap;
import java.util.Map;

public class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> hashmap = new HashMap<>();

        // key가 nums[idx], value가 idx 인 해시맵 생성
        for (int i = 0; i < nums.length; i++) {
            hashmap.put(nums[i], i);
        }

				// 정답 찾기
        for (int i = 0; i < nums.length; i++) {
            if(hashmap.containsKey(target - nums[i]) && hashmap.get(target-nums[i]) != i){
                return new int[]{i, hashmap.get(target-nums[i])};
            }
        }
        return new int[0];
    }
}

2. 올바른 괄호

문제 파악

• 열린 괄호와 닫힌 괄호의 사용이 짝지어져 있는지 확인하여 맞으면 true, 아니면 false를 리턴

접근 방법

• 스택(stack) 자료구조 이용
  • 열린괄호 ( “(” ) 면 스택에 push
  • 닫힌 괄호 ( “)” ) 면 스택에서 pop
    • 스택에 pop 할 것이 없으면 false 리턴
  • 문자열 확인이 끝난 후 스택에 열린 괄호가 남아있으면 false 리턴

코드 구현

import java.util.*;

public class Solution {
    boolean solution(String s) {
        Deque<String> stack = new ArrayDeque<>();

        for(char c : s.toCharArray()) {
            if(c == '(') {
                stack.push("(");
            }
            else if(c == ')') {
                if(stack.isEmpty()) {
                    return false;
                }
                else {
                    stack.pop();
                }
            }
        }
        
        return stack.isEmpty();
    }
}

3. 예산

문제 파악

• d : 부서별 신청한 금액이 포함된 integer 배열
• budget: 예산
• 최대로 지원할 수 있는 부서의 수 리턴

접근 방법

• 신청 금액이 적은 순으로 지원 하면 최대로 부서를 지원 가능함
• d를 오름차순으로 정렬하여 예산 넘지 않도록 지원

코드 구현

import java.util.Arrays;

class Solution {
    public int solution(int[] d, int budget) {
        int answer = 0;
        Arrays.sort(d);

        for(int price: d) {
            if(budget-price < 0)
                break;
            budget -= price;
            answer++;
        }
        
        return answer;
    }
}

4. 소수만들기

문제 파악

• 주어진 배열(nums)에서 소수를 만들 수 있으면 만들 수 있는 경우의 개수 리턴
• nums 원소는 1 이상 100 이하 자연수, 중복된 숫자는 없음

접근 방법

• brute force
• 세 숫자를 골라 해당 숫자의 합이 소수인지 판단
• 소수 판별은 ${n}$$n$$\sqrt{n}$ 내에 존재함을 이용하여 시간 복잡도를 줄임

코드 구현

import java.util.Arrays;

class Solution {
    public int solution(int[] nums) {
        int answer = 0;
        
        Arrays.sort(nums);
        
        for(int i = 0 ; i < nums.length-2 ; i++){
            for(int j = i + 1 ; j < nums.length-1; j++){
                for(int k = j + 1 ; k < nums.length; k++){
                    if(isPrime(nums[i]+nums[j]+nums[k])){
                        answer++;
                    }
                }
            }
        }
        return answer;
    }
    
    boolean isPrime(int n){
        if ( n < 2 ) { return false; }
        for(int i = 2 ; i * i <= n ; i++) {
            if ( n % i == 0){ return false; }
        }
        return true;
    }
}

 

5. 완주하지 못한 선수

문제 파악

• participant : 마라톤에 참여한 선수들 이름 배열
• completion: 완주한 선수들 이름 배열
• participant 배열에는 있으나 completion 배열에는 없는 사람 이름 리턴

접근 방법

• 참가자와 완주자 명단을 정렬한 후 하나씩 비교

코드 구현

import java.util.Arrays;

class Solution {
    public String solution(String[] participant, String[] completion) {

        Arrays.sort(participant);
        Arrays.sort(completion);
        
        for(int i = 0 ; i < completion.length; i++){
            if(!participant[i].equals(completion[i]))
                return participant[i];
        }
        
        return participant[participant.length-1];
    }
}

6. 전화번호 목록

문제 파악

• phonebook : 전화번호가 저장된 String 배열
• phonebook 내의 전화번호 중 어느 전화번호가 다른 전화번호의 접두어가 되는 경우가 있으면 false, 없으면 true 리턴

접근 방법

• phonebook을 정렬하면, 문자열이므로 크기가 숫자 크기 순서로 정렬되는 것이 아닌 아스키 코드 순으로 정렬됨을 이용
• 즉, 숫자의 앞 부분이 동일하다면 길이가 짧은 번호가 길이가 긴 번호보다 바로 앞에 있게 된다.
  • 길이가 짧은 번호 = 접두어
• phonebook[i]이 phonebook[i+1]의 접두어인지만 확인하면 된다.

코드 구현

import java.util.*;

public class Solution {
    public boolean solution(String[] phone_book) {
        Arrays.sort(phone_book);

        for (int i = 0; i < phone_book.length-1; i++) {
            if (phone_book[i+1].startsWith(phone_book[i])) {
                return false;
            }
        }
        return true;
    }
}

7. 주식 가격

문제 파악

• 변수
  • prices: 주식 가격을 저장한 int 배열
  • answer: 주식이 얼마의 시간동안 떨어지지 않았는지 저장하는 배열

접근 방법

• 스택(stack) 자료구조 이용
  • 스택에 주식가격의 인덱스를 저장
  • 현재 가격 prices[i] 보다 과거의 가격 prices[j] 이 더 크면 가격이 떨어진 것 ⇒ 스택에서 과거의 가격 인덱스 j 를 pop 하고, answer[j] 에는 지속 시간인 i-j 를 저장
  • 스택에 남아있는 인덱스들은 마지막까지 가격이 떨어지지 않은 것이므로 $j <time < prices.length$ 기간동안 가격이 떨어지지 않은 것 ⇒ answer[j] 에 prices.length - j - 1 만큼 저장해야 함

코드 구현

package week01.stockPrice;

import java.util.*;

class Solution {
    public int[] solution(int[] prices) {
        int[] answer = new int[prices.length];
        Deque<Integer> stack = new ArrayDeque<>();

        for (int i = 0; i < prices.length; i++) {
            while(!stack.isEmpty()) {
                int j = stack.peek();
                if (prices[i] < prices[j]) {
                    answer[j] = i - j;
                    stack.pop();
                }
                else { break; }
            }
            stack.push(i);
        }
        
				// 스택에 남아있는 가격들은 끝까지 가격이 떨어지지 않은 것 
        while (!stack.isEmpty()) {
            int j = stack.pop();
            answer[j] = prices.length - j - 1;
        }
        return answer;
    }
}

8. Daily Temperatures

문제 파악

• 변수
  • temperatures : 기온을 저장하는 int 배열 (input)
  • result : 며칠 후에 온도가 올랐는지를 저장하는 int 배열 (리턴해야하는 output)
• 온도가 오른적이 없으면 result[i]=0 으로 저장한다.

접근 방법

• 스택 자료구조 이용 (Deque<> LinkedList)
  • 스택에 기온 배열(temperatures)의 index를 저장
  • 과거의 기온인 stack의 top 기온(temperatures[j])과 현재 기온(temperatures[i])의 온도 비교
  • 현재의 기온이 더 크다면 과거의 기온 입장에서는 기온이 올랐다는 것을 의미함 ⇒ 두 인덱스 차이(i-j)를 결과배열에 저장
  • 현재의 기온이 더 작다면 과거의 기온 입장에서는 아직 기온이 오르지 않았음을 의미함 ⇒ 스택을 pop 할 필요 없음
  • 기온 배열의 연산이 모두 끝난 후에도 스택에 저장되어 있는 기온 인덱스들은 기온이 오른적이 없음을 의미하므로 0으로 저장

코드 구현

import java.util.*;

class Solution {
    public int[] dailyTemperatures(int[] temperatures) {
        int[] result = new int[temperatures.length];
        Deque<Integer> stack = new LinkedList<>();

        for (int i = 0; i < temperatures.length ; i++) {
            while(!stack.isEmpty()){
                int j = stack.peek();
                if(temperatures[i] > temperatures[j]){
                    result[j] = i-j;
                    stack.pop();
                } else {
                    break;
                }
            }
            stack.push(i);
        }

        while(!stack.isEmpty()){
            int j = stack.pop();
            result[j] = 0;
        }

        return result;        
    }
}

 

9. 신규 아이디 추천

 

10.

 

11.