문제:

매운 것을 좋아하는 Leo는 모든 음식의 스코빌 지수를 K 이상으로 만들고 싶습니다. 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 Leo는 스코빌 지수가 가장 낮은 두 개의 음식을 아래와 같이 특별한 방법으로 섞어 새로운 음식을 만듭니다.

섞은 음식의 스코빌 지수 = 가장 맵지 않은 음식의 스코빌 지수 + (두 번째로 맵지 않은 음식의 스코빌 지수 *2)

Leo는 모든 음식의 스코빌 지수가 K 이상이 될 때까지 반복하여 섞습니다.
Leo가 가진 음식의 스코빌 지수를 담은 배열 scoville과 원하는 스코빌 지수 K가 주어질 때, 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 섞어야 하는 최소 횟수를 return 하도록 solution 함수를 작성해주세요.

풀이 방법:

단순하게 scoville 배열을 정렬한 뒤에 첫 번째 인덱스값이 K보다 커지는 순간까지 섞는 과정을 반복하면 된다고 생각했다.
따라서 다음과 같이 코드를 작성할 수 있었다. 중간에 elif 조건으로 scoville 배열이 1인지 확인을 하였는데 이 경우에 더 이상 섞지 못하는 경우이기 때문에 -1을 반환하는 경우인 것이다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def solution(scoville,K):
    count=0
    while(True):
        scoville.sort()
        if scoville[0]>K:
            break
        elif len(scoville)==1:
            return -1
        else:
            count+=1
            a=scoville.pop(0)
            b=scoville.pop(0)
            scoville.append(a+2*b)
    return count
cs

 하지만 이 방법은 효율성 테스트에서 시간초과로 통과하지 못한다. 이 문제의 태그가 힙(heap)이므로 힙을 사용하도록 코드를 수정하였다.

힙이란 최댓값과 최솟값을 빠르게 찾아내기 위해 고안된 자료 구조로 완전이진트리로 구성되어 있다. 힙에는 최대 힙과 최소 힙 두 가지가 있다. 힙은 부모노드와 자식 노드와만 대소 관계가 존재하는데 부모 노드가 큰 경우가 최대 힙, 자식 노드가 큰 경우가 최소 힙이다.


 파이썬에서는 힙 구조를 구현할 수 있도록 모듈을 제공한다. import heapq 로 불러와서 사용을 한다. heapq는 부모 노드가 자식 노드보다 항상 작거나 같은 최소 힙을 제공한다. 따라서 가장 작은 요소가 0 인덱스를 가지며 pop을 했을 경우에 가장 작은 값이 나온다.


이번 문제를 해결하기 위해 heapq.heappush(heap,item)과 heapq.heappop(heap)을 사용했다.

heapq.heappush(heap,item)은 힙의 구조를 유지하면서 heap에 item을 넣는 것이고 heapq.heappop(heap)은 가장 작은 값을 반환하며 이 역시 힙의 구조를 유지한다. 따라서 위의 코드를 heap 구조를 유지하면서 해결하도록 수정하였다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
import heapq
def solution(scoville,K):
    count=0
    h=[]
    for i in scoville:
        heapq.heappush(h,i)
    while(True):
        if h[0]>=K:
            return count
        elif len(h)==1:
            return -1
        else:
            a=heapq.heappop(h)
            b=heapq.heappop(h)
            heapq.heappush(h,a+b*2)
            count+=1
cs


저작자표시 비영리 동일조건

'Algorithm > Python' 카테고리의 다른 글

[Programmers]Lv2. 큰 수 만들기  (0) 2019.02.12
[Programmers]Lv 1. K번째수  (0) 2019.02.11
[Programmers]Lv 1.같은 숫자는 싫어  (0) 2019.02.09
[Programmers]Lv 2.조이스틱  (2) 2019.02.08
[Programmers]Lv 1.문자열 내 마음대로 정렬하기  (0) 2019.02.07

문제:

배열 arr가 주어집니다. 배열 arr의 각 원소는 숫자 0부터 9까지로 이루어져 있습니다. 이때, 배열 arr에서 연속적으로 나타나는 숫자는 하나만 남기고 전부 제거하려고 합니다. 배열 arr에서 제거 되고 남은 수들을 return 하는 solution 함수를 완성해 주세요.단, 제거된 후 남은 수들을 반환할 때는 배열 arr의 원소들의 순서를 유지해야 합니다.

