[백준/Java, Kotlin] 2531번 회전 초밥

 

 

문제 풀이(Java만 설명)

• 첫번째 풀이(시간 968ms, 메모리 299988KB)

ArrayList<Integer> bob = new ArrayList<>();

int N = sc.nextInt(); //접시의 수
int d = sc.nextInt(); //초밥의 가짓수
int k = sc.nextInt(); //연속해서 먹는 접시의 수
int c = sc.nextInt(); //쿠폰 번호
int result = 0;

//배열리스트에 회전 초밥 벨트에 놓인 접시 번호 추가하기
for(int i=0; i<N; i++) {
    bob.add(sc.nextInt());
}

1. 문제에서 주어진 입력을 받고, 회전 초밥 벨트에 놓인 접시 N개를 bob이라는 arrayList에 추가한다.

 

//(1)
for(int i=0; i<N; i++) {
    int[] count = new int[d+1];
    int bobCount = 0;

    //(2)벨트에 초밥이 있다면 +1
    for(int j=0; j<k; j++) {
        count[bob.get((i+j) % N)]++;
    }

    //(3)초밥 쿠폰
    count[c]++;

    //(4)만약 0이 아니라면 초밥이 있는 것이므로 카운트 증가
    for(int a=1; a<=d; a++) {
        if(count[a] != 0) {
            bobCount++;
        }
    }

    //(5)최댓값 비교
    result = Math.max(result, bobCount);
}
//출력
System.out.println(result);

2. (1), (2) 총 N번 만큼 반복할 것이고, 회전 초밥의 개수 + 1의 크기를 가진 정수 배열(count)를 생성한다.

그리고 연속해서 먹는 접시의 수(k)만큼 반복하며, 현재 회전 초밥의 수에 해당하는 count의 인덱스에 1을 증가시킨다.

 

N=0일 때, (7 9 7 30)

count 배열은

0 0 0 0 0 0 0 2 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 이다.

 

(3) 그리고 초밥 쿠폰을 사용해주기 위해 count 배열에서 인덱스 c에 1을 증가시킨다.

 

(4) 1부터 초밥의 가짓수(d)까지 반복하면서 해당하는 값이 0이 아니라면 현재 먹을 수 있는 초밥이므로 카운트를 증가시킨다.

 

(5) 최대값이 담겨있는 result와 현재 먹을 수 있는 초밥의 최댓값을 비교한다.

 

 

이렇게 코드를 짰을 때, 오류 없이 돌아가긴 했지만 시간과 메모리가 너무 높다고 생각해서 다른 풀이를 참고해서 풀어봤다.

 

 

• 두번째 풀이(시간 348ms, 메모리 42336KB)

Scanner sc = new Scanner(System.in);

int N = sc.nextInt(); //접시의 수
int d = sc.nextInt(); //초밥의 가짓수
int k = sc.nextInt(); //연속해서 먹는 접시의 수
int c = sc.nextInt(); //쿠폰 번호

int[] sushiBelt = new int[N];
int[] sushi = new int[d+1];
int count = 0;
int max = 0;

//배열리스트에 회전 초밥 벨트에 놓인 접시 번호 추가하기
for(int i=0; i<N; i++) {
    sushiBelt[i] = sc.nextInt();
}

1. 문제에서 주어진 입력을 받는다.

회전 초밥 벨트에 놓인 접시 번호를 정수 배열인 sushiBelt에 입력 받는다.

 

//최초 접시 k개에 대해 체크
for(int j=0; j<k; j++) {
    if(sushi[sushiBelt[j]] == 0) {
        count++;
    }
    sushi[sushiBelt[j]]++;
}
max = count;

2. 회전하기 전 최초 접시 k개에 대해 몇 접시를 먹을 수 있을지 확인한다.

 

문제에 주어진 예제에 따르면 처음 k개의 접시는

7 9 7 30 이다.

그러므로 count와 max 에는 각각 3이 대입된다.

배열 sushi를 출력하면

0 0 0 0 0 0 0 2 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 와 같다.

 

for(int n=0; n<N; n++) {
    //count의 값이 커졌다는 것은 초밥의 종류가 변경되었다는 것.
    //쿠폰 접시가 빠진거라면 count에 추가해줘야함.
    if(count >= max) {
        if(sushi[c] == 0) {
            max = count+1;
        }else {
            max = count;
        }
    }

    //k개의 접시 중 첫번째 접시 빼기
    sushi[sushiBelt[n]]--;
    if(sushi[sushiBelt[n]] == 0) count--;

    //하나 뺏으니까 접시 하나 넣기
    if(sushi[sushiBelt[(n + k) % N]] == 0) count++;
    sushi[sushiBelt[(n + k) % N]]++;
}
//출력
System.out.println(max);

3. 투포인터를 사용하여 문제를 푼다.

 

N번 반복하며, 만약 count의 값이 max 값보다 커졌을 경우, 초밥의 종류가 변경되었다는 뜻이기 때문에 초밥 쿠폰으로 초밥을 더 먹을 수 있는지 확인해야한다.

 

확인이 끝났다면 투포인터를 사용해서 k개의 접시 중 첫번째 접시를 제거한다.

