[백준][계수정렬] 과제 안 내신 분..?

오늘의 학습 키워드

계수 정렬, 구현

 

오늘의 회고

🌱 오늘의 문제

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

 

28개의 중복되지 않는 1 이상 30 이하의 정수값을 입력 받는다.

이 중 1 이상 30 이하의 수 중 등장하지 않은 값 2개를 출력한다.

 

어려운 문제는 아니지만 "계수 정렬"이라는 개념을 적용해보기 좋은 문제인 것 같아 게시물로 작성해 본다.

계수 정렬에 대해 잘 모른다면 아래 글의 4. 계수 정렬 내용을 확인하세요! ☺️

 

https://developer-zoyh.tistory.com/30

[알고리즘] 정렬 시리즈 1탄: 선택 정렬, 삽입 정렬, 퀵 정렬, 계수 정렬

 

 

 

🌱 나의 시도

'''
- 문제 유형: 구현
- 풀이 방법: 일종의 계수 정렬을 활용한다. 출석 여부 배열을 활용하자!
- 풀이 순서
1. 학생 수 만큼의 출석 여부(Boolean)를 저장할 배열 isAttended 배열을 만든다.
2. 제출한 28명의 출석 번호를 입력 받으며, 입력 받은 출석 번호에 대하여 isAttended 배열에 처리해준다.
3. 출석 여부 배열을 1번부터 돌며 값이 False인 위치의 인덱스(출석 번호)를 출력한다.

-> 1차원 배열을 순회하면서 모든 과정을 처리할 수 있으므로 시간 복잡도는 O(n)이다.
'''
cnt_students = 31 # 0번부터 시작하므로 +1
isAttended = [False] * cnt_students 

for _ in range(28):
    x = int(input())
    isAttended[x] = True

for i in range(1, cnt_students):
    if not isAttended[i]: print(i)

 

 

 

풀이는 계수 정렬 알고리즘을 참고하되, 개수를 세지 않고 등장 여부(True/False)를 체크해주었다.

1부터 배열을 돌면서 False인 값을 출력해주면, 입력에서 등장하지 않은 값을 출력할 수 있다.

 

 

오늘의 후기

계수 정렬을 몰랐던 때에도 풀 수 있던 문제이지만, 개념을 문제로 만나면서 머릿속에 있던 여러 파편들이 연결되는 듯한 느낌을 받았다.

문제의 여러 조건(입출력 형식, 제약 조건 등)을 보고 문제를 파악하고 설계해나가는 시야가 넓어지고 있다.

더 다양하고 재밌는 문제들을 풀어나가고 싶다.