[Java | 코딩테스트] 코딩테스트 문법 정리

알린·2023년 11월 19일

Java 코딩테스트

코딩테스트

목록 보기

1/15

쏟아지는 코테들 앞두고 답답해서 하는 Java 코딩테스트 문법 정리

📚 문자열 처리

String

한 번 만들어지면 문자를 추가하거나 삭제할 수 없는 변경 불가한 타입
많은 문자열을 연결하면 많은 중간 문자열 객체가 생성되어 비효율적(성능 저하)

StringBuilder

한 번 만든 후에도 변경이 가능한 타입
String을 연결하는 작업 시 효율적

StringTokenizer

구분자로 문자열 나누기

공백 없는 숫자를 각각의 int 배열로 저장하기

String 배열로 split("") 사용해 한 줄 받기

String[] str = br.readLine().split("");

str 배열의 순서대로 정수형 배열에 삽입

miro[i][j] = Integer.parseInt(str[j]);

코드

ver.1

for (int i = 0; i < N; i++) {
     String[] str = br.readLine().split("");
     for (int j = 0; j < M; j++) {
          miro[i][j] = Integer.parseInt(str[j]);
      }
}

ver.2

for (int i = 0; i < N; i++) {
     String[] str = br.readLine();
     for (int j = 0; j < M; j++) {
          miro[i][j] = str.charAt(j) - '0';
      }
}

공백 없는 문자를 각각의 char 배열로 저장하기

for(int i = 0; i < N; i++) {
	String str = br.readLine();
    for(int j = 0; j < M; j++) {
		dna[j] = str.charAt(j);
    }
}

📚 배열, 리스트

크기가 가변적인 배열이 필요하다면 ArrayList
탐색이 빈번히 일어나는 경우 ArrayList
Index가 필요 없다면(탐색이 필요없다면) LinkedList
삽입이나 삭제 연산이 빈번히 일어나는 경우 LinkedList

배열과 배열리스트, 연결리스트의 삭제 과정 비교

배열(Array)

메모리 상에 데이터가 연속적으로 저장(순차 리스트)
최초 배열의 사이즈를 지정해야 배열 구성 가능
고정된 크기를 가짐(메모리 낭비될 수 있음)
논리적 저장 순서 = 물리적 저장 순서
Index로 저장된 데이터 참조

선언

// 사이즈와 값이 둘 다 없는 빈 배열
String[] arr = {};
arr = new String[3];

// 사이즈는 존재하지만 값이 없는 빈 배열
String[] arr = new String[3];

// 사이즈가 자동 지정된 값이 있는 배열
String[] arr = {"A", "b", "C"};

리스트(List)

Linked List, ArrayList 등의 선형 자료 구조를 구현할 때 사용하는 추상 자료형
크기가 가변적 👉 데이터를 담을 공간의 추가, 삭제가 가능

순차리스트(Sequential List)(= 배열리스트(ArrayList))

배열을 이용하여 리스트를 구현
데이터를 메모리 상에 순차적으로 연속하여 저장
빈자리 공간 없이 순서대로 저장
논리적 순서 = 물리적 순서
탐색에서 효율적, 추가나 삭제에서는 비효율적

연결리스트(Linked List)

데이터들을 노드에 분산하여 저장
노드는 데이터를 저장하는 데이터 필드와 위치를 저장하는 링크 필드로 구성
데이터가 메모리 상에 연속적으로 저장되지 않음
논리적인 순서로 메모리 저장
추가나 삭제에서 효율적, 탐색에서 비효율
논리적 저장 순서와 물리적 저장 순서가 다름(실제 메모리 주소 랜덤)

👉 연결리스트 자세한 설명은 여기

배열, 리스트 형변환

// 문자열 배열 → List
String[] tmp = "abcde";
List<String> list = new ArrayList<>(Arrays.asList(tmp));

// List → 문자열 배열
List<String> list = new ArrayList<>();
String[] tmp = list.toArray(new String[list.size()]);

// 정수형 배열 → List
int[] tmp = {1111, 2222, 3333, 4444};
List<Integer> list = new ArrayList<>(Arrays.asList(tmp));

// List → 정수형 배열
List<Integer> list = new ArrayList<>();
int[] tmp = list.stream().mapToInt(i->i).toArray();

📚 Stack

시간 순서상 가장 최근에 추가한 데이터가 가장 먼저 나오는 후입선출 LIFO(Last In First Out)형식으로 데이터를 저장하는 자료구조

Stack 클래스

Stack 클래스: 스택 자료구조를 구현한 클래스
Deque 인터페이스와 ArrayDeque를 사용하는 방식에 비해 성능상으로 떨어지기에 사용을 권장하지 않음

Stack<Ingeger> stack = new Stack<>();

Linked List 기반 Stack 구현

LinkedList는 doubly linked list이므로 스택으로도 사용 가능

Deque<Integer> stack = new LinkedList<>();

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

ArrayDeque 역시 양쪽에서 삽입, 삭제가 가능하므로 스택으로 활용 가능
다른 클래스들에 비해 가장 좋은 성능

