[python] 코딩테스트 skill

자료구조란?

- 일련의 동일한 타입의 데이터를 정돈하여 저장한 구성체를 의미

- 프로그램에서 사용할 많은 데이터를 메모리 상에서 관리하는 여러가지 구현방법들

- 효율적인 자료구조가 성능 좋은 알고리즘의 기반이 됨

- 자료의 효율적인 관리는 프로그램의 수행속도와 밀접한 관련이 있음

- 데이터 정돈 목적은 프로그램에서 저장하는 데이터에 대해 탐색 , 삽입 , 삭제 등의 연산을 효율적으로 수행하기 위해서 이다. 

 

알고리즘이란?

- 문제를 해결하는 방법을 순서대로 명확하게 기술한 것

- 알고리즘의 각 단계는 정확히 한가지 의미로 해석되어야 한다.(명확성)

- 알고리즘의 모든 유효한 입력에 대해 올바른 해를 출력해야 한다.(정확성)

- 유효한 입력이 주어지면 반드시 유한한 시간 내에 종료되어야 한다.(정지성)

- 알고리즘의 성능은 수행 시간을 나타내는 시간복잡도와 알고리즘이 수행되는 동안 사용되는 메모리 공간의 크기를 나타내는 공간복잡도에 기반하여 분석한다.

 

1. sys.stdin.readline()

python 코딩테스트를 응시하기 위해서 필요한 입력 처리에 대해서 공부해볼것이다.

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

input()은 매우 느리다. 그렇기 때문에 코딩 테스트에서 수십만 건의 입력을 받아야 하는 상황이 온다면

timeout이 오는 경우가 있다. 그래서 python으로 입력이 많은 문제를 풀어야 할 때는, 사용자의 입력을 받는

버퍼를 만든 뒤, 그 버퍼에서 입력을 다시 읽어들이는 sys.stdin.readline() 함수를 이용한다

 

ex) 문자열을 입력받아 대문자는 소문자로 소문자는 대문자로 바꾸는 코드

# swapcase 함수 사용

import sys
input = sys.stdin.readline
N = int(input())
S = input().rstrip()
# swapcase()는 문자열의 대문자를 소문자로, 소문자를 대문자로 치환해준다.
print(S.swapcase())


# 반복문 사용

import sys
input = sys.stdin.readline
N = int(input())
S = input().rstrip()
# 결과 저장을 위한 변수
result = ''

# 반복문을 이용해서 현재의 철자가 소문자라면 대문자로, 대문자라면 소문자로 치환하기
for i in S:
	if i.islower():
		result += i.upper()
	elif i.isupper():
		result += i.lower()

print(result)

 

2. map(자료형,input(),split())

map() 함수는 python에서 여러 개의 정수를 한 번에 입력 받기 위해서 필요하기 때문이다.

N, M = map(int, input().split())
print(N, M)

map() 함수는 입력 이외에도 구현이나, 시뮬레이션을 할 때 유용하게 사용이 된다. 다양한 

알고리즘을 구현할 때 있어서 자주 사용되는 함수이기 때문에 사용법을 익혀두자.

 

ex) 단어 필터

import sys
input = sys.stdin.readline
N, M = map(int, input().split())
S = input().rstrip()
E = input().rstrip()

# 필터 단어 S가 메세지 E에 포함시 코드를 계속 실행
while S in E:
    # replace 메소드를 통해서 E에서 S 단어를 계속 삭제
    E = E.replace(S, '')
if E:
    print(E)
else:
    print("EMPTY")

 

3. eval()

 수식 연산에서 연산자 우선 순위를 구현하는 것은 일반적인 수식 연산과 다른 문제이다.

왜냐하면 우선순위를 고려하는 다양한 자료구조가 필요할 수 있기 때문이다.

하지만 python 에서는 이러한 걱정 없이 우선순위가 있는 수식을 편리하게 계산해주는 함수 ,

eval() 이 있다. 이 함수는 인자로 주어진 문자열이 수식이라면 수식의 결과를 반환해주는 함수이다.

A = "10*10-99"
B = "10-99*10"
print(eval(A))			# 1
print(eval(B))			# -980

4. replace()

python에서 replace() 함수는 왼쪽부터 해당하는 문자열을 찾아서 치환해주는 함수이다.  문자열 알고리즘 문제에서 특정문자를 주어진 문자로 대치하는 문제가 나올때 유용하게 사용할 수 있는 함수이다

 

ex) baekjoon - 1343

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

1343번: 폴리오미노

board = input()

board = board.replace("XXXX","AAAA")
board = board.replace("XX","BB")

if 'X' in board :
  print(-1)
else :
  print(board)

5.  ''. join()

코딩테스트에서 문자열을 합칠 떄는 문자열의 개수가 정말 적은 것이 아니라면 + 연산자를 사용하면 안된다. +를 사용할 경우 각각의 문자열을 새로운 메모리에 복사하여 새 문자열을 만들기 때문에 시간 복잡도가 O(n^2)가 된다. 따라서 ''.join()을 사용해야 빠르게 합칠 수 있다.

a = list(map(str,input().split()))
print(a)

result = ''.join(a)
print(result)


# input 
# a b c d 1 2 3
# output
# ['a', 'b', 'c', 'd', '1', '2', '3']
# abcd123