2021년 9월 29일 수요일 - 여러분 21학점은 듣는게 아닌 것 같습니다...
오늘 올려볼 문제는 2531번 회전초밥 이라는 문제이다.
사진을 클릭하면 해당 문제로 이동합니다.
오늘은 음식이 나오는 알고리즘 문제를 가져왔다.
진짜 학교 생활 너무 힘들어서 엄청 오랜만에 블로그 쓴다..
입력 예제
첫번째 줄에 접시의 개수(n), 초밥 종류의 개수(d), 선택하려는 접시의 개수(k), 쿠폰 숫자(c)가 공백으로 구분되어 입력된다.
그 다음 n 줄에 초밥의 종류가 입력으로 들어온다.
풀이 및 코드
일단 회전 초밥은 배열의 끝과 끝이 이어져있는 경우라고도 볼 수 있다.
그렇기에 나는 크기가 접시의 개수(n)의 2배인 배열을 만들고 같은 내용을 이어서 저장하고 사용하기로 했다.
이렇게 배열을 크게 만드는 이유는 배열에 끝에 대한 처리를 편하게 하기 위함이다. 또한 선택하려는 접시의 개수(k)는 n보다 작기 때문에 2배만 하였다.
또한 중복에 대한 처리를 해줘야 하므로 현재 선택한 접시들의 개수를 저장하는 배열을 선언하여 사용한다.
어느정도 설명이 필요한 전제는 이정도이고 이제 코드를 봐보자!
풀이코드
import java.io.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
String[] input_nums = br.readLine().split(" ");
int n = Integer.parseInt(input_nums[0]), d = Integer.parseInt(input_nums[1]),
k = Integer.parseInt(input_nums[2]), c = Integer.parseInt(input_nums[3]);
// 선택한 각 초밥의 종류의 개수를 저장하는 배열(nums), 회전 초밥의 순서를 저장하는 배열(arr)
int[] nums = new int[3005], arr = new int[n * 2];
// result는 출력할 결과, diff는 각 선택한 접시의 다양성
int result = 0, diff = 0;
// 입력받기 이 때 n번째 인덱스부터 이어서 저장해주는 과정도 같이 해준다.
for(int i = 0; i < n; i++)
{
arr[i] = arr[n + i] = Integer.parseInt(br.readLine());
}
// 접시를 처음 선택하는 과정
for(int i = 0; i < k; i++)
{
// 선택하려는 초밥이 선택되지 않았다면 다양성에 1을 더함
if(nums[arr[i]]++ == 0)
{
diff++;
}
}
// 결과 초기화
result = diff;
for(int i = 0; i < n; i++)
{
// 선택한 접시중 왼쪽 접시를 뺀다
// 이때 빼고 난 후에 초밥 개수가 0이라면 다양성에 1을 뺀다.
if(--nums[arr[i]] == 0)
diff--;
// 선택한 접시중 오른쪽 접시를 더한다.
// 이때 더할 초밥 개수가 0이라면 다양성에 1을 더한다.
if(nums[arr[i + k]]++ == 0)
diff++;
// 만약 다양성이 결과보다 크다면
if(diff > result)
{
// 결과에 다양성에 대입한다.
result = diff;
}
// 쿠폰에 해당하는 초밥 개수가 0이고 결과와 다양성이 같다면
if(nums[c] == 0 && diff == result)
{
// 결과에 1을 더해준다.
result++;
}
}
bw.write(result + "\n");
bw.flush();
}
}
제출 화면
오늘은 재밌는 문제를 풀기도 했고 한동안 너무 블로그에 글을 안올려서 죄책감에 올렸다....
이 글이 도움이 되는 사람이 있기를!
'백준 문제 풀이' 카테고리의 다른 글
| [BOJ / 백준] 백준 3151번 문제를 풀어보았다. (ft. Java) (1) | 2021.09.04 |
|---|---|
| [BOJ / 백준] 백준 1120번 문제를 풀어보았다. (ft. Java) (0) | 2021.08.30 |
| [BOJ / 백준] 백준 11399번 문제를 풀어보았다. (ft. Java) (0) | 2021.08.29 |
| [BOJ / 백준] 백준 2294번 문제를 풀어보았다. (ft. Java) (0) | 2021.08.21 |
| [BOJ / 백준] 백준 2799번 문제를 풀어보았다. (ft. Java) (0) | 2021.08.14 |