Deque<Integer> stack = new ArrayDeque<>();

메서드

Stack<Ingeger> stack = new Stack<>();
Deque<Integer> stack = new ArrayDeque<>();
Deque<Integer> stack = new LinkedList<>();

stack.push(1) // 값 추가
stack.pop() // 마지막 값 삭제
stack.clear() // 값 전체삭제
stack.size() // 크기 반환
stack.isEmpty() // 비어있으면 true, 아니면 false
stack.contains(1) // 1을 포함하고 있으면 true, 아니면 false
stack.peek() // Stack top 출력 (제거 X), 비어있으면 null 반환

문제 적용

짝 맞추기
- 새로운 값이 push 하려할 때, 기존 Stack의 top과 짝을 이루게 되면, push하려는 값과 기존 top을 같이 pop하는 방식
- 유효 괄호쌍 검사, 동일 블록 제거하기 문제
되돌리기
- stack에 임시로 데이터를 저장하다가, top에서 가장 최근에 push했던 값을 확인 가능
DFS(재귀)
- 재귀적 함수 호출은 push, 함수 종료는 pop 하는 것과 같은 형태

📚 Queue

먼저 저장한 데이터가 먼저 출력되는 선입선출 FIFO(First In First Out)형식으로 데이터를 저장하는 자료구조

Linked List 기반 Queue 구현

LinkedList는 연결 리스트를 구현한 클래스로, 큐로 사용할 수 있습니다. 내부적으로 doubly linked list로 구현되어 있음

Queue<Integer> queue = new LinkedList<>();

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

ArrayDeque은 양쪽 끝에서 삽입, 삭제가 가능한 덱(deque) 자료구조를 dynamic array 방식으로 구현한 것
투 포인터를 이용해서 앞부분의 삽입, 삭제를 $O(1)$ 시간복잡도로 수행할

Queue<Integer> queue = new ArrayDeque<>();

