Anagram이란 두 문자열이 알파벳의 나열 순서를 다르지만 그 구성이 일치하면 두 단어는 아 나그램이라고 합니다. 예를 들면 AbaAeCe 와 baeeACA 는 알파벳을 나열 순서는 다르지만 그 구성을 살펴보면 A(2), a(1), b(1), C(1), e(2)로 알파벳과 그 개수가 모두 일치합니다. 즉 어느 한 단어를 재 배열하면 상대편 단어가 될 수 있는 것을 아나그램이라 합니다.
길이가 같은 두 개의 단어가 주어지면 두 단어가 아나그램인지 판별하는 프로그램을 작성하세 요. 아나그램 판별시 대소문자가 구분됩니다.
▣ 입력설명 첫 줄에 첫 번째 단어가 입력되고, 두 번째 줄에 두 번째 단어가 입력됩니다. 단어의 길이는 100을 넘지 않습니다.
▣ 출력설명 두 단어가 아나그램이면 “YES”를 출력하고, 아니면 ”NO”를 출력합니다.
▣ 입력예제 1
AbaAeCe
baeeACA
▣ 출력예제 1
YES
import sys
sys.stdin = open("input40.txt", "rt")
p1 = dict()
p2 = dict()
for a in input():
p1[a] = p1.get(a, 0) + 1
for b in input():
p2[b] = p2.get(b, 0) + 1
if p1 == p2:
print('YES')
else:
print('NO')
문제는 1번과 같음
import sys
sys.stdin = open("input41.txt", "rt")
a1 = input()
a2 = input()
def hash_func(x):
if x.isupper():
return ord(x)-65
else:
return ord(x)-97+26
h1 = [0] * 52
h2 = [0] * 52
for x in a1:
h1[hash_func(x)] += 1
for x in a2:
h2[hash_func(x)] += 1
for i in range(52):
if h1[i] != h2[i]:
print('NO')
break
else:
print('YES')
최소힙은 완전이진트리로 구현된 자료구조입니다. 그 구성은 부모 노드값이 왼쪽자식과 오른 쪽 자식노드의 값보다 작게 트리를 구성하는 것입니다. 그렇게 하면 트리의 루트(root)노드는 입력된 값들 중 가장 작은 값이 저장되어 있습니다. 예를 들어 5 3 2 1 4 6 7순으로 입력되 면 최소힙 트리는 아래와 같이 구성됩니다.
최소힙 자료를 이용하여 다음과 같은 연산을 하는 프로그램을 작성하세요.
1. 자연수가 입력되면 최소힙에 입력한다.
2. 숫자 0 이 입력되면 최소힙에서 최솟값을 꺼내어 출력한다.(출력할 자료가 없으면 -1를 출력한다.)
3. -1이 입력되면 프로그램 종료한다.
▣ 입력설명 첫 번째 줄부터 숫자가 입력된다. 입력되는 숫자는 100,000개 이하이며 각 숫자의 크기는 정 수형 범위에 있다.
▣ 출력설명
▣ 입력예제 1
5
3
6
0
5
0
2
4
0
-1
▣ 출력예제 1
3
5
2
import sys
class Heap:
def __init__(self):
self.data = [None]
def insert(self, item):
self.data.append(item)
i = len(self.data) - 1
while i > 1:
if self.data[i] < self.data[(i // 2)]:
self.data[i], self.data[(i // 2)] = self.data[(i // 2)], self.data[i]
else:
break
def remove(self):
if len(self.data) > 1:
self.data[-1], self.data[1] = self.data[1], self.data[-1]
data = self.data.pop()
self.min_heapify(1)
else:
data = None
return data
def min_heapify(self, i):
left = 2 * i
right = 2 * i + 1
smallest = i
if left < len(self.data) and self.data[i] > self.data[left]:
smallest = i
if right < len(self.data) and self.data[left] > self.data[right]:
smallest = i
if smallest != i:
self.data[i], self.data[smallest] = self.data[smallest], self.data[i]
self.min_heapify(smallest)
sys.stdin = open("input42.txt", "rt")
heap = Heap()
while True:
i = int(input())
if i == -1:
break
elif i == 0:
min = heap.remove()
print(min)
else:
heap.insert(i)
import sys
import heapq as hq
sys.stdin = open("input42.txt", "rt")
a = []
while True:
n = int(input())
if n == -1:
break
if n == 0:
if len(a) == 0:
print(-1)
else:
print(hq.heappop(a))
else:
hq.heappush(a, n)
힙만 최대힙으로 바꾸고 문제는 같음
import sys
import heapq as hq
sys.stdin = open("input42.txt", "rt")
class Heap:
def __init__(self):
self.data = [None]
def insert(self, item):
self.data.append(item)
i = len(self.data) - 1
while i > 1:
if self.data[i] > self.data[i//2]:
self.data[i], self.data[i//2] = self.data[i//2], self.data[i]
else:
break
def remove(self):
i = len(self.data) - 1
if i > 1:
self.data[1], self.data[-1] = self.data[-1], self.data[1]
data = self.data.pop()
self.max_heapify(1)
else:
data = None
return data
def get_length(self):
return len(self.data)
def max_heapify(self, i):
left = 2*i
right = 2*i+1
largest = i
size = len(self.data)
if left < size and self.data[i] < self.data[left]:
largest = left
if right < size and self.data[largest] < self.data[right]:
largest = right
if largest != i:
self.data[largest], self.data[i] = self.data[i], self.data[largest]
self.max_heapify(largest)
heap = Heap()
while True:
i = int(input())
if i == -1:
break
elif i == 0:
if heap.get_length() > 1:
max = heap.remove()
print(max)
else:
print(-1)
else:
heap.insert(i)
import sys
import heapq as hq
sys.stdin = open("input42.txt", "rt")
a = []
while True:
n = int(input())
if n == -1:
break
if n == 0:
if len(a) == 0:
print(-1)
else:
print(-hq.heappop(a))
else:
hq.heappush(a, -n)
10진수 N이 입력되면 2진수로 변환하여 출력하는 프로그램을 작성하세요. 단 재귀함수를 이용 해서 출력해야 합니다.
▣ 입력예제 1
11
▣ 출력예제 1
1011
import sys
sys.stdin = open("input44.txt", "rt")
def DFS(x):
if x == 0:
return
DFS(x//2)
print(x%2, end='')
if __name__ == "__main__":
n = int(input())
DFS(n)