01. 배열과 문자열

문제 1.3

URL화 : 문자열에 들어 있는 모든 공백을 '%20'으로 바꿔 주는 메서드를 작성하라. 최종적으로 모든 문자를 다 담을 수 있을 만큼 충분한 공간이 이미 확보되어 있으며 문자열의 최종 길이가 함께 주어진다고 가정해도 된다.

풀어보기

1. 문자열 순회하면서 이어붙이기

단순하게 문자열을 하나씩 확인하며 공백일 때는 '%20', 공백이 아닐 때는 기존 문자열을 덧붙여서 새로운 결과 문자열을 만들어 리턴한다.

# 1.3 URL화
s = "Mr John Smith"

def toURL(str):
    newS = ""
    for x in s:
        if x == ' ':
            newS += "%20"
        else:
            newS += x
    return newS

print(toURL(s))

# -결과----------------------------------------------------------------------------------
# Mr%20John%20Smith

수정된 풀이(하나의 문자열로 편집하여 리턴)

# 1.3 URL화
s = "Mr John Smith"

def toURL(str):
    n = len(str)

    # 마지막 부터 첫번째까지 순회
    for i in range(len(str)-1, 0-1, -1):
        if str[i] == ' ':
            str = str[:i] + "%20" + str[i+1:]

    return str

print(toURL(s))
# -결과----------------------------------------------------------------------------------
# Mr%20John%20Smith

해답

문제에 정확히 나오지 않았지만 주의해야할 사항은 이 문제는 새로운 문자열을 만들어 변환 하는 것이 아니라, 기존의 문자열을 가지고 조작하여 풀어야 하는 문제!

따라서 문자열을 앞에서 부터 편집하는 것이 아니라, 뒤에서 부터 편집한다. 앞에서 부터 편집하면 아직 편집해야 할 문자가 덮어쓰여질 우려가 있기 때문이다.

1. 공백의 갯수를 세고, 문자열을 뒤에서부터 거꾸로 편집하며 복사해나간다. 

void replaceSpaces(char [] str, int trueLength){    // truelength는 주어진 문자열의 길이
    int spaceCount = 0, index, i = 0;
    for (i = 0; i < trueLength; i++){
        if (srt[i] == ' '){
            spaceCount++;        // 공백의 숫자를 센다
        }
    }

    index = trueLength + spaceCount * 2; // 문자열의 길이에다가 URL화로 인해 치환될 문자열의 길이를 더한 값이 index

    if (trueLength < str.length){ // 만약 주어진 문자열의 길이가 실제 문자열의 길이보다 작다면 중간에 종료
        str[trueLength] = '\0'
    }
    // str[trueLength] -> str[index] 로 문자열 복사
    for (i = trueLength - 1; i>=0; i--){
        if (str[i] == ' '){
            str[index - 1] == '0';
            str[index - 2] == '2';
            str[index - 3] == '%';
            index = index-3;
        }
        else{
            str[index - 1] = str[i];
            Index--;
        }
    }
}

문제 설명

1. N 개의 정수를 가진 리스트 A와 정수 K가 입력으로 주어진다.
2. 문제의 목표는 A리스트를 K번 회전한 결과 리스트를 리턴하는 것.
3. 회전이란 리스트의 모든 요소가 하나씩 오른쪽으로 이동하는 것을 말한다(마지막 요소는 첫번째로 이동)

풀면서 주의할 점은 예외케이스를 놓치지 않는 것이다. 

입력으로 빈 리스트가 주어지거나 

리스트는 입력 됬는데 회전 횟수가 0으로 입력되는 경우를 처음에 생각못해서 헤맸다...  

 you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")

def solution(A, K):
    # write your code in Python 3.6
    if len(A) == 0:	## 빈 리스트가 입력으로 들어올 수 있다.
        return []
    if K == 0:		## 리스트만 입력되고 회전 수가 0으로 주어질 수 있다.
        return A
        
    while K > 0:
        
        result = []
        for i in range(len(A)):
            if i == 0:
                result.append(A[-1])
            else:
                result.append(A[i-1])
        A = result
        K -= 1
    return result
    pass

Codility 사이트에서 문제를 풀어보았다.

영어로 된 문제에 처음부터 당황..

하지만 수많은 예시들 덕분에 이해하는데 어렵진 않았다.

파이썬 알고리즘 공부를 하면서 여러가지 유용하고, 헷갈리는 문법들 정리

#1 시간, 공간 복잡도 관련 팁

알고리즘 수행시간을 알아보기 위한 코드

import time
start_time = time.time()

# 프로그램 작성

end_time = time.time()
print("time :", end_time - start_time)

- pypy3는 파이썬3의 문법을 그대로 지원하며, 대부분 파이썬3보다 실행 속도가 더 빠르다. Pypy3를 지원하는 환경이라면 속도를 줄이기 위해 이를 이용하도록 하자

- 기업코딩 테스트 환경에서는 파이썬으로 제출한 코드가 1초에 2000만번 연산을 수행한다고 가정하면 크게 무리가 없다.

- 시간제한이 1초인 문제를 만났을 경우 (참고만 하세요)

- 일반적으로 탐색해야할 전체 데이터의 개수가 100만개 이하일 때 완전탐색을 사용하면 적절하다.

- 정수형 자료형 데이터의 개수에 따른 메모리 사용량

#2 입출력

