백준 23305 수강변경 #그리디 (python)

 

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

23305번: 수강변경

 

👉 나의 풀이

n = int(input())  # 학생 수

have = list(map(int, input().split()))  # 갖고 있는거
want = list(map(int, input().split()))  # 듣고 싶은거

result = n   # 최종 결과 : 원하는 수업을 못듣는 학생 수

for i in range(n):  # want 배열 탐색
    for j in range(n):  # have 배열 탐색

        # print(have)
        # print(want)
        # print()

        if want[i] == have[j] and i != j:  # 내가 듣고 싶은걸 갖고 있는 사람이 있다면
            have[i], have[j] = have[j], have[i]  # 교환
            result -= 1
            have[i] = -1  # 이후에 교환되지 않도록 -1로 설정

            # 교환한 두 명이 원하는 수업을 얻었는지 확인

            if have[j] == want[j]:
                result -= 1
                have[j] = -1  # 이후에 교환되지 않도록 -1로 설정

            break




#print(have)
#print(want)
print(result)

👉 idea (greedy)

for문으로 want 배열을 돌면서 have 배열에 듣고싶은 과목 번호가 있는지 확인

듣고싶은 과목을 발견하는 즉시 교환(swap)

교환이 일어났다는건 원하는 수업을 얻었다는 것. 다음 순환 때 더이상 교환이 일어나지 않도록  have[i]를 -1로 설정

result(원하는 수업을 못듣는 학생 수)를 1 감소

 

교환대상도 원하는 값을 얻었다면 -1로 설정 -> 마찬가지로 result를 1감소

교환대상을 찾을 필요가 없으므로 want를 -1로 설정. 

 

 

👉 다른 풀이

n = int(input())
data = [0] * 1000001

for i in list(map(int, input().split())) :
  data[i] += 1

result = 0
for i in list(map(int, input().split())) :
  if data[i] >= 1 :
    data[i] -= 1
  else :
    result += 1

print(result)

 

1. 신청한 수업을 의미하는 수들을 입력받아 리스트 형태로 구성하고 반복문을 통해 data리스트의 해당 인덱스의 값을 1 증가시킨다.

 

2. 교환을 통해 수강하고 싶은 수업의 번호를 의미하는 수들을 입력받아 리스트 형태로 구성하고 반복문을 통해 값을 하나씩 확인한다.

 

3. 만약 data 리스트의 해당 인덱스의 값이 1이상일 경우 그 값을 1씩 빼준다.

 

4. 인덱스의 값이 0일 경우 result값을 1 증가시키고, 반복문이 종료되면 result 값을 출력한다.

 

 

 

👉 정답 풀이를 보고 나니 내가 너무 어렵게푼거같다 ㅎ