[ 그리디 알고리즘 1 ] 백준 1774 수 묶기 파이썬

 

 

백준 1744번 수 묶기

 

처음에는 너무 쉽게 풀은 줄 알았으나 생각할수록 예외가 많아지는 문제였다. 실패를 여러번 한 케이스 

n = int(input())
plus=[]
minus=[]
zero=0
for i in range(n):
  x = int(input())
  if x>0: plus.append(x)
  if x<0: minus.append(x)
  if x==0: zero+=1

plus.sort(reverse=True)
minus.sort()

answer = 0
used=[]
for i in range(len(plus)):
    if i in used: continue
    elif i == len(plus)-1: 
        answer += plus[i]
    elif plus[i]>1 and plus[i+1]>1:
        answer += plus[i]*plus[i+1]
        used.append(i+1)
    else:
        answer += plus[i]

used2=[]
for i in range(len(minus)):
    if i in used2: 
        continue
    elif i==len(minus)-1: 
        if zero>0: answer+= 0
        else: answer += minus[i]
    else:
        answer += minus[i]*minus[i+1]
        used2.append(i+1)


print(answer)

 

 

 

 

풀이 설명

n = int(input())
plus=[]   # 양수 리스트
minus=[]   # 음수 리스트
zero=0
for i in range(n):
  x = int(input())
  if x>0: plus.append(x)
  if x<0: minus.append(x)
  if x==0: zero+=1

plus.sort(reverse=True) # 내림차순
minus.sort()  # 오름차순 (+- 상관없이 숫자 큰걸 앞으로)


answer = 0
used=[]  # 사용한 i+1을 담기 -> for문 돌릴필요가 없다. (이미 계산됨)
for i in range(len(plus)):
    if i in used: continue # 이미 사용되었으면 continue
    elif i == len(plus)-1: # 리스트의 마지막인 경우 양수는 그냥 해당 요소를 더하기 
        answer += plus[i]
    elif plus[i]>1 and plus[i+1]>1: # 1보다 큰 경우 (1을 포함하면 4*1=4 , 4, 1 = 5 이렇게 각각 더한 경우보다 수가 작아짐 )
        answer += plus[i]*plus[i+1]
        used.append(i+1) # 미리사용한 i+1 은 used로 넣기 
    else:
        answer += plus[i] # plus[i]가 1인 경우

used2=[]
for i in range(len(minus)):
    if i in used2: # 위와 동일하게 사용한 i+1을 담은 used2 배열 (i가 used 배열 안에 있으면 다시 계산할 필요X 이미 곱했다.)
        continue
    elif i==len(minus)-1: #마지막 배열의 요소일 경우, 마이너스이기 때문에 0이 있다면 0으로 곱하면 0 이된다. 마이너스 그대로 더하기보다 0이 존재하면 (zero >0이라면) 곱해서 더해주기
        if zero>0: answer+= 0
        else: answer += minus[i]
    else:
        answer += minus[i]*minus[i+1]
        used2.append(i+1)


print(answer)

 

 

 

 

 

 

 

 

다른 분의 정답 코드 

n = int(input())
arr1=[]
arr2=[]
arr3=[]
ret=0

for _ in range(n):
    x = int(input())
    if x<1: arr1.append(x) # 마이너스 ~ 0까지 
    elif x>1: arr2.append(x) # 2이상의 양수 
    else: arr3.append(x) # 1 

arr1.sort()
arr2.sort()

for i in range(0,len(arr1)-1,2):
    ret += arr1[i]*arr1[i+1]
if len(arr1)%2==1: ret+=arr1[-1]

for i in range(len(arr2)-1,0,-2):
    ret += arr2[i]*arr2[i-1]
if len(arr2)%2==1: ret += arr2[0]

ret += sum(arr3)
print(ret)

간결하다,, 이 분은 sort를 모두 똑같이 하고 for문을 돌릴 때 2 간격으로 + - 로 하셨다. 그리고 너무 똑똑한 점은 1을 기준으로 나눈 점 !! 나는 0을 기준으로 따로 빼서 만들었는데 그래서 1일 경우 복잡해졌는데 1을 따로 빼버리면 한결 고민이 적어진다.