66th. CodeUp #3015 : 성적표 출력

PROBLEM.

성적표 출력

---

IDEA.

구조체와 삽입정렬 개념을 사용하여 구현하고자 했다.

---

TRIAL AND ERROR 1. 구조체 구현을 위해 struct 모듈을 사용

 

Python에서 구조체를 구현하는 방법 2가지에 대해 저번 포스팅에서 다뤘다.

 

Python의 구조체 구현하기 ↓

2020/12/25 - [Algorithm] - 65th. CodeUp #3017 : 정렬 기준

 

이 문제에서는 struct 모듈을 사용하고자 했는데, 막상 작성하다보니 '이름' 속성을 처리하기에 어려움이 있었다. '이름' 속성은 최대 10 byte 크기를 갖는다고 문제에 주어져있어 객체의 포멧을 정하는 것 까지는 가능했다.

 

import struct
n, m = map(int, input().split())
studs = list()

for i in range(n) :
	nm, sc = input().split()
	studs.append(struct.pack('10si', bytes(nm, encoding=
	"euc-kr"), int(sc)))

for i in range(1,n) :
	key = struct.unpack('10si', studs[i])
	isEnd = False
	for j in range(i-1,-1,-1) :
		print(j)
		res = struct.unpack('10si', studs[j])
		if key[1] > res[1] :
			studs[j+1] = studs[j]
		else :
			isEnd = True
	if isEnd : studs[j+1] = key
	else : studs[0] = key

for i in range(m) :
	res = struct.unpack('10si', studs[i])
	print(res[0])
 
'''
결과
4 2
Jeon 95
Kim 59
Lee 90
Bae 100
0
1
Traceback (most recent call last):
  File "./구조체연습/3015.py", line 16, in <module>
    res = struct.unpack('10si', studs[j])
TypeError: a bytes-like object is required, not 'tuple'
'''

 

하지만 막상 삽입정렬을 구현하려다 보니 studs 배열에서 꺼낼때마다 unpack을 해줘야한다는 것을 깨달았다. 그렇지 않으면 속성값이 byte형이기 때문에 값을 비교할 수 없다ㅜㅠ. 그리고 배열 인덱스를 바꿀 때도 다시 pack을 해줘야하는 것 같다. 위 소스에서는 pack을 하지 않고 studs[i+1]에 unpack된 key를 대입했기 때문에 tuple이 아닌 bytes-like objec가 필요하다는 에러가 뜬 것 같다. 

 

이런 작업을 하지 않으려면 애초부터 unpack한 배열을 만들어준 후 그 배열값으로 정렬을 해야한다는 생각이 들었다. 그런데 다시 생각해보면 unpack한 객체는 그냥 tuple인 것이기 때문에 collections 모듈의 namedtuple을 사용하는 것과 차이가 없다는 생각이 들었다. 그래서 그냥 namedtuple을 사용하기로 했다.

 

import collections
n, m = map(int, input().split())
studs = list()
Student = collections.namedtuple('Student',['name','score'])

for i in range(n) :
	nm, sc = input().split()
	studs.append(Student(nm, int(sc)))

for i in range(1,n) :
	key = studs[i]
	isend = False
	for j in range(i-1,-1,-1) :
		if key.score > studs[j].score :
			studs[j+1] = studs[j]
		else :
			isend = True
			break
	if isend : studs[j+1] = key
	else :studs[0] = key

for i in range(m) :
	print(studs[i].name)

 

TRIAL AND ERROR 2. 삽입정렬 구현

 

두 번째 시행착오는 삽입정렬 구현이다. 위 소스를 보면 isend 변수까지 나오면서 좀 복잡해진 것을 알 수 있다. 안쪽 for문이 끝난 후 studs[j+1]의 자리에 key를 넣어주고 있는데 만약 key값이 최댓값이어서 break 되지 않았을 때는 0번째 인덱스에 넣어줘야하기 때문이다. isend 없이 무조건 j+1에 넣어주면 끝에 가서 아래와 같은 참사가 발생한다. 

 

import collections
n, m = map(int, input().split())
studs = list()
Student = collections.namedtuple('Student',['name','score'])

for i in range(n) :
	nm, sc = input().split()
	studs.append(Student(nm, int(sc)))


for i in range(1,n) :
	key = studs[i]
	#isend = False
	for j in range(i-1,-1,-1) :
		if key.score > studs[j].score :
			studs[j+1] = studs[j]
		else :
			#isend = True
			break
	#if isend : 
	studs[j+1] = key
	print(studs)
	#else :studs[0] = key

for i in range(m) :
	print(studs[i].name)
    
'''
4 2
Jeon 95
Kim 59
Lee 90
Bae 100
[Student(name='Jeon', score=95), Student(name='Kim', score=59), Student(name='Lee', score=90), Student(name='Bae', score=100)]
[Student(name='Jeon', score=95), Student(name='Lee', score=90), Student(name='Kim', score=59), Student(name='Bae', score=100)]
[Student(name='Jeon', score=95), Student(name='Bae', score=100), Student(name='Lee', score=90), Student(name='Kim', score=59)]
Jeon
Bae
'''

 

최댓값 Bae가 0번째 idx에 가지 못하고 1번째 idx에 대입된다. 사실 isend를 사용해서 풀 수 있긴 하지만 뭔가 더 좋은 방법이 있을 것 같아 구글링해봤다. 

 

import collections
n, m = map(int, input().split())
studs = list()
Student = collections.namedtuple('Student',['name','score'])

for i in range(n) :
	nm, sc = input().split()
	studs.append(Student(nm, int(sc)))

for i in range(1,n) :
	key = studs[i]
	for j in range(i-1,-2,-1) :
		if j > -1 and key.score > studs[j].score :
			studs[j+1] = studs[j]
		else :
			break
	studs[j+1] = key

for i in range(m) :
	print(studs[i].name)

 

그 결과, for문의 범위를 조정해야한다는 것을 깨달았다. 나는 j가 -1 까지 나와야하기 때문에 range 범위를 -2로 조정해주었다. 이때, j = -1이면 배열 값을 비교할 때 index out of range 오류가 날 것이므로 j > -1 조건도 추가해주었다.

 

 

---

SOURCE.

import collections
n, m = map(int, input().split())
studs = list()
Student = collections.namedtuple('Student',['name','score'])

for i in range(n) :
	nm, sc = input().split()
	studs.append(Student(nm, int(sc)))

for size in range(1, n) :
	val = studs[size]
	i = size
	while i > 0 and studs[i-1].score < val.score :
		studs[i] = studs[i-1]
		i -= 1
	studs[i] = val

for i in range(m) :
	print(studs[i].name)

---

LESSON.

- 구조체를 구현하기에는 namedtuple이 좀 더 적합한 것 같다. struct 모듈은 언제 사용하면 좋은지 좀 더 공부가 필요해보인다.

- while문과 for문의 차이점 : while문은 i를 업데이트 하기 전에 반복문을 멈출 수 있다.

---

Reference.

ejklike.github.io/2017/03/04/sorting-algorithms-with-python.html

Study Note - 파이썬으로 정렬 알고리즘 구현하기

End.