일반적으로 ÀrrayDeque가 다른 클래스들에 비해 가장 빠름
=> 특별한 이유가 없다면 `ArrayDeque 사용하기

메서드

Queue<Integer> queue = new ArrayDeque<>();
Queue<Integer> queue = new LinkedList<>();

queue.add(1) // 값 추가
queue.offer(2) // 값 추가
queue.poll() // 첫 번째 값 반환 후 제거, 비어있으면 null 반환
queue.remove() // 첫 번째 값 제거
queue.clear() // 값 모두 삭제
queue.peek() // 첫 번째 값 출력 (제거 X)
queue.isEmpty() // 큐가 비어있는지 확인

문제 적용

BFS 구현
- queue에 현재 정점에 인접한 정점들을 저장
- 순차적으로 dequeue해서 각 정점을 방문
투포인터 사용
- 투포인터: 두 포인트의 위치를 기록하는 것을 활용하는 알고리즘
- 한 큐에서 dequeue된 값은 다른 큐에 enqueue된다는 특성 이용해 2개의 queue들을 1개의 queue로 이어서 투포인터 알고리즘으로 2개의 큐로 나누는 지점을 찾아가는 방식으로 시간복잡도 줄임
FIFO 활용
- 먼저 온 데이터를 먼저 출력해야하는 문제인 경우

📚 Deque

Double-Ended Queue의 약자 (양방향 큐)
스택과 큐의 혼합형
데이터 추출과 삭제 앞, 뒤로 모두 가능

Deque<Integer> dq = new ArrayDeque<>();
Deque<int[]> dq = new ArrayDeque<int[]>();  // Deque 배열 선언 시

dq.offer(1) // 값 추가 (큐랑 같음)
dq.offerFirst(1) // 앞으로 추가 (큐랑 반대)
dq.offerLast(1) // 뒤로 추가
dq.offer(new int[]{5,4,1,....,}) // 배열 추가

dq.poll(1) // 첫 번째 값 반환 후 제거, 비어있으면 null 반환 (큐랑 같음)
dq.pollFirst(1) // 첫 번째 값 반환 후 제거, 비어있으면 null 반환 (큐랑 같음)
dq.pollLast // 마지막 값 반환 후 제거, 비어있으면 null 반환 (큐랑 반대)
dq.peek() // 마지막 값 출력 (제거 X), 비어있으면 null 반환 (스택과 같음)
dq.get() // peek()과 같음


// 이 외에 add, offer, push, pop 모두 first, last 사용 가능
// push만 first, last 사용 불가

📚 PriorityQueue

들어온 순서에 상관없이 원소에 우선순위를 부여해 그 우선순위가 높은 순서대로 원소를 추출하는 큐
내부적으로 힙(heap)이라는 완전이진트리로 되어 있음

PriorityQueue<Integer> pq = new PriorityQueue<>(큐의 초기용량, Comparator를 정의하는 람다식);
// 기본은 낮은 숫자가 우선순위를 갖는다.
// 높은 숫자가 우선되게 하려면 () 안에 Collections.reverseOrder() 작성

pq.add(1) // 값 추가
pq.offer(1) // 값 추가
pq.poll() // 첫 번째 값 반환 후 제거, 비어있으면 null 반환
pq.remove() // 첫 번째 값 제거
pq.clear() // 값 모두 삭제
pq.peek() // 첫 번째 값 출력 (제거 X)

public void test_student_age() {
        int capacity = 4;
        
        // Student 객체 Age의 가장 낮은 값이 먼저 추출되도록 설정
        PriorityQueue<Student> studentAgeHeap = new PriorityQueue<>(capacity, Comparator.comparing((Student student) -> student.getAge()));

        studentAgeHeap.add(new Student("Frank", 23));
        studentAgeHeap.add(new Student("Angela", 10));
        studentAgeHeap.add(new Student("David", 30));
        studentAgeHeap.add(new Student("Joe", 15));

        assertThat(studentAgeHeap.poll().getName()); // Angela 출력
        assertThat(studentAgeHeap.poll().getName());  // Joe 출력

}

📚 HashSet

HashSet : 중복을 허용하지 않는 구조, 순서가 없고 정렬도 안 함
LinkedHashSet : 중복을 허용하지 않는 구조, 삽입된 순서대로 순서를 관리
TreeSet : 중복을 허용하지 않는 구조, 이진탐색트리 형태로 데이터를 저장하므로 정렬

👉 HashSet, HashMap 추가 설명

HashSet<Integer> set = new HashSet<>();

set.add(1) // 값 추가
set.remove(1) // 값이 1인 데이터 삭제
set.removeAll(set2) // set의 데이터 중 set2에 들어있는 데이터를 모두 삭제
set.retainAll(set2) // set의 데이터 중 set2에 들어있지 않은 데이터를 모두 삭제
set.clear() // 모든 데이터 삭제
set.size() // 크기 반환
set.contains(1) // 값 1이 있으면 true, 없으면 false

// 값 출력
// 방법 1: get 메소드가 없으므로 원소에 접근하려면 이터레이터 사용
Iterator iter = set.iterator();
while (iter.hasNext())
	System.out.println(iter.next());

// 방법 2: for-each문으로 원소에 접근
for (String item: set)
	System.out.println(item);

📚 HashMap

Map 인터페이스의 한 종류로 <key, value>로 이루어짐
key 값 중복 불가능, value는 중복 가능(null 사용도 가능)
=> 만일 기존에 저장된 key와 동일한 키로 value를 저장하면 기존의 value는 새로운 value로 대체됨)
Hashing을 사용하기 때문에 많은 양의 데이터 검색에 있어서 뛰어난 성능

출력 규칙

HashMap : 특정 규칙 없이 출력됨
LinkedHashMap : key 값이 입력순으로 정렬되어 출력
TreeMap : key 값이 알파벳순(오름차순)으로 정렬되어 출력

👉 HashSet, HashMap 추가 설명

HashMap<Integer, String> map = new HashMap<Integer, String>();
HashMap<Integer, String> map = new HashMap<>();  // 타입 파라미터 생략 가능

map.put(1, "사과");  // Key 삽입
map.remove(1);  // key값으로 value 삭제
map.clear();  // 전체 삭제

map.values(); // 저장된 모든 value 출력
map.get(1);  // Key값으로 value 반환
map.containsKey(1);  // Key 포함여부 반환(있으면 true, 없으면 false)
map.containsValue("사과");  // value 포함 여부 반환 

map.isEmpty();  // HashMap 비어있는지 여부 반환
map.keySet();  // HashMap에 저장된 모든 Key 반환
map.size();  // HashMap에 저장된 요소의 개수 반환

// 출력
// 전체 출력
System.out.println(map); // {1=사과}

// 저장된 key 값 확인
for (Integer i : map.keySet()) {
  System.out.println(map.get(i));  // 사과
}

// entrySet() 활용
for (Entry<Integer, String> entry: map.entrySet())
  System.out.println(entry.getKey() + entry.getValue());  // 1 사과

알린

짱이 되고싶은 개발 기록

다음 포스트

[Java | 코딩테스트] 코딩테스트 문법 정리

코딩테스트

📚 문자열 처리

String

관련 메소드

StringBuilder

관련 메소드

StringTokenizer

관련 메소드

공백 없는 숫자를 각각의 int 배열로 저장하기

코드

ver.1

ver.2

공백 없는 문자를 각각의 char 배열로 저장하기

📚 배열, 리스트

배열(Array)

선언

관련 메소드

리스트(List)

순차리스트(Sequential List)(= 배열리스트(ArrayList))

관련 메소드

연결리스트(Linked List)

배열, 리스트 형변환

📚 Stack

Stack 클래스

Linked List 기반 Stack 구현

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

메서드

문제 적용

📚 Queue

Linked List 기반 Queue 구현

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

메서드

문제 적용

📚 Deque

📚 PriorityQueue

📚 HashSet

📚 HashMap

출력 규칙

[Java | 자료구조] 연결 리스트 (Linked List)

0개의 댓글

[Java | 자료구조] 연결 리스트 (Linked List)