💻 🧐

분류 : 딕셔너리

표면적으로 딕셔너리를 사용해서 푸는 문제이지만, 두가지 해결해야 하는 이슈들이 더 있다.

1. Value 로 Key 값을 찾기.

2. input() 에서 발생하는 시간초과 문제 해결하기

keypoint : python input / value로 key 찾기 

code

import sys 
n,m = map(int,input().split(' '))

pocketmon_list = dict()
rev_poecketmon_list = dict()
cnt=1
for i in range(0,n):
    name = sys.stdin.readline().strip()
    pocketmon_list[str(cnt)] = name
    rev_poecketmon_list[name] = str(cnt)
    cnt+=1



for i in range(0,m):
    tmp_input = sys.stdin.readline().strip()
    if tmp_input.isdigit():
            print(pocketmon_list[tmp_input])
    else:
         print(rev_poecketmon_list[tmp_input])

중요한 내용 

1. Value 로 Key 찾기 

위 글을 참고하기 바란다. 결론은 value로 key 를 직접 찾는 것은 for 문을 사용한 완전탐색밖에 없다. 

2. 왜 input() 이 sys.stdin.readline().stirp() 보다 느릴까?

input() 함수는 Python 에서 기본적으로 제공하는 사용자 입력 함수인데 다음과 같은 특징을 갖고 있다.

1. 입력 된 값을 '문자열로 반환' 하고 '자동으로 개행 문자 제거' 를 한다.

2. 프롬프트 메시지를 인자로 받을 수 있다.

여기서 이 문자열로 변환하여 반환하고 자동으로 개행 문자를 제거하는게 물리적으로 시간이 대단히 오래걸린다.

그에 반해 readline() 함수는 개행 문자를 포함하여 문자열을 반환한다. 그렇기 때문에 그 시간 차이가 발생하는데 readline 함수에서는 strip() 을 사용하여 개행문자를 지울 수 있다. 

두 함수의 시간차이를 보여주는 함수이다.

import sys
import time

# sys.stdin.readline() 사용
start = time.time()
for _ in range(100000):
    line = sys.stdin.readline().strip()
end = time.time()
print(f'sys.stdin.readline() 사용 시간: {end - start}초')

# input() 사용
start = time.time()
for _ in range(100000):
    line = input()
end = time.time()
print(f'input() 사용 시간: {end - start}초')

100000줄의 입력을 처리하는 데 걸리는 시간:
input() 함수: 12.3456초
sys.stdin.readline() 함수: 0.4567초

결과값은 어마어마하게 차이가 난다. 따라서 python 에서 시간초과문제를 겪을 때 input 을 sys.stdin.readline().strip() 으로 변경해보자.

import sys
input = sys.stdin.readline().strip

이렇게 하면 코드변경 없이도 기존 input 함수에 적용하여 사용 할 수 있다.

분류 : 정렬

keypoint : python lambda, sort(key= )

code

# n 번의 숫자입력을 받습니다.
n = int(input()) 

# 좌표를 저장할 리스트
coor = []
for i in range(0,n):
    a,b = input().split(' ') 
    coor.append([int(a),int(b)])
    
    #리스트에 n 개의 좌표를 입력받는데
    #coor.append(list(map(int,input().split(' ')) 으로 대체할 수 있습니다.

#lambda 의 개념을 알아야 하는데 이건 아래에서 따로 다루겠습니다. 
coor.sort(key=lambda x: (x[1],x[0]))

for coord in coor:
    print(coord[0], coord[1])

lambda 

람다는 파이썬에서 중요하게 사용되는 함수입니다.

lambda 인자 : 표현식

람다는 다른 함수와 달리 def 로 선언하지 않고 인라인으로 선언하고 사용하여 사용할 수 있습니다.

예를들어 

def add(x, y):
	return x+y

라는 함수가 있다면 람다로 아래와 같이 표현할 수 있습니다.

add = lambda x, y: x+y

보통은 map 이나 sorted 와 같이 사용되게 되는데 이번 문제에서 활용한 것 처럼 sort 와 함께 사용해보겠습니다. 

 sort() 함수는 해당 리스트를 정렬하는데 사용됩니다. 이때 key 라는 인자를 활용 할 수 있는데 list 에서 key 를 사용하면 어떤 값을 기준으로 정렬할 것인지를 나타낼 수 있습니다.

my_list = ['apple', 'banana', 'cherry']

my_list.sort(key= lambda x: len(x))

라고 한다면  my_list 는 

['apple', 'cherry', 'banana']

로 저장됩니다. 이 처럼 key 를 사용하면 어떤 값을 통해 정렬할 것인지를 결정할 수 있다. 

우리 문제에서는

coor.sort(key=lambda x: (x[1],x[0]))

로 key 에 lambda 함수를 사용했는데 lambda x : x[1],x[0] 은 

def _key_function(x):
	return (x[1],x[0])

과 같다. 

즉 x[1] 과 x[0] 이 정렬 기준이라는 것인데, 이때 x[1] 기준으로 오름차순 정렬을 하고 만약 x[1] 값이 같다면 x[0] 을 기준으로 오름차순 정렬을 하게 된다.