배열 arr에서 연속적으로 나타나는 숫자는 제거하고 남은 수들을 return 하는 solution 함수를 완성해 주세요.

풀이 방법:

반복문을 사용해서 연속되는 두 개 원소를 비교해 보아서 서로 달라지는 부분에서 원소를 answer에 담았다. 즉 예시에서 1,1 의 경우에는 pass로 지나가지만 1,3 구간에서는 1을 answer에 추가하게 되는 것이다.

1
2
3
4
5
6
7
8
9
def solution(arr):
    answer=[]
    for i in range(len(arr)-1):
        if arr[i]==arr[i+1]:
            pass
        else:
            answer.append(arr[i])
    answer.append(arr[-1])
    return answer
cs


저작자표시 비영리 동일조건

'Algorithm > Python' 카테고리의 다른 글

[Programmers]Lv 1. K번째수  (0) 2019.02.11
[Programmers]Lv 2.더 맵게  (0) 2019.02.10
[Programmers]Lv 2.조이스틱  (2) 2019.02.08
[Programmers]Lv 1.문자열 내 마음대로 정렬하기  (0) 2019.02.07
[Programmers]Lv 2.주식 가격  (0) 2019.02.06

문제:

조이스틱으로 알파벳 이름을 완성하세요. 맨 처음엔 A로만 이루어져 있습니다.
ex) 완성해야 하는 이름이 세 글자면 AAA, 네 글자면 AAAA

조이스틱을 각 방향으로 움직이면 아래와 같습니다.
▲ - 다음 알파벳
▼ - 이전 알파벳(A에서 아래쪽으로 이동하면 Z로)
◀ - 커서를 왼쪽으로 이동 (첫 번째 위치에서 왼쪽으로 이동하면 마지막 문자에 커서)
▶ - 커서를 오른쪽으로 이동

예를 들어 아래의 방법으로 "JAZ"를 만들 수 있습니다.

-첫 번째 위치에서 조이스틱을 위로 9번 조작하여 J를 완성합니다.
-조이스틱을 왼쪽으로 1번 조작하여 커서를 마지막 문자 위치로 이동시킵니다.
-마지막 위치에서 조이스틱을 아래로 1번 조작하여 Z를 완성합니다.
따라서 11번 이동시켜 "JAZ"를 만들 수 있고, 이 때가 최소 이동입니다.

만들고자 하는 이름 name이 매개변수로 주어질 때, 이름에 대해 조이스틱 조작 횟수의 최솟값을 return 하도록 solution 함수를 만드세요.

풀이방법:

이 조이스틱은 크게 두가지를 최적의 방법으로 정해야 한다.

첫번째는 문자의 이동이다. 위 방향키를 사용해서 원하는 문자로 이동을 할지 아래 방향키를 사용할지를 정해야 한다. 이것은 비교적 간단하다. 알파벳은 총 26자이므로 A에서 14번째에 존재하는 알파벳은 위 방향키보다 아래 방향키로 이동하는 것이 더 효율적이기 때문이다. 이는 아스키코드 함수인 ord를 사용해서 이동하고 그 차이만큼 answer에 더하도록 한다.

두번째는 위치의 이동이다. 문자 중 A가 존재한다면 문자를 이동시킬 필요가 없으므로 왼쪽으로 이동할지 오른쪽으로 이동할지 결정을 해야한다.
이는 하나의 반복을 이용해서 결정하도록 하였다. 방금 문자를 이동시킨 인덱스에서 오른쪽 문자와 왼쪽 문자 중 A가 아닌 것을 더 빨리 만나는 쪽으로 이동하도록 하였다. 파이썬의 인덱스는 음수로 가면 오른쪽 맨 끝으로 이동하기 때문에 1씩 빼는 과정에서 음수로 가도 문제가 없다.

이 두가지의 방법을 원하는 알파벳을 만들때까지 반복하도록 한다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
def solution(name):
    answer = 0
    name=list(name)
    base=["A"]*len(name)
    idx=0
    while(True):
        rightidx=1
        leftidx=1
        if name[idx]!="A":
            if ord(name[idx])-ord("A")>13:
                answer+=26-(ord(name[idx])-ord("A"))
            else:
                answer+=ord(name[idx])-ord("A")
            name[idx]="A"
        if name ==base:
            break
        else:
            for i in range(1,len(name)):
                if name[idx+i]=="A":
                    rightidx+=1
                else:
                    break
                if name[idx-i]=="A":
                    leftidx+=1
                else:
                    break
            if rightidx>leftidx:
                answer+=leftidx
                idx-=leftidx
            else:
                answer+=rightidx
                idx+=rightidx
    return answer
