JAVA26 [Java] 10866번. 덱 1. 문제 분석이전에, 큐와 스택을 구현할 때는 Linked List를 이용하여 구현하였다. 이번에 구현할 deque도 Linked List를 이용해 구현할 수 있지만,deque는방향이 정방향/역방향 두 방향이기 때문에 Double Linked List로 구현해야겠다는 생각이 들었다. deque를 양방향 링크드 리스트(Double Linked List)로 구현하면 다음과 같은 차이점이 있다. 장점각 노드가 이전 노드와 다음 노드를 모두 참조하므로, 앞과 뒤 양쪽에서 삽입과 삭제가 용이하다.덱의 앞과 뒤에서 O(1)시간에 삽입과 삭제를 할 수 있다. 단점양방향 포인터를 관리해야 하므로 구현이 더 복잡하다.각 노드가 두 개의 포인터를 가지고 있으므로 메모리가 더 많이 사용된다. 2. 구현Deque 클래스는 .. 2024. 6. 19. [JAVA] Queue를 LinkedList/ArrayDeque로 구현했을 때 차이점 *작성자는 공부 중인 학생으로 잘못 된 정보가 있을 수 있음을 알려드립니다. Queue와 관련된 문제들의 풀이를 보면서Queue를 정의할 때 두가지 방법으로 나뉘는 것을 발견했다. //방법1 : LinkedList 이용Queue queue = new LinkedList();//방법2 : ArrayDeque 이용Queue queue = new ArrayDeque(); 위 두가지 방법의 차이점은 무엇일까?그리고 왜 Queue queue = new Queue();로 생성할 수 없는 것일까? 1. new Queue()를 사용할 수 없는 이유결론부터 말하자면 Queue는 클래스가 아닌 인터페이스이기 때문이다. 인터페이스는 메서드의 선언만 포함하고 실제 구현은 포함하지 않는다.public interface Anim.. 2024. 6. 16. [Java] 스택(Stack) 스택(Stack)이란?스택은 가장 마지막에 들어간 것이가장 처음 나오는 구조이다.이를 LIFO(Last-In-First-Out)라고 한다. 사용하는 대표 사례는수식의 괄호 쌍이나 전위/중위/후위 표기법, DFS, Flood Fill, undo/redo를 구현하는데 사용된다. Java에서 스택을 사용하기 위해서import java.util.stack 코드를 추가해줘야 한다. Java의 스택에서 제공하는 주요 함수는 다음과 같다.Methodpush(item)스택의 가장 위에 item을 추가하고, 추가된 요소를 반환한다.pop()스택의 가장 위에 있는 요소를 삭제하면서, 가장 위 요소를 반환한다.peek()스택의 가장 위에 있는 요소를 삭제하지 않고, 가장 위 요소를 반환한다.empty()스택이 비었는지 확인.. 2024. 5. 30. [Java] 1919번. 애너그램 만들기 문제 링크 https://www.acmicpc.net/problem/1919*최종 코드는 1차 코드가 아닌 아래쪽 최종 코드를 참고해주시기 바랍니다. 문제 분석이 문제는 쉽게 말하자면 각 문자열이 겹치지 않는 알파벳의 개수를 묻는 것이다.aabbcc와 bbxxyy에서 bb를 제외한 나머지는 모두 겹치지 않기 때문에애너그램을 만들기 위해서는 bb를 제외한, aa,cc,xx,yy를 제거해야 한다. 내가 생각한 방식은 다음과 같다.1. 두개의 문자열을 입력받는다.2. 앞 문자열을 순회하면서 알파벳 배열에 해당하는 알파벳을 +한다.3. 뒷 문자열을 순회하면서 알파벳 배열에 해당하는 알파벳을 -한다.이렇게 하면 두개의 배열을 만들 필요 없이 26 크기를 가진 배열 하나로 계산이 가능하다. 그리고 마지막으로 배열의.. 2024. 5. 28. [Java] 13300번. 방배정 문제 링크 https://www.acmicpc.net/problem/13300문제 분석각 학생들은 학년과 성별로 구분된다.같은 학년의 같은 성별끼리 구성되어야 하므로 2중 배열을 사용해서같은 학년이면서 같은 성별인 학생끼리 함께 저장한 후에 이를 방의 최대 인원으로 나누고 올림을 하면 방의 개수를 구할 수 있다. 구현 순서를 다음과 같이 정리할 수 있다.1. 전체 학생 수와 최대 인원을 입력받는다.2. 전체 학생 수 만큼 입력을 받는다.(같은 학년/같은 성별끼리 저장)3. 각 배열 값을 K로 나누고 올림하여 방의 개수를 모두 더한다.최종 코드import java.io.*;public class Main { public static void main(String[] args) throws IOExce.. 2024. 5. 28. [Java] 1158번. 요세푸스 문제 문제 링크 https://www.acmicpc.net/problem/1158문제 분석이 문제를 처음 읽었을 때,이 문제는 완전히 '원형연결리스트(Circular Linked List)'아니야?!라는 생각을 했다.그런데 Java에서의 LinkedList는 기본적으로 양방향이며,원형 연결리스트 기능은 지원하지 않는다. 자바에서 구현한 연결 리스트의 노드에는내부적으로 이전과 다음 노드의 주소값을 가지고 있다고 했는데그냥 이 주소값을 수동으로 바꾸어서마지막 노드의 다음 노드 주소값에 첫번째 노드의 주소값을 넣으면 되지 않을까?라는 생각에 열심히 알아보았지만,Java에서 지원하는 LinkedList의 참조값을 직접 수정할 수 없다고 한다. 따라서 문제를 해결 할 수 있는 방안은 크게 다음과 같다.1. 원형 연결 .. 2024. 5. 28. [Java] 5397번. 키로거 문제 링크 https://www.acmicpc.net/problem/5397 문제 분석이전에 풀었던 1406번 에디터 문제와 크게 다르지 않다.동일하게 문자의 삽입과 삭제가 빈번하게 일어나는 문제이므로LinkedList로 구현한다. 구상한 해결 방안은 다음과 같다.1.int형 변수를 입력받는다.2.입력받은 수 만큼 아래 과정을 반복한다.3.문자열을 입력받는다.4.를 입력하면 오른쪽으로 이동-를 입력하면 왼쪽의 문자를 삭제, 문자를 입력하면 저장한다.5.최종 LinkedList를 문자열로 변환 후 출력한다. 모두 1406번에서 구현한 코드이기 때문에 어렵지 않게 구현할 수 있다. 최종 코드import java.io.*;import java.util.LinkedList;import java.util.List.. 2024. 5. 28. [Java] 1406번. 에디터 문제 링크 https://www.acmicpc.net/problem/1406*최종 코드는 1차 코드가 아닌 아래쪽 최종 코드를 참고해주시기 바랍니다. 문제 분석문자열의 길이가 최대 100,000이고 최대 500,000번의 삽입/삭제 또는 커서의 이동이 일어난다.삽입 삭제가 주된 문제이기 때문에 Linked List로 접근하면 된다. 내가 구상한 해결법은 다음과 같다.1. 문자열을 입력받는다.2. LinkedList로 변환한다.3. M(명령어 개수)를 입력받는다.4. 커서를 가장 마지막에 위치시킨다.5. M만큼 돌면서 명령어를 실행시킨다. 여기서, 4번에는 세부적으로 다양한 구현이 있다.방법1) 2번의 LinkedList로 변환하는 과정에서 length++로 연산한다. -> O(1)방법2)LinkedLis.. 2024. 5. 27. 이전 1 2 3 다음
