문제
풀이 과정
- 먼저, 실패한 코드
#include <stdio.h>
#define MAX 101
int n,k;
int check[MAX];
int main() {
scanf("%d %d", &n, &k);
for (int i=0; i<k; i++) {
scanf("%d", &check[i]);
}
int multi[n];
int cnt = 0;
int result = 0;
for (int i=0; i<k; i++) {
if (cnt < n) {
int flag = 0;
for (int j=0; j<cnt; j++) {
if (multi[j] == check[i]) {
flag = 1;
}
}
if (flag == 0) {
multi[cnt++] = check[i];
}
} else {
int flag = 0;
for (int j=0; j<n; j++) {
if (multi[j] == check[i]) {
flag = 1;
}
}
if (flag == 0) {
multi[n-1] = check[i];
result++;
}
}
}
printf("%d", result);
return 0;
}- check를 순환하면서
- multi 배열이 n이 아니고(꽂을 곳이 있고), multi 배열에 check[i]와 같은 값이 없다면 multi 배열에 check 배열의 값을 넣음
- multi 배열이 꽂을 곳이 없고, multi 배열에 check[i]와 같은 값이 없다면 multi 배열의 마지막을 check[i]값으로 변경하고 카운팅
- 그러면 내 예상은
2, 7
Check 2 3 2 3 1 2 7
Multi 0 0 일 때,
Multi 2 0
Multi 2 3
2, 3 은 Multi 배열에 이미 있기 때문에 패스
Multi 2 1, result++
2는 있기 때문에 패스
Multi 2 7, result++
result = 2- 이런 방식을 생각했다
- 하지만 이 코드엔 간과한 점이 있었으니(ㅠㅠ)
- 그건 바로 플러그 교체할 때 또 사용되는 건지 아니면 사용이 안되는건지 확인하는 로직이 빠져 버렸다
- 예를 들어 보자
Check 2 3 2 3 1 3 3
Multi 0 0 일 때,
Multi 2 0
Multi 2 3
2, 3 은 Multi 배열에 이미 있기 때문에 패스
Multi 2 1, result++
Multi 2 3, result++
3 은 Multi 배열에 이미 있기 때문에 패스
result = 2 인데
사실상 최소값은,
Multi 2 0
Multi 2 3
2, 3 은 Multi 배열에 이미 있기 때문에 패스
Multi 1 3, result++
3, 3 은 Multi 배열에 이미 있기 때문에 패스
result = 1 이여야 함- 그렇다면 그 뒤에 나오는 애들의 빈도수를 확인하고 넣어야 하나?
- 멀티탭은 순서대로 넣어야 하기 때문에, 빈도수 확인은 필요가 없다
- multi 배열에 있는 값이 check 배열에 있는 값에서 얼마나 가까운 곳에 있는지 확인하면 된다
- 예를 들어 보자
Check 2 3 4 2 5 3 6
Multi 0 0 일 때,
Multi 2 0
Multi 2 3
Check 4 2 5 3 6
Multi 2 3
이제 4를 넣어야 하는데, 멀티탭은 꽉 찼다.
그럼 Mutl에서 어떤 값을 지우고 4를 넣어야 할까?
1. 더이상 사용되지 않는 값이 있으면, 그 값으로 교체
2. 없다면, 가장 빨리 사용될 값으로 교체 (오래 유지 하는게 핵심이기 때문)
그럼 각각의 값을 살펴보자
Multi 2 3
3 은 Check[5] 에서 다시 사용
2 는 Check[3] 에서 다시 사용
그렇다면? 3이 더 늦게 사용되므로 2를 교체해준다
Check 2 5 3 6
Multi 4 3
4가 존재하지 않으니 4를 교체
Check 5 3 6
Multi 2 3
2가 존재하지 않으니 2를 교체
3 패스
Check 6
Multi 5 3
둘 다 존재 하지 않으니 아무거나 교체정답 코드
#include <stdio.h>
#define MAX 101
int n,k;
int check[MAX];
int main() {
scanf("%d %d", &n, &k);
for (int i=0; i<k; i++) {
scanf("%d", &check[i]);
}
int multi[n];
int cnt = 0;
int result = 0;
for (int i=0; i<k; i++) {
int cur = check[i];
int flag = 0;
for (int j=0; j<cnt; j++) {
if (multi[j] == cur) {
flag = 1;
break;
}
}
if (flag == 1) continue;
if (cnt < n) {
multi[cnt++] = cur;
continue;
}
int last_idx = -1;
int farthest = -1;
for (int a=0; a<n; a++) {
int next_use = 0;
for (int b=i+1; b<k; b++) {
if (multi[a] == check[b]) {
next_use = b;
break;
}
}
if (next_use == 0) {
last_idx = a;
break;
}
if (next_use > farthest) {
farthest = next_use;
last_idx = a;
}
}
multi[last_idx] = cur;
result++;
}
printf("%d", result);
return 0;
}
Embedded Software Engineer