백준 03일차

29. 수 정렬 - 버블로 풀어봄

##############버블 정렬 양 옆에 수를 비교해서 왼쪽이 크면 교환 반복횟수는 n-1번#####################

##############시간복잡도는 O(n²) for 안에 for, 공간복잡도는 O(n): 배열을 하나만 써서##################

import sys

 

n = int(sys.stdin.readline())

num = []

for x in range(n):

tmp = int(sys.stdin.readline())

num.append(tmp)

 

def swap(a,b):

num[a], num[b] = num[b], num[a]

 

for i in range(len(num)-1):

for y in range(len(num)-1):

if num[y] > num[y+1]:

swap(y,y+1)

 

for j in num:

print(j)

30. 수 정렬 2 1. 병합정렬 merge sort 시간초과 -> quick sort로 바꿈

#######################merge sort###############

import sys, math

 

n = int(sys.stdin.readline())

num = []

for x in range(n):

tmp = int(sys.stdin.readline())

num.append(tmp)

 

def merge(arr):

 

if len(arr) == 1:

return arr

mid = len(arr)//2

end = len(arr)

result = []

left = merge(arr[0:mid])

right = merge(arr[mid:end])

i,j = 0,0

#print(left, right,'before')

while len(left)>i and len(right)>j:

if left[i] < right[j]:

result.append(left[i])

i += 1

else:

result.append(right[j])

j += 1

while len(right)>j:

result.append(right[j])

j += 1

while len(left)>i:

result.append(left[i])

i += 1

#print(arr,'arr')

#print(result,'after')

return result

 

results = merge(num)

for x in results:

print(x)

 

 ####### ####### ######quick sort도 시간초과발생 python에서는 정렬알고리즘으로 불가 pypy를 이용########

import sys

 

n = int(sys.stdin.readline())

arr = []

for x in range(n):

tmp = int(sys.stdin.readline())

arr.append(tmp)

 

def swap(arr,a,b):

arr[a],arr[b] = arr[b],arr[a]

return arr

 

def quick(arr, start, end):

if start >= end:

return

 

pivot = start

left = start + 1

right = end

 

while left <= right:

while left <= end and arr[left] <= arr[pivot]:

left += 1

while right > start and arr[right] > arr[pivot]:

right -= 1

if left > right:

swap(arr, pivot, right)

else:

swap(arr, left, right)

 

quick(arr,start, right-1)

quick(arr,right+1,end)

 

 

quick(arr,0,len(arr)-1)

for x in arr:

print(x)

 

31. 수 정렬하기(계수정렬 == 도수정렬 == 카운팅정렬)

import sys

 

n = int(sys.stdin.readline())

arr = [0] * 10001

for x in range(n):

tmp = int(sys.stdin.readline())

arr[tmp] += 1

for x in range(10001):

while arr[x]>0 :

print(x)

arr[x] -= 1

 

 

32. 단어 정렬 문제

## sorted 함수와 ramda 함수 ##
## key = lamda x : (조건1,조건2) ## 조건1 우선 적용 내림차순일경우 -x[1] ##

finish = sorted(result, key = lambda x : (x[0], x[1]))

import sys

 

n = int(input())

arr = []

result = []

for x in range(n):

tmp = input()

arr.append(tmp)

c = set(arr)

for y in c:

lis = []

lis.append(len(y))

lis.append(y)

result.append(lis)

finish = sorted(result, key = lambda x : (x[0], x[1]))

for k in finish:

print(k[1])

 

33. 백설 공주 난쟁이 찾기

1) for 문 중첩

arr = []

for k in range(9):

tmp = int(input())

arr.append(tmp)

result = []

 

def find(start):

 

start = start

sum = 0

for q in range(start,9):

for w in range(start,9):

for e in range(start,9):

for r in range(start,9):

for t in range(start,9):

for y in range(start,9):

for u in range(start,9):

if q != w and q != e and q != r and q != t and q != y and q != u :

if w != e and w != r and w != t and w != y and w != u :

if e != r and e != t and e != y and e != u :

if r != t and r != y and r != u :

if t != y and t != u :

if y != u :

sum = arr[q] + arr[w] + arr[e] + arr[r] + arr[t] + arr[y] + arr[u]

if sum == 100:

#print(sum,q,w,e,r,t,y,u)

result.append(arr[q])

result.append(arr[w])

result.append(arr[e])

result.append(arr[r])

result.append(arr[t])

result.append(arr[y])

result.append(arr[u])

return

else:

sum = 0

 

return

 

 

find(0)

for x in sorted(result):

print(x)