A사장은 업무 개선방안을 사원들에게 공모하여 n개의 개선방안 레포트를 제출 받았다.
이를 임원들에게 주어 1등에서 n등 까지 순위를 메기라고 지시한다.
이 결과들을 모아 포상할 예정이다.
B부장도 이런 지시를 받아 순위를 메겨야 한다. 한꺼번에 여러 레포트를 비교하려니 머리가 복잡하다. 그래서 이진 트리를 이용하여 2개씩 비교해 가며 순위를 메기기로 하였다.
<입력>
레포트수 입력 : 5
1번, 2번 레포트중 더 우수 한것은? : 2
1번, 3번 레포트중 더 우수 한것은? : 1
1번, 4번 레포트중 더 우수 한것은? : 4
2번, 4번 레포트중 더 우수 한것은? : 2
1번, 5번 레포트중 더 우수 한것은? : 5
2번, 5번 레포트중 더 우수 한것은? : 5
<결과>
1등 : 5
2등 : 2
3등 : 4
4등 : 1
5등 : 3
<해결방안> 1번 레포트를 2진 트리의 루트를 삼고 2~n번 까지 순서대로 트리내용 보다 우수한것은 왼쪽, 우수하지 못한것은 오른쪽의 노드로 삼는 것을 반복한 후 인오더 서치하면 우수한 것에서 그렇지 못한 순서로 나열 된다.
포인트를 사용 하여도 되고, 그냥 배열을 사용해도 되겠죠. 동적 할당이 어렵거나 안되면 레포트를 100개 이내에서 할당하여 처리 하세요.
제가 관리자로 일할때 사용한 방법 입니다. 실제로는 프로그램을 사용 한것이 아니고 손으로 간단히 그렸습니다.
자세한 설명은 아래의 제 블로그를 참고 하세요.
https://blog.naver.com/i_jeju/221492642019
4개의 풀이가 있습니다.
def comp(l):
if not l:
return []
ll, rl = [], []
for i in range(1, len(l)):
gr = input('What is a more great report?(%d, %d) : ' % (l[0], l[i]))
if int(gr) == l[0]:
rl.append(l[i])
else:
ll.append(l[i])
return comp(ll) + [l[0]] + comp(rl)
if __name__ == '__main__':
n = input('Input number of reports : ')
reports = comp([i for i in range(1, int(n) + 1)])
for i in range(int(n)):
print('Rank %d : %d' % (i+1, reports[i]))
python 3.7.2
tree2=[]
#노드추가
def tr_apn(nam):
tt=[]
tt.append(-1) #left link (-1:널)
tt.append(name) #노드값
tt.append(-1) #ri link (-1:널)
tree2.append(tt)
#root구성
name=input('과제제출자: ')
tr_apn(name)
#tree구성
p=0
name=input('과제제출자(종료:-1): ')
while name!='-1':
i=0
while True:
pan=int(input(name+'가 '+tree2[i][1]+'보다 잘햇으면 1, 아니면 2: '))
if pan == 1:
k=0
else:
k=2
if tree2[i][k]==-1:
p=p+1
tree2[i][k]=p
tr_apn(name)
break
else:
i=tree2[i][k]
print()
name=input('과제제출자(종료:-1): ')
#인오더 트레버스(inorder traversal) : 재귀호출
def in_tra(p):
if p != -1:
in_tra(tree2[p][0])
print(tree2[p][1])
in_tra(tree2[p][2])
in_tra(0)
과제제출자: aa
과제제출자(종료:-1): bb
bb가 aa보다 잘햇으면 1, 아니면 2: 2
과제제출자(종료:-1): cc
cc가 aa보다 잘햇으면 1, 아니면 2: 1
과제제출자(종료:-1): dd
dd가 aa보다 잘햇으면 1, 아니면 2: 2
dd가 bb보다 잘햇으면 1, 아니면 2: 1
과제제출자(종료:-1): ee
ee가 aa보다 잘햇으면 1, 아니면 2: 2
ee가 bb보다 잘햇으면 1, 아니면 2: 2
과제제출자(종료:-1): ff
ff가 aa보다 잘햇으면 1, 아니면 2: 1
ff가 cc보다 잘햇으면 1, 아니면 2: 2
과제제출자(종료:-1): -1
cc
ff
aa
dd
bb
ee
# "newitem is better"에서 256 보다 크면 ==를 써야함
class BinaryTree:
item, left, right = None, None, None
def __init__(self, item):
assert 0 < item <= 256
self.item = item
def inorder(self):
return (self.left.inorder() if self.left else []) + \
[self.item] + \
(self.right.inorder() if self.right else [])
def insert(self, newitem, inp):
assert self.item != newitem
better = inp.pop(0)
print('{}번, {}번 레포트 중 더 우수한 것은? {}'.format(self.item, newitem, better))
if newitem is better:
self.left = BinaryTree(newitem) if not self.left else self.left.insert(newitem, inp)
else:
self.right = BinaryTree(newitem) if not self.right else self.right.insert(newitem, inp)
return self
n, reports, inp = 5, [1, 2, 3, 4, 5], [2, 1, 4, 2, 5, 5]
root = BinaryTree(reports.pop(0))
while reports:
root.insert(reports.pop(0), inp)
print(root.inorder())
using System;
using System.Collections.Generic;
namespace solution
{
class Node
{
public int val;
public Node left;
public Node right;
public Node(int val, Node left=null, Node right=null)
{
this.val = val;
this.left = left;
this.right = right;
}
}
class Program
{
static void Main(string[] args)
{
Console.Write("\n 레포트수 입력 : ");
int n = int.Parse(Console.ReadLine());
Node head = new Node(1);
rankCompare(n, head);
List<int> list = new List<int>();
listNode(head, list);
Console.WriteLine("\n\n <결과> ");
for (int i = 0; i < n; i++)
{
Console.WriteLine("\n {0}등 : {1}", i+1, list[i]);
}
}
private static void rankCompare(int n, Node head)
{
for (int i = 2; i <= n; i++)
{
Node curr = head;
while (true)
{
Console.Write("\n {0}번, {1}번 레포트중 더 우수 한것은? :", curr.val, i);
int input = int.Parse(Console.ReadLine());
if (input == i)
{
if (curr.right == null)
{
curr.right = new Node(i);
break;
}
curr = curr.right;
}
else
{
if(curr.left == null)
{
curr.left = new Node(i);
break;
}
curr = curr.left;
}
}
}
}
private static void listNode(Node node, List<int> list)
{
if (node.right != null)
listNode(node.right, list);
list.Add(node.val);
if (node.left != null)
listNode(node.left, list);
}
}
}