공백을 기준으로 입력받기

# 3 3 3     <-- 변수로 저장
n, m, k = map(int, input().split())

# 2 4 5 2 3 <-- 배열로 저장
data = list(map(int, input().split()))

2차원 배열 입력받기

data = []
for i in range(n):
    # 데이터가 공백없는 형태로 입력될 때
    # 12345 --> [1, 2, 3, 4, 5]
    data.append(list(map(int, input())))
    
    # 데이터가 공백을 두고 입력될 떄
    # 1 2 3 4 5 --> [1, 2, 3, 4, 5]
    data.append(list(map(int, input().split())))

빠르게 입력받기 (일반적인 입력 방식보다 더 효율적)

import sys

data = sys.stdin.readline().rstrip()

f-string (더 간결하게 여러 자료형을 한 줄로 출력할 수 있음)

num = 7
print(f"정답은 {num}입니다.")

#3 정렬

#0 내림차순 정렬
B.sort(reverse=True) # 내림차순정렬

#1 튜플리스트, 2차원리스트일 경우 여러 가지 기준으로 정렬하기.
s_list.sort(key = lambda x : (-x[1], x[2], -x[3], x[0]))

#2 튜플에 숫자형과 문자형이 섞여있을 경우 숫자형에 int()를 씌워주면
# bad operand type for unary -: 'str' 이슈를 해결할 수 있다
s_list.sort(key = lambda x : (-int(x[1]), int(x[2]), -int(x[3]), x[0] ))

#3 리스트에서 median 값 구하는 식
data[(n-1) // 2] # n은 리스트 길이

#4 sorted with key
array = [('홍길동', 35), ('이순신', 75), ('아무개', 50)]
result = sorted(array, key = lambda x: x[1])
# 성적을 기준으로 오름차순정렬


#5 문자열, 배열, 튜플 등을 역순으로 출력(간결하게)
s = 'abcde'
print(s[::-1])  # 'edcba'
print(s[3:0:-1])  # dcba, 0~3인덱스를 역순으로

l = ['a', 'b', 'c', 'd', 'e']
print(l[::-1])  # ['e', 'd', 'c', 'b', 'a']
t = ('a', 'b', 'c', 'd', 'e')
print(t[::-1])  # ('e', 'd', 'c', 'b', 'a')

#4 문자열, 배열 다루기

파이썬 문자열 아스키변환

주요 아스키 코드값 0 ~ 9 : 48 ~ 57 , A ~ Z : 65 ~ 90, a ~ z : 97 ~ 122

ord('a') ## 아스키코드 숫자 반환
chr(ord('a')) ## 아스키코드에 해당하는 문자 반환

크기가 N이고 모든 값이 0인 리스트 초기화

N = 10
arr = [0] * N

1부터 10까지 증가하는 리스트 초기화

array = [i for i in range(1, 11)]

2차원 배열 좌표 이동

## 풀이 - 좀더 간단한 코드로

n = int(input())
x, y = 1,1
plans = input().split()

## L, R, U, D
dx = [0, 0, -1, 1]
dy = [-1,1,  0, 0]
move = ['L', 'R', 'U', 'D']

for plan in plans:
    for i in range(len(move)):
        if plan == move[i]:
            nx = x + dx[i]
            ny = y + dy[i]
    if nx < 1 or ny < 1 or nx > n or ny > n:
        continue
    x, y = nx, ny
print(x, y)

2차원 배열 90도 회전

n = len(a) # 행 길이 계산
m = len(a[0]) # 열 길이 계산
result = [[0] * n for _ in range(m)]
after = [] # 90도 회전된 배열 저장

# 시계방향으로 회전
for i in range(n):
	tmp = []
	for j in range(m):
    	tmp.append(before[m-1-j][i])
    after.append(tmp)
    
# 반시계방향으로 회전
for i in range(m):
    tmp  = []
    for j in range(n):
    	tmp.append(before[j][m-1-i]) #반시계

    after.append(tmp)

#5 자료형

- 1e9, 1E9 는 10의 9제곱과 같다.

- 임의의 큰 수를 표현하기 위해 자주 표현되는 형식

# 실수형의 계산은 정확하게 떨어지지 않는다.
# 반올림해서 사용하는 것을 습관화하자

if 0.3 + 0.6 == 0.9:
	print(True)
else:
	print(False)

# --> False

- 튜플은 한 번 선언되면 변경할 수 없다.

- 튜플은 리스트에 비해 공간 효율적이다.

#6 내장함수 및 라이브러리

eval() : 문자열로 표현된 수식의 계산 결과값을 반환

result = eval("(3+5)*7")
# --> 56

순열과 조합

# 순열 : 주어진 데이터를 가지고 서로 다른 n 개를 선택하여 일렬로 나열하는 것 
from itetools import permutations

data = [1, 4, 5, 6, 7]
result = list(permutations(data,3))

# 조합 : 주어진 데이터를 가지고 서로 다른 n 개를 선택하는 것 
from itetools import combinations

data = [1, 4, 5, 6, 7]
result = list(combinations(data,3))

Counter : 원소의 등장 횟수를 간단히 셀 수 있다, 원소와 등장 횟수를 사전 형태로 저장할 수 있다.

from collections import Counter

counter = Counter(['red', 'blue', 'green'])
print(dict(counter))

# --> {'red' : 1, 'blue' : 1, 'green' : 1}