cs



저작자표시 비영리 동일조건

'Algorithm > Python' 카테고리의 다른 글

[Programmers]Lv 2.더 맵게  (0) 2019.02.10
[Programmers]Lv 1.같은 숫자는 싫어  (0) 2019.02.09
[Programmers]Lv 1.문자열 내 마음대로 정렬하기  (0) 2019.02.07
[Programmers]Lv 2.주식 가격  (0) 2019.02.06
[Programmers]Lv 1.소수 찾기  (0) 2019.02.05

문제:

문자열로 구성된 리스트 strings와, 정수 n이 주어졌을 때, 각 문자열의 인덱스 n번째 글자를 기준으로 오름차순 정렬하려 합니다. 예를 들어 strings가 [ "sun" , "bed" , "car" ]이고 n이 1이면 각 단어의 인덱스 1의 문자 "u", "e", "a"로 strings를 정렬합니다.

풀이 방법:

 sorted에 있는 key 조건을 사용해서 풀어야 하는 문제이다. sorted 함수는 sorted( iterable , key=None , reverse=False)로 구성되어 있는데, key에 조건을 설정해주면 그 조건에 따라서 iterable을 정렬 해 준다. 이 문제에서는 인덱스 n번째로 정렬을 하므로 lambda 함수를 사용하도록 한다. 같은 인덱스 1의 문자가 여럿일 수 있으므로 미리 한번 조건 없이 정렬한 뒤 키 값을 주어서 정렬을 하도록 한다.

1
2
3
def solution(strings, n):
    strings=sorted(strings)
    return sorted(strings, key = lambda x : x[n])
cs


저작자표시 비영리 동일조건

'Algorithm > Python' 카테고리의 다른 글

[Programmers]Lv 1.같은 숫자는 싫어  (0) 2019.02.09
[Programmers]Lv 2.조이스틱  (2) 2019.02.08
[Programmers]Lv 2.주식 가격  (0) 2019.02.06
[Programmers]Lv 1.소수 찾기  (0) 2019.02.05
[Programmers]Lv 2.쇠막대기  (0) 2019.02.04

문제:

 초 단위로 기록된 주식가격이 담긴 배열 prices가 매개변수로 주어질 때, 가격이 유지된 기간은 몇 초인지를 return 하도록 solution 함수를 완성하세요.

풀이방법:

스택/큐를 사용해서 풀어야 하는 문제인 것 같지만 딱히 스택/큐를 활용하지 않아도 쉽게 풀 수 있다. 이중반복문을 이용해서 떨어지기 전까지 계속 count를 증가시키고 떨어지는 순간 break를 걸어서 그 때까지의 count를 answer 배열에 넣어주면 된다.


1
2
3
4
5
6
7
8
9
10
11
12
def solution(prices):
    answer=[]
    for i in range(len(prices)):
        count=0
        for j in range(i+1,len(prices)):
            count+=1
            if prices[i] <= prices[j]:
                pass
            else:
                break
        answer.append(count)
    return answer
cs


저작자표시 비영리 동일조건

'Algorithm > Python' 카테고리의 다른 글

[Programmers]Lv 2.조이스틱  (2) 2019.02.08
[Programmers]Lv 1.문자열 내 마음대로 정렬하기  (0) 2019.02.07
[Programmers]Lv 1.소수 찾기  (0) 2019.02.05
[Programmers]Lv 2.쇠막대기  (0) 2019.02.04
[Programmers]Lv 1. 시저 암호  (0) 2019.02.03

문제:

1부터 입력받은 숫자 n 사이에 있는 소수의 개수를 반환하는 함수, solution을 만들어 보세요.

소수는 1과 자기 자신으로만 나누어지는 수를 의미합니다.
(1은 소수가 아닙니다.)

풀이 방법:

소수는 1과 자기 자신으로만 나누어지는 수이기 때문에 반복문을 사용해서 임의의 수 x가 소수인지 판별하는 방법은 2부터 x-1까지 나누어 보았을 때, 나머지가 생기지 않으면 된다. 따라서 다음과 같이 코드를 작성할 수 있다.

1
2
3
4
5
6
7
8
9
10
11
12
13
def solution(n):
    answer=[]
    cnt=1
    while(cnt!=n):
        cnt+=1
        prime=True
        for i in range(2,cnt):
            if cnt%i==0:
                prime=False
                break
        if prime:
            answer.append(cnt)
    return len(answer)