제거했을 때, sushi 배열에 제거한 초밥이 0이라면 count에서 1을 빼주고, 0이 아니라면 아직 해당 번호의 초밥이 있다는 뜻이므로 냅둔다.

 

접시 하나를 뺐으니 다음 접시를 추가해줘야한다.

일단 추가하는 접시가 연속해서 먹는 접시의에 포함되어있지 않다면 count를 1 증가시켜주고, sushi 배열에서도 해당 번호의 값을 1 증가 시킨다.

 

 

투포인터를 사용하니 시간과 메모리가 현저하게 줄었고, 투포인터에 대해 제대로 알지 못 했었는데 이 문제를 통해서 투포인터에 대해 잘 알게 됐다.

 

 

 

코드

• Java 첫번째 코드

import java.util.ArrayList;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		ArrayList<Integer> bob = new ArrayList<>();
		
		int N = sc.nextInt(); //접시의 수
		int d = sc.nextInt(); //초밥의 가짓수
		int k = sc.nextInt(); //연속해서 먹는 접시의 수
		int c = sc.nextInt(); //쿠폰 번호
		int result = 0;
		
		//배열리스트에 회전 초밥 벨트에 놓인 접시 번호 추가하기
		for(int i=0; i<N; i++) {
			bob.add(sc.nextInt());
		}
		
		
		for(int i=0; i<N; i++) {
			int[] count = new int[d+1];
			int bobCount = 0;
			
			//벨트에 초밥이 있다면 +1
			for(int j=0; j<k; j++) {
				count[bob.get((i+j) % N)]++;
			}
			
			//초밥 쿠폰
			count[c]++;
			
			//만약 0이 아니라면 초밥이 있는 것이므로 카운트 증가
			for(int a=1; a<=d; a++) {
				if(count[a] != 0) {
					bobCount++;
				}
			}
			//최댓값 비교
			result = Math.max(result, bobCount);
		}
		//출력
		System.out.println(result);
	}
}

 

 

• Java 두번째 코드(추천 ⭐)

import java.util.Arrays;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int N = sc.nextInt(); //접시의 수
		int d = sc.nextInt(); //초밥의 가짓수
		int k = sc.nextInt(); //연속해서 먹는 접시의 수
		int c = sc.nextInt(); //쿠폰 번호
		
		int[] sushiBelt = new int[N];
		int[] sushi = new int[d+1];
		int count = 0;
		int max = 0;
		
		//배열리스트에 회전 초밥 벨트에 놓인 접시 번호 추가하기
		for(int i=0; i<N; i++) {
			sushiBelt[i] = sc.nextInt();
		}
		
		//처음 최소 접시 k개에 대해 체크
		for(int j=0; j<k; j++) {
			if(sushi[sushiBelt[j]] == 0) {
				count++;
			}
			sushi[sushiBelt[j]]++;
		}
		max = count;
		
		
		for(int n=0; n<N; n++) {
			//count의 값이 커졌다는 것은 초밥의 종류가 변경되었다는 것.
			//쿠폰 접시가 빠진거라면 count에 추가해줘야함.
			if(count >= max) {
				if(sushi[c] == 0) {
					max = count+1;
				}else {
					max = count;
				}
			}
			
			//k개의 접시 중 첫번째 접시 빼기
			sushi[sushiBelt[n]]--;
			if(sushi[sushiBelt[n]] == 0) count--;
			
			//하나 뺏으니까 접시 하나 넣기
			if(sushi[sushiBelt[(n + k) % N]] == 0) count++;
			sushi[sushiBelt[(n + k) % N]]++;
		}
		//출력
		System.out.println(max);
	}
}

 

 

• Kotlin 첫번째 코드

fun main(){
    var(N, d, k, c) = readln().split(" ").map { it.toInt() }
    var list = mutableListOf<Int>()
    var result = 0

    repeat(N){
        list.add(readln().toInt())
    }

    for(i in 0 until N){
        var count = MutableList(d+1){0}
        var bobCount = 0

        for(j in 0 until k){
            count[list[(i+j) % N]]++
        }
        count[c]++

        for(a in 1..d){
            if(count[a] != 0){
                bobCount++
            }
        }
        result = maxOf(result, bobCount)

    }

    println(result)
}

 

 

• Kotlin 두번째 코드 (추천 ⭐)

fun main(){
    var(N, d, k, c) = readln().split(" ").map { it.toInt() }
    var sushiBelt = MutableList(N){0}
    var sushi = MutableList(d + 1){0}

    var cnt = 0

    for(i in 0 until N){
        sushiBelt[i] = readln().toInt()
    }

    //최초의 k개의 벨트에 대해서 접시 확인
    for(j in 0 until k){
        if(sushi[sushiBelt[j]] == 0) cnt++
        sushi[sushiBelt[j]]++
    }
    var max = cnt

    for(n in 0 until N){
        if(max <= cnt){
            if(sushi[c] == 0){
                max = cnt+1
            }else{
                max = cnt
            }
        }

        //첫번째 접시 빼기
        sushi[sushiBelt[n]]--
        if(sushi[sushiBelt[n]] == 0) cnt--

        //접시 추가하기
        if(sushi[sushiBelt[(n + k) % N]] == 0) cnt++
        sushi[sushiBelt[(n + k) % N]]++
    }
    println(max)
}

 

 

 

https://www.acmicpc.net/problem/2531