본문 바로가기

전체보기

 (126)
[백준] 9019번: DSLR - JAVA 🔗 문제 링크 BOJ 9019번: DSLR 9019번: DSLR 네 개의 명령어 D, S, L, R 을 이용하는 간단한 계산기가 있다. 이 계산기에는 레지스터가 하나 있는데, 이 레지스터에는 0 이상 10,000 미만의 십진수를 저장할 수 있다. 각 명령어는 이 레지스터에 www.acmicpc.net 📝 풀이 과정 숫자와 문자열을 동시에 저장해야 하기 때문에 Register class를 만들어주었다. class에서 D, S, L, R을 한 연산을 처리한 결과를 반환해주기로 하였다. D 연산의 경우 n을 2배한 뒤 값이 9999보다 크다면 %10000 값을 반환하라고 하지만 9999보다 작은 경우에는 %10000을 한다면 원래 값이 반환되므로 num * 2 % 10000을 반환한다. S 연산의 경우 n =..
[백준] 7662번: 이중 우선순위 큐 - JAVA 🔗 문제 링크 BOJ 7662번: 이중 우선순위 큐 7662번: 이중 우선순위 큐 입력 데이터는 표준입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터의 첫째 줄에는 Q에 적 www.acmicpc.net 1️⃣ PriotyQueue 📝 풀이 과정 큰 값과 작은 값으로 정렬해야 하기 때문에 고민하다 PriorityQueue를 두 개 사용하여 작은 값을 기준으로하는 minQueue와 큰 값을 기준으로 하는 maxQueue를 선언하였다. 기본적으로 PriorityQueue는 작은 값이 먼저 poll되기 때문에 maxQueue에는 Collections.reverseOrder()를 활용해 반대로 정렬하였다. 하지만,..
[백준] 7569번: 토마토 - JAVA 🔗 문제 링크 BOJ 7569번: 토마토 7569번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, www.acmicpc.net 📝 풀이 과정 [백준] 7576번: 토마토에서 높이만 추가된 문제이다. 높이가 추가되었기 때문에 기존 4방향(앞, 뒤, 왼쪽, 오른쪽) 탐색에서 2방향(위, 아래)도 탐색해야한다. 이 문제에서 헷갈릴 수 있는 부분은 배열 선언 부분인데 기존 tomato[N][M]배열이 높이(H)개 만큼 존재하는 것이므로 tomato[H][N][M]이 되어야 한다! 💻 코드 import java.util.Linked..
[백준] 7576번: 토마토 - JAVA 🔗 문제 링크 BOJ 7576번: 토마토 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 📝 풀이 과정 익은 토마토가 주변의 앞, 뒤, 왼쪽, 오른쪽 4방향의 안익은 토마토를 익게 만드는 총 일수를 구하는 문제이다. 전형적인 BFS 문제의 구조를 띄고 있다. 처음 입력을 받으며 익은 토마토는 Queue에 넣는다.나의 경우 Queue에 int[] 배열로 토마토의 위치를 저장하였다. 마지막에 안익은 토마토가 존재할 경우 -1을 출력하는 조건 존재하기 때문에 이를 처리하기 위해 안익은 토마토가 등장..
[백준] 5525번: IOIOI - JAVA 🔗 문제 링크 BOJ 5525번: IOIOI 5525번: IOIOI 첫째 줄에 N이 주어진다. 둘째 줄에는 S의 길이 M이 주어지며, 셋째 줄에 S가 주어진다. (1 ≤ N ≤ 1,000,000, 2N+1 ≤ M ≤ 1,000,000) www.acmicpc.net 📝 풀이 과정 문제에서 핵심은 $P_N$에서 O는 N개만큼 들어있다는 점이다. 따라서, 현재 칸까지 'OI'가 몇 개 반복되었는지 누적하도록 하였다. 예를 들어, N = 1, S = OOIOIIOII인 경우를 살펴보자. 위와 같이 arr = M.toCharArray()이고, memo는 'OI'의 누적 갯수를 저장할 배열들이고, ans는 $P_N$이 몇 개 들어가는지 저장할 변수이다. i = 1일 경우, arr[i + 1]의 값이 'I'이므로 m..
[백준] 6064번: 카잉 달력 - JAVA 문제 링크 BOJ 6064번: 카잉 달력 6064번: 카잉 달력 입력 데이터는 표준 입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터는 한 줄로 구성된다. www.acmicpc.net 풀이 과정 아 문제의 핵심은 만일 x < M 이면 x' = x + 1이고, 그렇지 않으면 x' = 1이다. 같은 방식으로 만일 y < N이면 y' = y + 1이고, 그렇지 않으면 y' = 1이다. 예를 들어, # 일 때 1번째 해 : 2번째 해 : ... 10번째 해 : 11번째 해 : 12번째 해 : 13번째 해 : 이 처럼 x가 M, y가 N에 도달할 경우 1로 변경된다는 것이다. 단순히 하나씩 계산하며 만족하는 결과를..
[백준] 5430번: AC - JAVA 문제 링크 BOJ 5430번: AC 5430번: AC 각 테스트 케이스에 대해서, 입력으로 주어진 정수 배열에 함수를 수행한 결과를 출력한다. 만약, 에러가 발생한 경우에는 error를 출력한다. www.acmicpc.net 풀이 과정 명령어가 R이면 배열 전체를 뒤집고, D라면 첫번째 인자를 삭제하기 때문에 전체 배열을 뒤집는 경우는 $O(N)$의 시간복잡도가 소요되기 때문에, 배열을 직접 뒤집는게 아닌 조건에 따라 앞과 뒤에서 삭제하는 방식을 사용하기로 했다. 때문에, 앞과 뒤에서 pop을 자유롭게 할 수 있는 Deque를 활용하기로 했다. 입력의 앞과 뒤에 붙은 괄호를 제거하기 위해 substring(1, str.length())를 활용해 앞뒤로 한 개씩 삭제해 주었고, split을 사용해 ','을..
ArrayList와 LinkedList의 차이, 선택하기 알고리즘 문제를 풀면서 List를 사용해야 되는 일이 자주 발생한다. 차이를 알아보고 효율적인 Collection을 선택해보자 ArrayList 구조 ArrayList는 내부적으로 배열의 형태를 지니고 있다. get / set 배열의 index를 통해 접근하는 방식이기 때문에, random access속도가 빠르며 get / set 메소드는 상수 시간을 가지게 된다. add ArrayList는 배열이기 때문에 중간에 값을 끼워넣는 연산이 불가능하다. 만약 새로운 값을 추가하려고 할 때, List의 크기가 생성되어 있는 배열의 size(생성시 따로 설정하지 않았다면 size = 10인 배열이 생성된다)보다 커지게 되면, 이전 크기의 2배가 되는 배열을 생성해 배열 전체를 복사하여 새로운 배열에 복사하고 제..

티스토리툴바