[C언어] 2531. 회전 초밥

전체 배열에서 k개의 연속된 부분 배열을 선택하였을 경우, 부분 배열안에 다른 값들의 종류가 최대가 되는 개수를 출력하는 문제이다.

 

그리고 쿠폰을 사용하여 정해진 번호의 초밥을 추가로 먹을 수 있으며 이 초밥이 기존에 먹지 않았을 경우 종류가 다른 초밥으로 인정되어 최대 값에 +1이 된다.

 

풀이

문제에서 주어진 테스트 케이스로 설명을 해보겠다.

벨트에 놓인 초밥의 수 : 8

초밥의 종류 : 30

연속해서 먹는 접시의 수 : 4

사용 가능한 쿠폰의 번호 :30

 

입력된 n개의 초밥의 정보 : 7 9 7 30 2 7 9 25

 

처음 입력된 7을 기준으로 연속해서 4개씩 먹어보겠다.

 

7 9 7 30 -> 먹은 초밥의 종류 :  3

9 7 30 2 -> 먹은 초밥의 종류 :  4

7 30 2 7 -> 먹은 초밥의 종류 :  3

30 2 7 9 -> 먹은 초밥의 종류 :  4

2 7 9 25 -> 먹은 초밥의 종류 :  4 + 1

 

회전 초밥이니 마지막 초밥은 처음 초밥과 이어지므로

7 9 25 7 -> 먹은 초밥의 종류 :  3 + 1

9 25 7 9 -> 먹은 초밥의 종류 :  3 + 1

25 7 9 7 -> 먹은 초밥의 종류 :  3 + 1

 

위의 규칙을 보면 k개의 단위로 결과값을 얻는다. 그리고 초밥의 먹은 초밥의 종류를 카운트하는 별도의 배열을 사용하면 k개 안에 초밥의 종류가 몇 가지 있는지 카운트가 가능하다.

 

예로 7 9 7 30을 해보면

초밥 7번을 먹으면 먹은 초밥의 종류를 카운트하는 배열은 0에서 1로 증가시킨다. 이 경우 기존에 먹지 않은 종류의 초밥을 먹은거니 먹은 새로운 초밥을 카운트 하는 변수에 +1을 해준다. 이렇게 해주면

7번 인덱스는 2

9번 인덱스는 1

30번 인덱스는 1이다.

 

이렇게 검사를 해주면 새로운 부분 배열 9 7 30 2를 체크해주어야 한다. 이 경우 첫 7을 제외하고 새로운 2을 넣어주야한다.

제외하는 방법은 종류 카운트 배열에서 7번을 -1 해주면 된다. 그리고 2번을 +1해주면 된다. 그리고 중요한건 먹은 종류를 카운트 배열이 1에서 0이 된거면 새로운 종류의 초밥이 k개 안에 속하지 않은 것이기 때문에 새로운 초밥을 카운트 하는 변수를 -1해주면 된다.

 

추가로 쿠폰으로 기존에 먹지 않은 종류의 초밥을 먹었을 경우가 최대 값이므로 처음 시작할 때 새로운 초밥을 먹고 시작하도록 하자!!!

 

정답 코드

http://colorscripter.com/s/HdczG4s