acmicpc.net 1920(정렬), 1620(정렬), 1764(정렬), 1181(정렬)

https://www.acmicpc.net/problem/1920

정렬 문제다. 아주 옛날에 별생각없을때 푼적이 있는데 그땐 그냥 반복문으로 다 검사하는식으로 해서 

시간초과가 뜨고 안했었다. 이번엔 뭔가 공부도 하고있겠다 구현해서 멋있게 통과해보자!!!! 하는 

마음이 갑자기 들어서 구현했다. 참고로 바로 아래 소스는 답이 아니다.

# -*- encoding: cp949 -*-
def BinarySearch(a,l,r,x):
    if l > r:
        print 0
        #return 
    else:
        mid = (l+r)/2
        if x < a[mid]:
            BinarySearch(a,l,mid-1,x)
        elif a[mid] < x:
            BinarySearch(a,mid+1,r,x)
        else:
            print 1#'find!',a[mid],mid
            #return True#print 'find!',a[mid],mid

def CheckSort(a,n):
    sorted = 1
    for i in xrange(n):
        if a[i] > a[i+1]:
            sorted = 0
        if sorted==0:
            break
    if sorted==1: print '정렬 완료'
    else: print '정렬 오류 발생'

def InsertionSort(a,l,r):
    #print 'l =',l,', r =',r
    for i in xrange(l+1,r+1):
        #print 'i =',i
        v = a[i]; j = i
        #print 'h =',j-1,a[j-1],v
        while a[j-1] > v:
            a[j] = a[j-1];
            j -= 1
            if j < 1: break
        a[j] = v

M = 20
def QuickSort(a,l,r):
    if r-l <= M: InsertionSort(a,l,r)
    else:
        v = a[r]; i = l-1; j = r
        while True:
            i += 1
            while a[i] < v:
                i += 1
            j -= 1
            while a[j] > v:
                j -= 1
            if i>=j: break
            a[i],a[j] = a[j],a[i]
        a[i],a[r] = a[r],a[i]
        QuickSort(a,l,i-1)
        QuickSort(a,i+1,r)

n = int(raw_input())
a = map(int,raw_input().split())
m = int(raw_input())
find = map(int,raw_input().split())

QuickSort(a,0,n-1)
#CheckSort(a,n-1)
for i in range(m):
    BinarySearch(a,0,n-1,find[i])

그랬는데 첫 구현은 런타임 에러가 떴다. 기본 퀵정렬소스 c에서 파이썬으로 고치는데 2시간이 

걸렸는데....(그냥 퀵도 아니고 실행해본결과 그나마 조금 빠른 작은 부분파일을 고려한 퀵이었다. 

미묘한 +-1차이때문에 시간이 오래걸림.) 냈는데 런타임에러뜨니까 힘이 빠졌다. 역시 그냥 

라이브러리를 믿어야되..... 찾아보니까 이진 탐색까지 파이썬에서는 라이브러리로 다 있다. -_-............

# -*- encoding: cp949 -*-
import bisect
n = int(raw_input())
a = sorted(map(int,raw_input().split()))
m = int(raw_input())
find = map(int,raw_input().split())
for i in range(m):
    r = bisect.bisect(a,find[i])
    if a[r-1]!=find[i]:
        print 0
    else: print 1

2016-10-11 추가.

지금 보니까 이 코드도 그리 좋아보이진 않는다. 지금의 나라면 set으로 해쉬맵을 만들어서 O(1)로

# -*- encoding: cp949 -*-
n=input()
num = set(map(int,raw_input().split()))
m=input()
for i in map(int,raw_input().split()):
    if i in num:
        print 1
    else: print 0

탐색을 했을것같다. 

https://www.acmicpc.net/problem/1620

나는야 포켓몬 마스터... 앞의 글은 다 무시하고 문제 부분만 읽으면 된다.

문자열 정렬에 관한 문제이다.

import bisect
n,m = map(int,raw_input().split())
pokemon = [raw_input() for i in xrange(n)]
sort_pokemon = sorted(pokemon)
pokemon_num = sorted([[pokemon[i],str(i+1)] for i in xrange(len(pokemon))], key=lambda x:x[0])

answer = ''
for i in xrange(m):
    name_or_num = raw_input()
    if name_or_num.isdigit():
        answer += pokemon[int(name_or_num)-1]+'\n'
    else:
        answer += pokemon_num[bisect.bisect(sort_pokemon, name_or_num)-1][1]+'\n'
print answer[:-1]

https://www.acmicpc.net/problem/1764

듣보잡문제. 별 설명이 필요 없다.

import bisect
n,m = map(int,raw_input().split())
hear = sorted([raw_input() for i in xrange(n)])

hear_see = []
for name in sorted([raw_input() for i in xrange(m)]):
    if hear[bisect.bisect(hear,name)-1]==name:
        hear_see.append(name)
print len(hear_see),'\n','\n'.join(hear_see)

https://www.acmicpc.net/problem/1181

word = list(set([raw_input() for i in xrange(int(raw_input()))]))
print '\n'.join(sorted(word, key=lambda x:(len(x),x)))