[백준] 회전초밥 2531번 (🥈실버1)
사이트
https://www.acmicpc.net/problem/2531
문제
분석
서론
음 뭔가 문제 이해가 어려웠지 풀이는 너무 쉬웠다... 이게 실버1이라고 그리고 정답률이 37퍼라고???
그래서 한번보자
이해
이해가 가지 않았던 문제이다.
위 사진 처럼 벨트가 저렇게 돌아가는데
어떻게 순서가 이렇게 나오지 곰곰히 생각을 해봤다.
순서가 반대로 되야되는거 아닌가.... (2 30 7 9) (9 7 2 30) (25 9 7 2) 이렇게 되어야 되는게 아닌가...
일단은 뭐 풀어보니깐 순서는 중요하지가 않다.
다음은 쿠폰이다!! 만약 30번 쿠폰이 주어졌을시 연속으로 4개를 먹을때!! 즉 띄엄띄엄 먹지말고 연속으로 4개다!!
그걸 먹을때 30번 초밥을 무료로 준다는 것이다. 참고로 30번 쿠폰이 입력에 없을때는 요리사가 새로 만든다고 한다.
즉 쿠폰을 이용하여 최대 초밥을 먹을 수 있는 종류를 구하는 문제이다.
8 30 4 30
7
9
7
30
2
7
9
25
입력은 이렇게 이다. 맨위에서 8은 접시, 30은 초밥 종류(즉 초밥 번호), 4는 연속 접시 갯수, 30은 쿠폰 번호이다.
두번째 줄 부터 쭉 접시의 갯수 즉 8개의 갯수대로 초밥의 종류를 30이하까지 담아주면 된다.
풀이1
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
n = Integer.parseInt(st.nextToken());
d = Integer.parseInt(st.nextToken());
k = Integer.parseInt(st.nextToken());
c = Integer.parseInt(st.nextToken());
for (int i = 0; i < n; i++) {
list.add(Integer.parseInt(br.readLine()));
}
solution();
System.out.println(max);
}
여기는 입력부분이다. 문제 분류가 슬라이딩 윈도우라서 문제에 맞게 list로 초밥의 종류를 받았다. (동적으로 뺴줄려고)
private static void solution() {
boolean[] visit = new boolean[d + 1];
int cnt = 0;
int start;
for (int i = 0; i < n; i++) {
start = list.get(0);
for (int j = 0; j < k; j++) {
if (!visit[list.get(j)]) {
visit[list.get(j)] = true;
cnt++;
}
}
if (!visit[c]) {
cnt++;
}
visit = new boolean[d + 1];
list.remove(0);
list.add(start);
max = Math.max(cnt, max);
cnt = 0;
}
}
여기가 핵심 코드이다. 차근차근 보자
boolean[] visit = new boolean[d + 1];
int cnt = 0;
int start;
일단 그래프와 비슷하게 visit 불린 배열을 선언하였다. 왜냐하면 초밥의 종류를 확인하기 위해서이다.
cnt는 초밥의 종류 갯수
start는 앞에 초밥을 제거하기 위해 넣었다 왜냐하면 회전 초밥이므로 회전하기 때문이다.
for (int i = 0; i < n; i++) {
start = list.get(0);
for (int j = 0; j < k; j++) {
if (!visit[list.get(j)]) {
visit[list.get(j)] = true;
cnt++;
}
}
if (!visit[c]) {
cnt++;
}
visit = new boolean[d + 1];
list.remove(0);
list.add(start);
max = Math.max(cnt, max);
cnt = 0;
}
이게 for 문 전체이다 차근차근 보자
for (int i = 0; i < n; i++) {
start = list.get(0);
for (int j = 0; j < k; j++) {
if (!visit[list.get(j)]) {
visit[list.get(j)] = true;
cnt++;
}
}
일단 연속된 그릇이 4개이고 전체를 4개씩 끊어서 다 돌아야 되므로 경우의 수는 n이다!
그래서 첫번째 for문을 위와 같이 설정해두었다.
그 후 list의 첫번째 요소를 start에 넣는다.
두 번째 for문은 연속된 그릇의 초밥의 종류를 돈다.
if문에 와서 만약 그 초밥이 false이면 즉 처음 담으면 해당 초밥은 true로 바뀌고 cnt가 증가한다.
만약 초밥이 true면 cnt가 증가하지 못하는 것이다.
if (!visit[c]) {
cnt++;
}
두번째 for문이 끝났으면 쿠폰 초밥도 visit 유무 검사를 하고 cnt를 증/감 시킬지 결정한다.
visit = new boolean[d + 1];
list.remove(0);
list.add(start);
max = Math.max(cnt, max);
cnt = 0;
그 다음 visit 배열을 초기화 시켜주고 list의 첫번째 요소를 제거 시키고 이전에 start를 설정해두어 list에 추가시켜준뒤
Math.max를 통해 비교를 하고 cnt는 다시 0으로 초기화 시켜주어야 된다. 왜냐하면 계속 비교할거깐
이렇게 해서 1세트는 끝이다!! 위 입력되로 할려면 8세트까지 비교해야된다.
이렇게 해서 제출을 했지만 솔직히 시간초과가 뜰줄 알았다. 왜냐하면 N 이 30000개 이하까지 허용되고 k도 3000이니깐
최악의 경우의 수일때 시간복잡도가 ㄷㄷ 해진다...
근데....
신긴한게 맞았다.... 그리고 980ms가 떴다.... 맞았지만 시원하지가 않았다. 다른 사람들꺼는 200이하가 많던데...
그래서 다른 방법으로 풀어보았다!!
풀이2
본 문제의 핵심 분야를 잘 못짚은거 같다.
투포인터 및 슬라이딩 윈도우 분야인데.....
public class Bra2531 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int n = Integer.parseInt(st.nextToken());
int d = Integer.parseInt(st.nextToken());
int k = Integer.parseInt(st.nextToken());
int c = Integer.parseInt(st.nextToken())-1;
int [] eat=new int[d];
int [] my_eat=new int[n];
for(int i=0; i<n; i++){
my_eat[i]=Integer.parseInt(br.readLine())-1;
}
int cnt=0;
int res=0;
for(int i=0; i<k; i++){
if(eat[my_eat[i]] ++ ==0){
cnt++;
}
}
for(int i=0; i<n; i++){
if(res<=cnt){
if(eat[c]==0){
res=cnt+1;
}
else{
res=cnt;
}
}
int j=(i+k)%n;
if(eat[my_eat[j]]++ ==0){
cnt++;
}
if(--eat[my_eat[i]] ==0){
cnt--;
}
}
System.out.println(res);
}
}
그래서 위와 같이 리펙토링 해서 실행을 해봤다!!!
코드 설명은 생략! 간단하니깐
전체코드1
package bra;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;
public class Bra2531 {
static int n;
static int d;
static int k;
static int c;
static int[] food;
static List<Integer> list = new ArrayList<>();
static int max = 0;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
n = Integer.parseInt(st.nextToken());
d = Integer.parseInt(st.nextToken());
k = Integer.parseInt(st.nextToken());
c = Integer.parseInt(st.nextToken());
food = new int[n];
for (int i = 0; i < n; i++) {
food[i] = Integer.parseInt(br.readLine());
list.add(food[i]);
}
solution();
System.out.println(max);
}
private static void solution() {
boolean[] visit = new boolean[d+1];
int cnt = 0;
int start;
for (int i = 0; i < n; i++) {
start = list.get(0);
for (int j = 0; j < k; j++) {
if (!visit[list.get(j)]) {
visit[list.get(j)] = true;
cnt++;
}
}
if (!visit[c]) {
cnt++;
}
visit = new boolean[d + 1];
list.remove(0);
list.add(start);
max = Math.max(cnt, max);
cnt=0;
}
}
}
전체코드2
public class Bra2531 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int n = Integer.parseInt(st.nextToken());
int d = Integer.parseInt(st.nextToken());
int k = Integer.parseInt(st.nextToken());
int c = Integer.parseInt(st.nextToken())-1;
int [] eat=new int[d];
int [] my_eat=new int[n];
for(int i=0; i<n; i++){
my_eat[i]=Integer.parseInt(br.readLine())-1;
}
int cnt=0;
int res=0;
for(int i=0; i<k; i++){
if(eat[my_eat[i]] ++ ==0){
cnt++;
}
}
for(int i=0; i<n; i++){
if(res<=cnt){
if(eat[c]==0){
res=cnt+1;
}
else{
res=cnt;
}
}
int j=(i+k)%n;
if(eat[my_eat[j]]++ ==0){
cnt++;
}
if(--eat[my_eat[i]] ==0){
cnt--;
}
}
System.out.println(res);
}
}결과
느낀점
너무 어려웠다... 리펙토링 하는게... 열심히 노력해보자.
추가로 리펙토링된 코드가 뭔가 고급스러운 느낌이 난다 아직 멀었따...