[ 백준 / BOJ ] 나3곱2

/  제출 1  /

 

n = int(input())
B = list(map(int, input().split()))

# 나3, 곱2 => 곱3, 나2 해서 값 나오면 해당 숫자의 이전 값, 둘이 붙여
# 만약 둘 다 안 되면 그게 첫 번째 값
order = []
for num in B:
  mulThree = num * 3
  if num % 2 == 0:
    divTwo = num // 2
  else:
    divTwo = 0

  if divTwo in B:
    order.append([divTwo, num])
    continue
  elif mulThree in B:
    order.append([mulThree, num])
    continue
  else:
    order.append([0, num])
result = []
start = 0
next = 0
while len(result) != n:
  for item in order:
    if item[0] == start:
      result.append(item[1])
      next = item[1]
      break
    if item[0] == next:
      result.append(item[1])
      next = item[1]
      break
      
print(*result, sep=" ")

 

틀렸습니다.   가 나왔습니다. ( 풀이시간 30분 )

 

예제 테스트케이스 두 개 다 나오고 로직도 괜찮아보였는데..

 

가능한 연산을 반대로 구현하고, 그 구현값이 리스트에 있으면 두 값은 전후 상관관계를 가진다고 생각했습니다.

따라서 이와 같이 연관관계 리스트를 만들어줬습니다.

그리고 마지막에 2중 for문을 돌며 다음 값들을 뽑아와줬습니다.

 

---

/  다른 분 풀이  /

 

질문검색방을 보니까 대부분 문제에서 제시한 내용 그대로 따라가신 것 같습니다.

또한 해당 문제 관련 알고리즘 강의가 있는 것 같고, 저도 그 내용을 참고해 복습했습니다.

n = int(input())
b = list(map(int, input().split()))

a = []

for num in b:
    can3 = 0
    num_origin = num
    while True:
        if num % 3 == 0:
            can3 += 1
            num //= 3
        else:
            break
    a.append([can3, num_origin])

a.sort(key= lambda x: (-x[0], x[1]))
for i in range(n):
    print(a[i][1], end=' ')

 

---

/  제출 2  /

 

위와 같은 서로소를 이용한 풀이는 진짜 떠올릴 자신이 없고, 제가 푼 접근이 나쁘지 않은 것 같아 다시 수정해봤습니다.

 

굳이 연산을 뒤집어 가면서 복잡하게 하지 말고, 그냥 문제 해결법처럼 3으로 나눠지면 나누고 안 나눠지면 2를 곱하는 식으로 나가면서, linked list같은 느낌으로 head-tail구성으로 만들어준 뒤 배열에 넣었습니다.

 

그 뒤 2중 for문을 돌며 head에 들어맞는 tail을 찾아오고 결과 리스트에 차곡차곡 넣어준 뒤, 마지막에 순서를 뒤집는 연산을 수행했습니다. 조금 쓸데없는 연산이 들어간 것 같기는 하지만 이해하기 더 쉬워 구현면에서는 이렇게 접근하는게 제게는 유리할 것 같다고 생각했습니다.

 

n = int(input())
B = list(map(int, input().split()))

# 나3, 곱2 => 곱3, 나2 해서 값 나오면 해당 숫자의 이전 값, 둘이 붙여
# 만약 둘 다 안 되면 그게 첫 번째 값
order = []
for num in B:
  if num % 3 == 0 and num // 3 in B:
    order.append([num, num//3])
  else:
    if num * 2 in B:
      order.append([num, num*2])
    else:
      order.append([num, 0])

result = []
tail = 0
while len(result) != n:
  for item in order:
    if item[1] == tail:
      result.append(item[0])
      tail = item[0]
      
result.reverse()
print(' '.join(map(str, result)))

 

 

일단 문제를 그대로 따라가자! 정답 맞추는게 우선! 효율성 리팩토링은 차근차근! 새로운 느낌의 접근은 실력이 더 는 후에 하자!