CHAAANY ARCHIVE
3개의 기록을 주제별로 둘러보세요.
백준 18258번은 여섯 가지 명령으로 큐의 선입선출 동작을 구현하는 문제다. 원문에서는 같은 코드를 삼항 연산자 사용 전후로 나눠 보았다. 다시 정리해 보니 핵심은 표현식의 길이가 아니라 큐의 양 끝을 어떻게 다루고, 최대 200만 개의 명령을 어떻게 한꺼번에 출력하느냐에 있었다.백준 18258번 큐 2배열과 두 인덱스로 큐 자체를 구현하는 방법은 백준 18258 배열 큐 풀이에 따로 남겼다. 이 글에서는 Java 표준 자료구조인 ArrayDeque를 사용한다.명령을 Queue 연산으로 그대로 옮긴다ArrayDeque에서는 앞과 뒤를 메서드 이름으로 분명하게 드러낼 수 있다.명령ArrayDeque 연산비어 있을 때push XaddLast(X)해당 없음popremoveFirst()-1 출력sizesize..
백준 15828번 ‘Router’는 크기가 정해진 buffer에 packet을 넣고 처리하는 과정을 simulation한다. 들어온 packet number는 queue 뒤에 넣고, 0이면 가장 앞 packet을 처리하며, -1이면 입력을 끝낸다.백준 15828번 Router입력값별 동작입력동작양수buffer에 빈자리가 있으면 뒤에 추가, 가득 차면 버림0buffer가 비어 있지 않으면 앞 packet 제거-1simulation 종료queue의 실제 크기를 size()로 확인하면 별도의 packetCount를 동기화할 필요가 없다. 두 상태를 따로 관리하면 한쪽만 갱신하는 branch에서 오류가 생길 수 있다.Java 코드import java.io.BufferedReader;import java.io.I..
백준 1021번을 처음 읽었을 때는 두 번째 예제가 왜 그렇게 움직이는지 헷갈렸다. 원문에는 시계 방향과 반시계 방향으로 돌린 횟수를 각각 구해 더 작은 값을 선택하면 된다고 정리해 두었다.백준 1021번 회전하는 큐방향별 Deque를 두 개 만들 필요는 없다. 현재 큐에서 target의 왼쪽 거리를 찾으면 오른쪽 거리는 현재 크기 - 왼쪽 거리다. 더 짧은 방향으로 실제 큐 하나만 회전하고 target을 꺼내면 된다.이동 횟수를 index로 바꾸기현재 큐가 다음과 같다고 하자.front → [1, 2, 3, 4, 5] ← backtarget = 44의 왼쪽 index는 3이다.왼쪽 회전: 3회오른쪽 회전: 5 - 3 = 2회따라서 오른쪽으로 두 번 회전한 뒤 맨 앞의 4를 꺼낸다. target을 꺼내는..