이건 그냥 외우자! 

체스판 다시 칠하기 문제는 brute force 의 시작을 알려주는 문제인 것 같다.

문제정의

1. N*M 개의 정사각형으로 이루어진 보드가 주어진다.

2. 이 중에서 8*8 의 크기를 가진 체스판을 만드려고 한다.

3. 체스판은 한 정사각형이 검은색이라면 다른 정사각형은 흰색이 나와야한다.

4. N*M 개 중에서 임의로 8*8 크기의 보드를 꺼냈으니 (3) 을 어길 수 있다.

5. 그렇기 때문에 제대로 체스 판을 만들기 위해서 다시 색을 칠해야 하는 수를 구하는 프로그램을 작성해라.

아이디어

1. 체스판의 8*8 보드는 [0][0] 위치의 색이 검정색이거나 흰색인 경우 두가지이다. 따라서 아래처럼 이거나 아래의 색을 바꿔 [0][0] 이 흰색인 경우만 가능하다. 

2. 그렇다면 (1) 의 전제를 가지고  전체 M*N 의 보드의 [0][0] 부터 8by8 의 윈도우를 만들며 새로 색칠해야 하는 수를 계산하면 된다.

3. 새로 색칠해야 하는 수는 레퍼런스로 갖고 있는 보드와 얼마나 다른 색을 갖고 있는지를 확인하면 된다. 

    - (1) 에 레퍼런스로 갖고 있는 보드는 두가지 경우의 수만 가능하기 때문에 

for i in range(0,8):
	for j in range(0,8):

        if ref_board[i][j] == window_board[window_start_index+i][window_start_index+j]:
            cnt+=1
            
return min(cnt,64-cnt)

의 의사코드 정도로 해결 할 수 있을 것이다. 

전체코드

import sys
ref_board=[['W', 'B', 'W', 'B', 'W', 'B', 'W', 'B'],
       ['B', 'W', 'B', 'W', 'B', 'W', 'B', 'W'],
       ['W', 'B', 'W', 'B', 'W', 'B', 'W', 'B'],
       ['B', 'W', 'B', 'W', 'B', 'W', 'B', 'W'],
       ['W', 'B', 'W', 'B', 'W', 'B', 'W', 'B'],
       ['B', 'W', 'B', 'W', 'B', 'W', 'B', 'W'],
       ['W', 'B', 'W', 'B', 'W', 'B', 'W', 'B'],
       ['B', 'W', 'B', 'W', 'B', 'W', 'B', 'W']]
n, m = map(int, sys.stdin.readline().split())


whole_board = []

res=n*m

for _ in range(n):
    whole_board.append(list(sys.stdin.readline().strip('\n')))
    
def window(x, y):
    cnt=0
    for i in range(8):
        for j in range(8):
            if chess[i][j]==whole_board[x+i][y+j]:
                cnt+=1
    return min(cnt, 64-cnt)
for i in range(n-7):
    for j in range(m-7):
        res=min(res, window(i, j))
print(res)

왜 틀렸는지 정말 모르겠는 . .  문제였다. Python 을 주 언어로 하고 있지만, 나는 역시 제대로 알고 있는게 아닌가보다.

첫번째 시도. < 실패 > 

print(len(input().split(' ')))

두번째 시도. < 실패 >

string = list(input().split(' '))
if '' in string:
    string.remove('')
print(len(string))

세번째 시도. <실패>

string_list = map(str,input().split(' '))
string_list=list(string_list)
for string in string_list:
    if string == '' or string == ' ':
       # print("this is blank : ",string)
        string_list.remove(string)
print(len(string_list))

갈수록 길어지는, 코드들과 왜 틀렸는지를 알아보려고 했던 흔적들이 보인다. 

고민고민하다가. 메소드들을 다 파헤쳐보기 시작했다. 

그 중, List 의 Remove 함수의 치명적인 약점(?) 과 나의 대책없음이 드러났다.

https://docs.python.org/3/tutorial/datastructures.html

파이썬 공식 문서, List remove 는 Remove the first item from the list -

그러니까 remove 를 요청한 아이템중에서 가장 먼저 나오는 것을 삭제하는것이다. 

왜 remove 함수를 사용하면 리스트의 모든 아이템을 삭제해주는 것이라고 생각했을까... 참 바보같다고 생각이 든다.

그래서 결론은 리스트 내의 모든 공백과 null 을 없애주는 일을 해야한다. 

list comprehension 을 사용했다.

string = input()
word = [word for word in string.split(' ') if word]
print(len(word))

string = input()
check = [-1]*26
 
for i in range(len(string)):
	if check[ord(string[i])-97] == -1:
	    check[ord(string[i])-97] = i
        
for i in range(26):
    print(check[i], end=' ')

아스키코드를 활용해 간단하게 풀 수 있다.

문자를 아스키코드로 변환해주는 내장 메소드이다.

https://docs.python.org/3/library/functions.html#ord