난이도 : Silver1
Link : https://www.acmicpc.net/problem/1713
Tag : 구현, 시뮬레이션
풀이일자 : 2024년 8월 27일
📌 문제 탐색하기
N : 사진 틀의 갯수
둘쨋 줄 : 전체 학생의 총 추천 횟수
셋째 줄 : 추천을 받은 학생
이 문제는 셋째 줄에 추천을 받은 학생을 사진 틀의 갯수에 맞게 사진을 등록하는 문제이다.
여기서 중요하게 생각할 것은
1. 학생을 추천하면 반드시 사진틀에 게시되어야 한다.
2. 비어있는 사진 틀이 없다면 추천 받은 횟수가 가장 적은 학생을 삭제 삭제된 학생의 추천수는 0으로 만든다.
3. 만일 추천 받은 횟수가 겹칠 경우에는 가장 오래전에 등록된 사진을 삭제 해야한다.
가능한 시간복잡도
사진 틀의 갯수는 1~20 가지 이며 총 추천 횟수는 1000번 이하 이고, 학생을 나타내는 번호는 1~ 100이므로
모든 학생들이 다 등장하고 추천을 진행 한다고 해도 탐색 할 수 있는 횟수는 1000 * 100 정도로 충분히 탐색 가능한 시간복잡도를 가진다.
📌 문제 접근 방법
-
사진이 걸려있는지, 그 사진이 몇개의 추천 횟수를 가지고 있는지를 알아야 하기 때문에 사진이 걸려있는 배열과 사진의 추천 횟수를 가지고 있는 배열을 만들고자 하였다
picture [] : 걸려있는 사진 배열
pic_cnt : 걸려있는 사진의 추천 횟수 배열 -
추천 횟수가 같을때 가장 처음에 등록된 사진을 제거해야하기 때문에 등록 순서를 저장할 배열을 만들고자 하였다.
last_pic [] : 최근 등록된 사진
-
vote_list 추천을 받을때 마다 picture을 탐색하여 빈 공간이 있을때와 빈공간이 없을때로 구분해서 탐색한다.
-
빈자리가 있을때는 picture 배열에 추가하고, last_pic에 등록한 기록을 저장한다.
-
빈자리가 없을때는 추천수가 같을때, 추천수가 같지 않을때로 구분하여 없앨 사진을 last_pic을 통해 정하고 그 자리에 추천된 사진을 넣으면 될 것이다.
-
문제에서 요구하는 답안은 오름차순으로 학생들의 번호를 출력하는 것이므로 picture에 있는 학생들의 번호를 정렬하여 출력하면 될것이다.
📌 코드 설계하기
-
n을 입력받는다.
-
vote 에 추천 횟수 vote_list에 추천 리스트를 입력받는다.
-
탐색을 위한 배열을 추가한다.
- last_pic[] : 최근 등록된 사진을 저장할 배열
- picture[] : 걸려있는 사진을 저장할 배열
- pic_cnt[] : 걸려있는 사진의 추천 횟수를 저장할 배열
-
vote_list를 반복하여 picture 안에서 탐색을 진행한다.
- 이미 등록된 사진이 추천되었을 때
1. 이미 등록된 사진의 인덱스의 추천횟수 pic_cnt를 증가시킨다. - 빈자리가 있을 때
1. picture[i] == 0 인곳에 사진을 등록하고 다음 vote_list로 넘어간다.
2. 등록한 사진을 last_pic에 추가한다. - 빈자리가 없을때
1. 추천 횟수가 겹칠 때
- 2개 이상이라면
last_pic에서 가장 처음에 등록된 사진을 제거한다.
- 추천 횟수가 겹치지 않을 때
가장 작은 추천 횟수인 인덱스의 picture을 제거하고 새롭게 추천받은 사진을 추가한다.
- 이미 등록된 사진이 추천되었을 때
-
picture을 sort하여 오름차순으로 정렬한다.
-
picture에 0이 아닌 수를 한칸 띄어서 출력한다.
📌 시도 회차 수정 사항
1. 틀렸습니다(10%)
추천수가 겹칠때의 로직에서 마지막에 등록된 사진을 제거한다는 것이 마지막에 등록된 사진의 추천수를 생각하지 않고 삭제해서 발생하는 문제였다.
예외 케이스
3
11
1 1 1 2 1 3 3 2 3 2 4
n = int(input())
vote = int(input())
vote_list = list(map(int, input().split()))
last_pic = [] # 최근 등록된 사진
picture = [0 for i in range(n)] #사진
pic_cnt = [0 for i in range(n)] #사진 추천 횟수
for i in vote_list:
if i in picture: #이미 등록된 사진일때 카운트 업
index = picture.index(i)
pic_cnt[index] += 1
else:
tmp = 0
for j in range(len(picture)):
if picture[j] == 0: #빈자리가 있을때 사진 등록
picture[j] = i
last_pic.append(i)
pic_cnt[j] += 1
break
else:
tmp += 1
if tmp == len(picture):
#추천수가 작은거 삭제
min_cnt = min(pic_cnt)
min_index = pic_cnt.index(min_cnt)
del_pic = [index for index, value in enumerate(pic_cnt) if value == min_cnt]
if len(del_pic) != 1 and min_cnt != 0: #가장 작은 추천이 2개 이상일때
for t in del_pic:
if picture[t] == last_pic[0]:
last_pic.remove(picture[t])
picture[t] = i
pic_cnt[t] = 1
last_pic.append(i)
break
else:
picture[min_index] = i
pic_cnt[min_index] = 1
picture.sort()
for i in picture:
print(i, end= ' ')
2.틀렸습니다.(99%)
모든 예외 케이스를 다 실행해봤을때 문제가 발생하지 않았는데 뭐가 문제였는지 찾기 쉽지 않았지만 문제를 다시 한번 읽어보니 출력 부분에서는 최종 게제된 최종 후보의 학생만 출력해야 한다.
나는 게제되지 않더라도 빈 칸을 출력했기 때문에 틀렸던 것이다.
예외 케이스
2
1
1
n = int(input())
vote = int(input())
vote_list = list(map(int, input().split()))
last_pic = [] # 최근 등록된 사진
picture = [0 for i in range(n)] #사진
pic_cnt = [0 for i in range(n)] #사진 추천 횟수
for i in vote_list:
if i in picture: #이미 등록된 사진일때 카운트 업
index = picture.index(i)
pic_cnt[index] += 1
else:
tmp = 0
for j in range(len(picture)):
if picture[j] == 0: #빈자리가 있을때 사진 등록
picture[j] = i
last_pic.append(i)
pic_cnt[j] += 1
break
else:
tmp += 1
# print(tmp, len(picture))
if tmp == len(picture):
#추천수가 작은거 삭제
min_cnt = min(pic_cnt)
min_index = pic_cnt.index(min_cnt)
del_pic = [index for index, value in enumerate(pic_cnt) if value == min_cnt]
if len(del_pic) != 1 and min_cnt != 0: #가장 작은 추천이 2개 이상일때
tmp2 = 0
for t_2 in range(len(last_pic)):
for t in del_pic:
if picture[t] == last_pic[t_2]:
last_pic.remove(picture[t])
picture[t] = i
pic_cnt[t] = 1
last_pic.append(i)
tmp2 = 1
break
if tmp2 == 1:
break
else: #추천수가 겹치지 않을때
last_pic.remove(picture[min_index])
picture[min_index] = i
pic_cnt[min_index] = 1
last_pic.append(i)
picture.sort()
for i in picture:
print(i, end= ' ')📌 정답 코드
n = int(input())
vote = int(input())
vote_list = list(map(int, input().split()))
last_pic = [] # 최근 등록된 사진
picture = [0 for i in range(n)] #사진
pic_cnt = [0 for i in range(n)] #사진 추천 횟수
for i in vote_list:
# print("pic",picture)
# print("pic_cnt",pic_cnt)
# print("last_pic",last_pic)
if i in picture: #이미 등록된 사진일때 카운트 업
index = picture.index(i)
pic_cnt[index] += 1
else:
tmp = 0
for j in range(len(picture)):
if picture[j] == 0: #빈자리가 있을때 사진 등록
picture[j] = i
last_pic.append(i)
pic_cnt[j] += 1
break
else:
tmp += 1
if tmp == len(picture):
#추천수가 작은거 삭제
min_cnt = min(pic_cnt)
min_index = pic_cnt.index(min_cnt)
del_pic = [index for index, value in enumerate(pic_cnt) if value == min_cnt]
if len(del_pic) != 1 and min_cnt != 0: #가장 작은 추천이 2개 이상일때
tmp2 = 0
for t_2 in range(len(last_pic)):
for t in del_pic:
if picture[t] == last_pic[t_2]:
last_pic.remove(picture[t])
picture[t] = i
pic_cnt[t] = 1
last_pic.append(i)
tmp2 = 1
break
if tmp2 == 1:
break
else: #추천수가 겹치지 않을때
last_pic.remove(picture[min_index])
picture[min_index] = i
pic_cnt[min_index] = 1
last_pic.append(i)
picture.sort()
for i in picture:
if i != 0:
print(i, end= ' ')
