2021년 7월 17일 토요일 - 오늘도 덥다아..
오늘 올려볼 문제는 2243번 사탕상자 라는 문제이다.
사진을 클릭하면 해당 문제로 이동합니다.
오늘은 딱 보기에는 쉬워보이는 문제를 가져왔다!보기에만 그렇다는거
논리는 간단할 수 있지만 메모리를 어떻게 적게 사용할 수 있는지 고민해야 하는게 가장 큰 핵심인 것이 이 문제다!
입력 예제
확실히 이번 문제는 입력 예제만 보고서는 이해가 힘든 문제이다...
그렇기에 글로 한 번 다시 간략하게 설명해보자면
- 첫째 줄에는 사탕상자에 접근하는 횟수를 나타낸다.
- 이 때 접근이라 하면 사탕을 넣고 빼는 것을 모두 얘기한다.
- 둘째 줄부터는 사탕상자에 접근하는 방법에 대한 입력이 한 줄 단위로 주어진다.
- 1번 숫자가 1이라면, 2번 숫자의 맛을 가진 사탕을 , 3번 숫자만큼 상자에 더한다. (이때 3번 숫자는 음수일 수 있다.)
- 1번 숫자가 2라면, 2번 숫자번째로 맛있는 사탕을 상자에서 꺼내고, 꺼낸 사탕의 맛을 출력한다.
문제에 대한 이해는 생각보다 쉬운편이다.
하지만 이를 제한된 자원으로 구현할 걸 생각하면 머리가 아파올 것이다...
풀이 및 코드
처음 생각한 풀이로는
- 사탕의 맛이 1 ~ 1,000,000까지 이므로 int 타입의 배열을 1,000,005 크기만큼 만든다.
- 이렇게 배열을 만드는 이유는 사탕상자에 들어간 사탕의 개수를 O(1) 빠르기로 접근가능하기 때문이다.
- priority queue를 사용하여 어떤 맛의 사탕이 상자안에 들어가있는지 저장한다.
- priority queue를 사용하는 이유는 정렬을 알아서 해주기 때문에 사용했다.
- 상자에 사탕을 추가할 때는 int 배열에 접근하여 사탕의 개수가 0일 때만 priority queue에 사탕 맛을 추가한다.
- int 배열에는 항상 들어온 입력만큼 개수를 업데이트해준다.
- 상자에서 사탕을 뺄 때는 입력받은 2번 숫자를 0 이하가 되게끔 만들어준다.
- 0 이하로 만드는 과정은 priority queue에서 숫자를 하나 꺼내서, 그 숫자로 int 타입 배열에 접근한 후 그 수를 2번 숫자에 뺀다.
- 0 이하로 만들어준 priority queue에서 나온 숫자를 출력해준다.
이런식으로 구현하는 것이었다.코드 없이 설명하는게 너무 어렵다..
하지만 그 결과로는...
제출 현황(실패)
이와 같이 메모리 초과가 났다.
int배열 크기가 백만이니깐 메모리 크기 4,000,000B, 넉넉하게 4MB였기에 priority queue에서 메모리 초과가 난다는 것을 2번이나 더 시도해보고 깨달았다..
그렇기에 위에서 사용한 priotiry queue를 사용하는 대신 그냥 int배열을 사용하기로 결정했다.
- int타입 배열 100,000 크기만큼 만들고
- 배열에서 사탕상자 안에 들어간 사탕 맛의 개수만큼만 사용할거기에 개수를 저장하고 있는 변수 하나를 만든다.
- 사탕상자에 사탕을 넣을 때마다 사탕 맛의 개수까지 정렬을 진행해준다.
- 사탕을 꺼내는 과정은 priority queue와 비슷하게 진행해주면 된다.
풀이코드
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
public class Main {
public static void main(String[] args) throws NumberFormatException, IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
// arr은 사탕 개수를 저장하는 배열, tastes는 사탕 맛을 저장하는 배열이다.
int[] arr = new int[1000005], tastes = new int[100005];
// tastes 배열을 높은 수로 채워둔다. (정렬을 편하게 하기 위해서)
Arrays.fill(tastes, Integer.MAX_VALUE);
// index는 사탕 맛의 개수를 저장하는 변수이다.
int n = Integer.parseInt(br.readLine()), index = 0;
for(int a = 0; a < n; a++)
{
String[] input = br.readLine().split(" ");
// 사탕을 꺼낼 때
if(input[0].equals("1"))
{
int cnt = Integer.parseInt(input[1]);
// find는 사탕 맛을 찾고 저장하는 변수이다.
int find = 0;
while(cnt > 0)
{
cnt -= arr[tastes[find++]];
}
find--;
bw.write(tastes[find] + "\n");
// 사탕 개수를 하나 줄인다.
arr[tastes[find]]--;
// 사탕 개수가 0이라면
if(arr[tastes[find]] == 0)
{
// 사탕 개수를 높은 수로 저장한다.(이 과정은 사탕 맛의 개수를 줄이는 과정과 같다. 정렬하면 자연스레 뒤로 밀리기 때문)
tastes[find] = Integer.MAX_VALUE;
// 부분 정렬 후 맛의 개수를 하나 줄인다.
Arrays.sort(tastes, 0, index--);
}
}
// 사탕을 넣을 때
else
{
int taste = Integer.parseInt(input[1]);
// 입력받은 맛이 상자안에 없다면
if(arr[taste] == 0)
{
// 맛을 저장하는 배열에 맛을 추가한다.
tastes[index++] = taste;
}
// 맛의 개수 배열에 입력받은 개수를 더한다.
arr[taste] += Integer.parseInt(input[2]);
// 맛의 개수만큼 부분 정렬을 한다.
Arrays.sort(tastes, 0, index);
}
}
bw.flush();
}
}
제출 화면
오늘은 내가 평소 틀리는 유형인 "틀렸습니다", "시간 초과"가 아닌 "메모리 초과"가 나와서 뇌가 조금 고장났던 것 같다.
그래도 잘 풀어낸 것 같아서 다행이다!
'백준 문제 풀이' 카테고리의 다른 글
| [BOJ / 백준] 백준 1043번 문제를 풀어보았다. (ft. Java) (0) | 2021.07.26 |
|---|---|
| [BOJ / 백준] 백준 1987번 문제를 풀어보았다. (ft. Java) (0) | 2021.07.24 |
| [BOJ / 백준] 백준 2578번 문제를 풀어보았다. (ft. Java) (0) | 2021.07.21 |
| [BOJ / 백준] 백준 15904번 문제를 풀어보았다. (ft. Java) (0) | 2021.07.16 |
| [BOJ / 백준] 백준 1103번 문제를 풀어보았다. (ft. Java) (0) | 2021.07.16 |