cs

하지만 이 방법은 효율적이지 못한 방법이라 큰 수의 경우에는 통과를 하지 못한다.



 그 이유는 2부터 x-1까지 검사하기 때문에 엄청 큰 소수 인 경우 x-1까지 반복해야하기 때문이다.

하지만 수학적으로 생각해보면 만약 어떤 수의 약수가 존재한다면 x-1까지 검사할 필요 없이 sqrt(x)까지만 검사를 해보아도 충분하다는 것을 알 수 있다.

따라서 위 코드를 다음과 같이 수정을 하였다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
def solution(n):
    import math
    answer=[2]
    cnt=1
    while(cnt!=n):
        cnt+=1
        prime=True
        for i in range(2,math.ceil(math.sqrt(cnt))+1):
            if cnt%i==0:
                prime=False
                break
        if prime:
            answer.append(cnt)
    return len(answer)
cs


math에 있는 루트 함수인 sqrt와 올림 함수인 ceil을 사용해서 범위를 잡아 주었다. 그러면 다음과 같이 큰 수의 경우에도 통과를 하는 것을 알 수 있다.



 하지만 이 방법이 소수를 판별하는 문제에서 최적의 효율을 나타내지는 않는다. 소수를 판별하는 문제에서 가장 효율이 좋은 코드는 '에라토스테네스의 체' 원리를 사용하는 것이다. 소수가 1과 자기 자신으로 나누어 지는 수라고 가정하면 소수가 아닌 수는 임의의 소수 하나로 나눌 수 있다는 말이 된다. 따라서 2부터 x-1까지 나누어보는 것이 아닌 소수 배열을 만들어서 임의의 소수로 나누어 지지 않는다면 소수가 된다는 것이다. 다음은 에라토스테네스의 체 원리를 이용해 작성한 코드다.


1
2
3
4
5
6
7
8
9
10
11
12
13
def solution(n):
    answer=[]
    for i in range(2,n+1):
        prime=True
        for j in answer:
            if i%j == 0:
                prime=False
                break
            elif j > i**(1/2):
                break
        if prime:
            answer.append(i)
    return len(answer)
cs

다음

다음과 같이 더 빨리 통과함을 알 수 있다. 효율성 테스트에서는 더 빨리 통과한다는 것을 체감할 수 있다.

 


저작자표시 비영리 동일조건

'Algorithm > Python' 카테고리의 다른 글

[Programmers]Lv 1.문자열 내 마음대로 정렬하기  (0) 2019.02.07
[Programmers]Lv 2.주식 가격  (0) 2019.02.06
[Programmers]Lv 2.쇠막대기  (0) 2019.02.04
[Programmers]Lv 1. 시저 암호  (0) 2019.02.03
[Programmers]Lv 2.프린터  (0) 2019.02.02

2019/01/12 - [Language/Python] - [Python 따라하기]1. Python 설치하기


서론:


 Python을 배우기에 앞서서 Python의 자료형들에 대해서 알아야 한다. 영어를 배우려면 알파벳을 먼저 알아야 하는 것처럼 프로그래밍 언어를 배우기 위해서는 자료형을 우선 알고 시작하는 것이 중요하기 때문이다. Python의 자료형들은 비교적 단순해서 이해하기 쉬운 편이다.

String(문자열)


 String(문자열)은 문자나 단어로 구성되어 있는 자료형이다. 다른 프로그래밍 언어에서는 " "로 둘러싸이면 string ' '로 둘러싸이면 char로 표현되는 것과는 달리 Python에서는 " ", ' ' 상관 없이 둘다 string으로 표현이 된다.


따라서 숫자를 " "나 ' '로 묶으면 int형이 아닌 string이 된다.



만약 장문의 글을 쓰게 되어서 여러 줄을 표현을 해야 하거나, 글 중에 인용구등이 포함이 되어 있는 글이라 " "와 ' ' 를 섞어서 사용해야 할 경우가 있다. 

그럴 경우 다음과 같이 작성을 하면 된다.



다른 자료형을 str()함수를 사용해서 문자열로 바꿀 수 있다.


문자열 연산


문자열은 다음과 같이 더하기와 곱셈 연산을 지원한다.


문자열 인덱싱과 슬라이싱


문자열의 인덱싱과 슬라이싱을 이용하면 문자열의 일부분만을 불러 낼 수 있고, 인덱싱과 슬라이싱은 반복 가능한 개체에서는 모두 사용가능하다.
인덱싱과 슬라이싱은 다음과 같이 사용한다.



m은 ' 를 포함하여 세번째 글자이지만 2로 인덱싱을 해야 접근 할 수 있다.

그 이유는 파이썬은 0부터 숫자를 세기 때문이다. 이 말은 문자열의 첫 번째 글자의 위치가 1이 아닌 0이라는 뜻이다. 따라서 맨 끝의 인덱스로 접근 하기 위해서는 문자열의 길이로 접근 하는 것이 아닌 문자열의 길이-1 로 접근을 해야한다. 문자열의 길이를 구하기 위해서 내장함수 len()을 사용하도록 한다.



만약 길이보다 더 큰 값을 넣거나 음수(-) 값으로 인덱싱을 하면 어떻게 될까??



길이보다 더 큰 값을 넣으면 IndexError가 발생하지만 음수(-)는 오류가 발생하지 않았다. a[-1]은 a[len(a)-1]과 같은 값을 얻었는데, 그 이유는 음수(-)에선 맨 끝에서부터 다시 인덱싱을 할 수 있기 때문이다. 하지만 음수값도 길이 이상을 벗어난다면 IndexError가 발생한다.


문자열 내장함수

문자 개수 세기(count)

문자열 내 한 글자나 구절이 몇개가 있는지 확인 할 수 있는 함수이다.


문자 위치 찾기(1번)

 찾는 문자의 인덱스를 반환해주며, 만약 존재하지 않는 문자를 찾는다면 오류가 발생한다.


문자 위치 찾기(2번)

내장 함수 index와 같은 역할을 하지만 index와 달리 존재하지 않는 문자를 찾으면 오류가 아닌 -1을 리턴한다.


문자 구성 확인하기

isdigit은 문자열이 숫자로만 구성되어 있는가 확인해주는 함수이며, 숫자로만 구성 되어 있으면 True, 하나라도 문자가 있으면 False이다.
isalph는 isdigit과 반대로 문자로만 구성되어있는지 확인해주는 함수이다.

대소문자 변환하기

capitalize는 문자열의 첫 글자를 대문자로 만들어 주는 함수다.
islower는 문자열이 소문자로만 구성되어 있는지 확인하는 함수이며, 맞으면 True 아니면 False를 리턴한다.
isupper는 문자열이 대문자로만 구성되어 있는지 확인하는 함수이며, 맞으면 True 아니면 False를 리턴한다.
upper는 문자열 전체를 대문자로 만드는 함수이고, lower는 문자열 전체를 소문자로 만드는 함수이다.
swapcase는 대문자를 소문자로 소문자를 대문자로 만드는 함수이다.


문자열 분리하기

str.split(sep)으로 사용하며 str을 sep으로 분리하는 함수이다. 보통 " " 공백(띄어쓰기)를 기준으로 분리를 한다. 받는 변수가 없으면 리스트 값으로 분리를 한다.

문자열 붙이기

str.join(iterable) join은 반복가능(iterable)한 자료 사이에 str 값을 넣어주는 함수이다. 하지만 보통 str부분에 ""을 넣어서 문자열을 붙여주는 용도로 사용한다.



Int,Float(정수형, 실수형)

 int는 정수형(integer)를 뜻하고 Float는 소수점이 포함이 된 숫자(Floating-point)를 뜻한다.



Float 형으로 변환하기 위해서는 float()를 사용하고, int형으로 변환하기 위해서 int()를 사용한다. 소주점이 포함된 숫자에 int()를 사용하면 소수점 부분을 버린다.



사칙연산

숫자형과 평소에 알고 있는 연산자( +, - ,* ,/)를 사용해서 사칙연산을 할 수 있다.




 이 외에도 제곱(**), 나머지(%), 몫(//)을 수행하는 사칙 연산이 있다.



Python에서는 사칙연산을 축약하여 사용할 수 있으며, 내장함수나 라이브러리를 통해서 많은 연산을 지원해준다.


위의 사칙 연산을 다음과 같이 축약 할 수 있다.


round(반올림)

round(numbers,ndigits)로 사용 한다. 수(number)를 소숫점 ndigits번째 자리까지 나타내도록 ndigits + 1 번째에서 반올림을 하는 함수이다. ndigits의 고정값(default)은 0으로 고정되어있다.

하지만 .5 와 같은 경우에는 일반적으로 알고 있는 반올림 연산을 따르지 않는 경우가 생기는데, 그 이유는 컴퓨터에서 소숫점을 표현하는 방식 때문이다.
(ex 4.5 == 4.44444444449와 같이 표현이 되기 때문)


pow(제곱)

pow(x,y,z)로 사용을 한다. (x**y)%z 와 같은 연산을 한다. z의 고정값(default) 값이 None으로 되어 있어 값을 주지 않으면 나머지 연산은 하지 않는다.

import math

다음은 수학연산을 지원하는 내장 라이브러리인 math이다. import math로 불러오며 다양한 수학 연산을 지원한다. 연산자는 다음 링크에서 확인 할 수 있다.


List(배열)

List는 배열 자료형이며 여러 개의 자료형을 담는 역할을 한다. List는 다음과 같이 표현이 되며 문자열(string)과 같이 인덱싱과 슬라이싱이 가능하다


List 안에 List를 사용하는 것을 2중 배열문이라고 하는데 행렬을 표현하고자 할 때 주로 많이 사용한다. 2중 배열문은 다음과 같이 인덱싱을 한다.



List 역시 string과 동일하게 덧셈과 곱셈 연산을 지원한다.



List는 String과 비슷한 기능을 지원하지만 값을 수정 할 수 있다는 점은 다르다.


리스트 내장함수

요소 값 추가하기(1)

list.append(x)를 사용하면 list에 x의 값을 list의 끝에 추가하는 작업을 수행한다.

요소 값 추가하기(2)

append는 항상 list의 맨 끝에 넣는다는 점을 보완하기 위해서 사용한다. insert(a,b)는 a번째 위치에 b를 넣는 작업을 수행한다.

요소 값 제거하기(1)

list.pop()을 사용하면 list의 끝 값을 제거하는 작업을 수행하며, .pop(a)로 사용하면 list의 a번째 위치의 값을 제거한다.

요소 값 제거하기(2)

list.remove(x)를 사용하면 첫 번 째로 나오는 x의 값을 제거하는 작업을 수행한다.

요소 값 정렬하기(1)

list.sort()를 사용하면 list를 오름차순으로 정렬한다.

요소 값 정렬하기(2)

sorted(iterable,key=None,reverse=False)는 정렬함수이면서 다양한 기능을 제공한다. sort()는 리스트 자체를 정렬시키면서 반환값이 없지만, sorted는 반환값으로 제공하기 때문에 정렬 전의 상태와 정렬 후의 상태가 동시에 필요할 때 사용한다. 또한 reverse=True로 조건을 켜두면 오름차순이 아닌 내림차순으로 정렬을 하며 key 값을 넣어주면 key를 기준으로 정렬을 한다.

요소 값 뒤집기

reverse는 리스트 전체를 뒤집는 작업을 한다. 내림차순으로 정렬을 하는 것이 아닌 단순히 리스트를 뒤집는 일만 한다.

요소 값 위치 찾기

index(x,a,b)를 사용하면 list 내 a이상 b미만의 인덱스에서 x가 처음 나타는 위치 값을 반환한다. 고정값으로 a는 시작점으로, b는 마지막 점으로 설정 되어 있다.

요소 값 세기

count(x)를 사용하면 list 내 x의 갯수를 세서 반환을 해준다.


저작자표시 비영리 동일조건

'Language > Python' 카테고리의 다른 글

[Python 따라하기] 6. 함수만들기(def, print, format)  (0) 2019.03.05
[Python 따라하기]5. 반복문(For, While, break, continue)  (0) 2019.02.26
[Python 따라하기]4.조건문  (0) 2019.02.19
[Python 따라하기]3. 자료형_part2(Tuple,Set,Dictionary)  (0) 2019.02.12
[Python 따라하기]1. Python 설치하기  (0) 2019.01.29

문제:

여러 개의 쇠막대기를 레이저로 절단하려고 합니다. 효율적인 작업을 위해서 쇠막대기를 아래에서 위로 겹쳐 놓고, 레이저를 위에서 수직으로 발사하여 쇠막대기들을 자릅니다. 쇠막대기와 레이저의 배치는 다음 조건을 만족합니다.

-쇠막대기는 자신보다 긴 쇠막대기 위에만 놓일 수 있습니다.

-쇠막대기를 다른 쇠막대기 위에 놓는 경우 완전히 포함되도록 놓되, 끝점은 겹치지 않도록 놓습니다.

-각 쇠막대기를 자르는 레이저는 적어도 하나 존재합니다.

-레이저는 어떤 쇠막대기의 양 끝점과도 겹치지 않습니다.


이러한 레이저와 쇠막대기의 배치는 다음과 같이 괄호를 이용하여 왼쪽부터 순서대로 표현할 수 있습니다.


(a) 레이저는 여는 괄호와 닫는 괄호의 인접한 쌍 '()'으로 표현합니다. 또한 모든 '()'는 반드시 레이저를 표현합니다.

(b) 쇠막대기의 왼쪽 끝은 여는 괄호 '('로, 오른쪽 끝은 닫힌 괄호 ')'로 표현됩니다.


쇠막대기와 레이저의 배치를 표현한 문자열 arrangement가 매개변수로 주어질 때, 잘린 쇠막대기 조각의 총 개수를 return 하도록 solution 함수를 작성해주세요.


풀이 방법:

 이 문제에서 막대기가 갈라지는 경우는 레이저로 자르는 것 이외에도 쌓인 막대기가 달라져서 생길 수 있다. 
'('는 막대기가 쌓인다는 의미이고 ')'는 막대기가 사라진다는 의미로 생각을 해야한다. 따라서 '(' 일 때 stack 값을 1 증가시키고 ')' 일 때는 감소 시키도록 한다.
또한 ')' 이전에 '('가 있었으면 레이저의 의미이고, ')'가 있었다면 막대기의 층이 달라진다는 의미이다. 따라서 이를 위해 cut 라는 bool 값을 추가했다.
 


첫 레이저에서는 쌓인 막대기가 없어서 생긴 조각이 없다. 하지만 두번째 레이저에서는 '(' 가 4개 ')'개 인 것이므로 3개의 조각이 생긴다. (현재 stack=3)



세번째 레이저에서는 3개의 stack이 유지 중에 '('를 1번 ')'를 1번이 있었으므로 이번에도 3개의 조각이 생긴다. (현재 stack=3)



')'가 두 번 연속 반복된 상황이다. 따라서 stack을 1 줄이면서 1개의 조각을 더 추가시킨다. (현재 stack=2)



네번째 레이져까지 도달할 때까지 stack 2에서 '('를 2번 ')'를 한 번 만나서 3개의 조각이 생기게 된다. (현재 stack=3)



')'가 두 번 연속 반복된 상황이다. 따라서 stack을 1 줄이면서 1개의 조각을 더 추가시킨다. (현재 stack=2)



다섯번째 레이저를 만나기까지 '(' 한 번 ')' 한 번씩 만났다 따라서 2개의 조각이 생기게 된다. (현재 stack=2)



')'가 세 번 연속 반복된 상황이다. 따라서 stack을 1씩 두 번  줄이면서 1개의 조각씩을 더 추가시킨다. (현재 stack=0)



여섯번째 레이저를 만나기까지 '(' 두 번 ')' 한 번을 만나면서 1개의 조각이 생긴다. (현재 stack =1)



')'가 두 번 연속 반복된 상황이다. 따라서 stack을 1 줄이면서 1개의 조각을 더 추가시킨다. (현재 stack=0)


이렇게 쇠막대기를 잘라나가면 답을 얻을 수 있게 될 것이다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def solution(arrangement):
    stack=0
    answer=0
    for i in arrangement:
        if i=="(":
            stack+=1
            cut=True
        else:
            stack-=1
            if cut:
                answer+=stack
                cut=False
            else:
                answer+=1
    return answer
cs




저작자표시 비영리 동일조건

'Algorithm > Python' 카테고리의 다른 글

[Programmers]Lv 2.주식 가격  (0) 2019.02.06
[Programmers]Lv 1.소수 찾기  (0) 2019.02.05
[Programmers]Lv 1. 시저 암호  (0) 2019.02.03
[Programmers]Lv 2.프린터  (0) 2019.02.02
[Programmers]Lv 1.약수의 합  (0) 2019.02.01

문제:

어떤 문장의 각 알파벳을 일정한 거리만큼 밀어서 다른 알파벳으로 바꾸는 암호화방식을 시저 암호라고 합니다. 예를 들어 "AB"는 1만큼 밀면 "BC"가 되고, 3만큼 밀면 "DE"가 됩니다. "z"는 1만큼 밀면 "a"가 됩니다. 문자열 s와 거리 n을 입력받아 s를 n만큼 민 암호문을 만드는 함수, solution을 완성해 보세요.

풀이 방법:

Python의 내장함수는 ord()와 chr()를 사용하는 문제이다. s를 반복문으로 돌려서 각 자리가 소문자, 대문자, 공백인지 확인한다.
이후 chr(((ord(i)-ord('a'))+n)%26+ord('a')) 이와 같이 시저 암호를 만든다.

1
2
3
4
5
6
7
8
9
10
def solution(s, n):
    answer = ''
    for i in s:
        if i.islower():
            answer+=chr(((ord(i)-ord('a'))+n)%26+ord('a'))
        elif i.isupper():
            answer+=chr(((ord(i)-ord('A'))+n)%26+ord('A'))
        else:
            answer+=' '
    return answer
cs


저작자표시 비영리 동일조건

'Algorithm > Python' 카테고리의 다른 글

[Programmers]Lv 1.소수 찾기  (0) 2019.02.05
[Programmers]Lv 2.쇠막대기  (0) 2019.02.04
[Programmers]Lv 2.프린터  (0) 2019.02.02
[Programmers]Lv 1.약수의 합  (0) 2019.02.01
[Programmers]Lv 2. 다리를 지나는 트럭  (0) 2019.01.31

문제:

일반적인 프린터는 인쇄 요청이 들어온 순서대로 인쇄합니다. 그렇기 때문에 중요한 문서가 나중에 인쇄될 수 있습니다. 이런 문제를 보완하기 위해 중요도가 높은 문서를 먼저 인쇄하는 프린터를 개발했습니다. 이 새롭게 개발한 프린터는 아래와 같은 방식으로 인쇄 작업을 수행합니다.

1.인쇄 대기목록의 가장 앞에 있는 문서(J)를 대기목록에서 꺼냅니다.
2.나머지 인쇄 대기목록에서 J보다 중요도가 높은 문서가 한 개라도 존재하면 J를 대기목록의 가장 마지막에 넣습니다.
3.그렇지 않으면 J를 인쇄합니다.

예를 들어, 4개의 문서(A,B,C,D)가 순서대로 인쇄 대기목록에 있고 중요도가 2 1 3 2 라면 C D A B 순으로 인쇄하게 됩니다.

내가 인쇄를 요청한 문서가 몇 번째로 인쇄되는지 알고 싶습니다. 위의 예에서 C는 1번째로, A는 3번째로 인쇄됩니다.

현재 대기목록에 있는 문서의 중요도가 순서대로 담긴 배열 priorities와 내가 인쇄를 요청한 문서가 현재 대기목록의 어떤 위치에 있는지를 알려주는 location이 매개변수로 주어질 때, 내가 인쇄를 요청한 문서가 몇 번째로 인쇄되는지 return 하도록 solution 함수를 작성해주세요.

풀이 방법:

내가 인쇄를 요청한 문서의 중요도가 2라고 할 때 2의 중요도가 여러 개가 있다면 이 프린터를 이용했을 때 내가 요청한 문서를 찾을 수가 없다.
따라서 프린터에 넣기 전에 1.0을 곱해서 다른 값들이 int 값을 가질 때 내가 요청한 문서는 float 값을 가지도록 하였다.
이후 인쇄 된 배열인 answer_list에 이 프린터의 기능에 따라 하나씩 넣었다. 
전부 인쇄 한 뒤 answer_list에서 float형인 값을 찾아 그 인덱스를 반환하였다.(단, 이 문제에서 1번째가 0이 아닌 1이므로 1을 더해서 반환한다.)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def solution(priorities, location):
    answer_list=[]
    priorities[location]*=1.0
    key=priorities[location]
    while(len(priorities)!=1):
        a=priorities.pop(0)
        if a < max (priorities):
            priorities.append(a)
        else:
            answer_list.append(a)
    answer_list.append(priorities.pop(0))
    for i in range(len(answer_list)):
        if type(answer_list[i]) !=float:
            pass
        else:
            answer = i
    return answer+1
cs



저작자표시 비영리 동일조건

'Algorithm > Python' 카테고리의 다른 글

[Programmers]Lv 2.쇠막대기  (0) 2019.02.04
[Programmers]Lv 1. 시저 암호  (0) 2019.02.03
[Programmers]Lv 1.약수의 합  (0) 2019.02.01
[Programmers]Lv 2. 다리를 지나는 트럭  (0) 2019.01.31
[Programmers]Lv 1. 이상한 문자 만들기  (0) 2019.01.30

+ Recent posts

티스토리툴바