문제:

괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 '(' 와 ')' 만으로 구성되어 있는 문자열이다. 그 중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PsS,VPS)이라고 부른다. 한 쌍의 괄호 기호로 된 "()"문자열은 기본 VPS 이라고 부른다. 만일 x가 VPS 라면 이것을 하나의 괄호에 넣은 새로운 문자열 "(x)"도 VPS 가 된다. 그리고 두 VPS x 와 y를 접합(concatenation)시킨 새로운 문자열 xy도 VPS 가 된다. 예를 들어 "(())()"와 "((()))"는 VPS이지만 "(()(","(())()))", 그리고 "(()"는 모두 VPS 가 아닌 문자열이다.

여러분은 입력으로 주어진 괄호 문자열이 VPS인지 아닌지를 판단해서 그 결과를 YES 와 NO로 나타내어야 한다.

입력:

입력 데이터는 표준 입력을 사용한다. 입력은 T개의 테스트 테이터로 주어진다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 테이터의 첫째 줄에는 괄호 문자열이 한 줄에 주어진다 하나의 괄호 문자열의 길이는 2 이상 50이하이다.

출력:

출력은 표준 출력을 사용한다. 만일 입력 괄호 문자열이 올바른 괄호 문자열(VPS)이면 "YES", 아니면 "NO"를 한 줄에 하나씩 차례대로 출력해야 한다.

풀이 방법:

스택을 사용해서 "(" 를 만난다면 +1을 해주고 ")"을 만난다면 -1을 해주는 작업을 하도록 한다. 이렇게 괄호 문자열을 모두 탐색하고 난다면 VPS와 같은 경우에는 count가 0이 된다. 그렇지 않다면 0이 아닌 값이 나올 것이다. 하지만 ")("와 같은 경우 VPS가 아니지만 count의 값이 0이 되게 된다. 그래서 ")"를 먼저 만나서 count가 음수가 되는 경우 역시 올바르지 않은 경우이다. 이를 조절해주면 문제 없이 문제가 풀릴 것이다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
for i in range(int(input())):
    count=0
    for j in input():
        if count < 0:
            count=100
            break
        if j=="(":
            count+=1
        else:
            count-=1
    if count==0:
        print("YES")
    else:
        print("NO")
cs


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

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

[BOJ]1912. 연속합  (0) 2019.04.19
[BOJ]2504. 괄호의 값  (0) 2019.04.18
[BOJ]1874. 스택 수열  (0) 2019.04.16
[BOJ]10828. 스택  (0) 2019.04.15
[BOJ]4948.베르트랑 공준  (0) 2019.04.14

문제:

스택(stack)은 기본적인 자료구조 중 하나로, 컴퓨터 프로그램을 작성할 때 자주 이용되는 개념이다. 스택은 자료를 넣는 (push) 입구와 자료를 뽑는(pop) 입구가 같아 제일 나중에 들어간 자료가 제일 먼저 나오는 (LIFO,Last In First out) 특성을 가지고 있다.

1부터 n까지의 수를 스택에 넣었다가 뽑아 늘어놓음으로써, 하나의 수열을 만들 수 있다. 이때, 스택에 push하는 순서는 반드시 오름차순을 지키도록 한다고 하자. 임의의 수열이 주어졌을 때 스택을 이용해 그 수열을 만들 수 있는지 없는지, 있다면 어떤 순서로 push와 pop 연산을 수행해야 하는지를 알아낼 수 있다. 이를 계산하는 프로그램을 작성하라.

입력:

첫 줄에 n (1<=n<=100,000)이 주어진다. 둘때 줄부터 n개의 줄에는 수열을 이루는 1이상 n이하의 정수가 하나씩 순서대로 주어진다. 물론 같은 정수가 두 번 나오는 일은 없다.

출력:

입력된 수열을 만들기 위해 필요한 연산을 한 줄에 한 개씩 출력한다. push연산은 +로, pop 연산은 -로 표현하도록 한다. 불가능한 경우 NO를 출력한다.

풀이 방법:

문제를 풀기에 앞서서 문제를 이해를 하는 것조차 어려웠다. 1~n까지의 수가 있을 때 각 수를 스택 구조를 유지하는 배열에 넣었다가 빼면서 우리가 입력으로 넣은 수열을 만드는 것이 문제의 목표이다. 


 처음에는 while로 넣었다가 빼는 과정을 조절하려고 했으나 적절한 조건을 찾기 어려웠다. 그래서 예외처리 구문을 사용해서 빈 리스트에서 pop을 하려 할 때 오류가 발생해서 빠져나오도록 만들었다. 

 

 우선 입력으로 처음 넣은 값을 만들기 위해서 그 값까지 모든 값들을 계속 순차적으로 넣어야 한다. 그래서 맨 처음 i로 반복되는 for 반복문이 첫 원소를 만들기 위한 과정이다. 이후 j 반복문을 통해서 본격적으로 원하는 수열을 만들고자 한다. 일단 우선적으로 answer가 비어있다면 하나 추가를 하는 과정을 거친 뒤 stack인 answer 배열의 맨 윗 값이 원하는 값인지 비교를 하는 조건문을 만들었다. 만약 원하는 값이라면 -를 하고 그렇지 않다면 아직 answer에 들어가 있지 않은 것이라면 반복문 i처럼 계속넣어주면 되기 때문에 이번에는 while로 넣어주도록 한다. 그리고 다시 끝 값을 비교하고 빼도록 한다. 


하지만 j-for를 반복하면서 더하거나 빼는 작업을 한 번도 하지 않았다면 이 것은 문제가 생긴 경우 이므로 somethingtodo라는 부울 함수를 사용해 NO를 출력하도록 한다. (주로 빼야할 수가 이미 들어가 있을 경우 발생한다.)


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
34
35
36
37
38
39
40
41
n=int(input())
def sol(n):
    answer_list=[int(input()) for i in range(n)]
    answer=[]
    ans=[]
    k=0
    try:
        for i in range(1,answer_list[0]+1):
            k+=1
            answer.append(k)
            ans.append("+")
        for j in range(n):
            somethingtodo=False
            if len(answer)==0:
                k+=1
                answer.append(k)
                ans.append("+")
                somethingtodo=True
            if answer[-1]==answer_list[j]:
                answer.pop()
                ans.append('-')
                somethingtodo=True
            else:
                while answer_list[j]>answer[-1]:
                    k+=1
                    answer.append(k)
                    ans.append("+")
                    somethingtodo=True
                if answer[-1]==answer_list[j]:
                    answer.pop()
                    ans.append("-")
                    somethingtodo=True
            if somethingtodo:
                pass
            else:
                print("NO")
                return
        print(*ans,sep="\n")
    except:
        print("No")
sol(n)
cs


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

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

[BOJ]2504. 괄호의 값  (0) 2019.04.18
[BOJ]9012.괄호  (0) 2019.04.17
[BOJ]10828. 스택  (0) 2019.04.15
[BOJ]4948.베르트랑 공준  (0) 2019.04.14
[BOJ]1929. 소수 구하기  (0) 2019.04.13

문제:

정수를 저장하는 스택을 구현한 다음, 입력으로 주어지는 명령을 처리하는 프로그램을 작성하시오.

명령은 총 다섯 가지이다.

-push X: 정수 X를 스택에 넣는 연산이다.
-pop: 스택에서 가장 위에 있는 정수를 빼고, 그 수를 출력한다. 만약 스택에 들어있는 정수가 없는 경우에는 -1을 출력한다.
-size: 스택에 들어있는 정수의 개수를 출력한다.
-empty: 스택이 비어있으면 1, 아니면 0을 출력한다.
-top: 스택의 가장 위에 있는 정수를 출력한다. 만약 스택에 들어있는 정수가 없는 경우에는 -1을 출력한다.

입력:

첫째 줄에 주어지는 명령의 수 N(1<=N<=10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다.
주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 않은 명령이 주어지는 경우는 없다.

출력:

출력해야하는 명령이 주어질 때마다, 한 줄에 하나씩 출력한다.

풀이 방법:

python의 배열은 push와 pop이 스택과 동일하게 작동하므로 명령어가 들어오는 대로 수행해주면 문제 없이 통과 할 수 있다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
answer=[]
for i in range(int(input())):
    a=input().split()
    if a[0]=="push":
        answer.append(int(a[1]))
    elif a[0]=="top":
        if len(answer):
            print(answer[-1])
        else:
            print(-1)
    elif a[0]=="size":
        print(len(answer))
    elif a[0]=="empty":
        if len(answer):
            print(0)
        else:
            print(1)
    else:
        if len(answer):
            print(answer.pop())
        else:
            print(-1)
cs


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

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

[BOJ]9012.괄호  (0) 2019.04.17
[BOJ]1874. 스택 수열  (0) 2019.04.16
[BOJ]4948.베르트랑 공준  (0) 2019.04.14
[BOJ]1929. 소수 구하기  (0) 2019.04.13
[BOJ]1181. 단어정렬  (0) 2019.04.12

문제:

짝지어 제거하기는, 알파벳 소문자로 이루어진 문자열을 가지고 시작합니다. 먼저 문자열에서 같은 알파벳이 2개 붙어 있는 짝을 찾습니다. 그다음, 그 둘을 제거한 뒤, 앞뒤로 문자열을 이어 붙입니다. 이 과정을 반복해서 문자열을 모두 제거한다면 짝지어 제거하기가 종료됩니다. 문자열 S가 주어졌을 때, 짝지어 제거하기를 성공적으로 수행할 수 있는지 반환하는 함수를 완성해 주세요. 성공적으로 수행할 수 있으면 1을, 아닐 경우 0을 리턴해주면 됩니다.

예를 들어, 문자열 S=baabaa라면 

baabaa -> bbaa -> aa ->

의 순서로 문자열을 모두 제거할 수 있으므로 1을 반환합니다.

풀이 방법:

스택의 개념을 이용해서 풀었다. 문자열 s를 한 개씩 answer_list에 넣으면서 끝 두 값이 일치하면 제거하고 그렇지 않다면 유지한채로 다시 쌓는 방식이다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def solution(s):
    answer_list=[]
    s=list(s)
    idx=0
    while(idx!=len(s)):
        answer_list.append(s[idx])
        idx+=1
        if len(answer_list)>1:
            if (answer_list[-1]==answer_list[-2]):
                answer_list.pop()
                answer_list.pop()      
    if len(answer_list)==0:
        return 1
    else:
        return 0
cs


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

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

[Programmers]Lv 3. 숫자 게임  (0) 2019.03.23
[Programmers]Lv 2.JadenCase 문자열 만들기  (0) 2019.03.22
[Programmers]Lv 2.행렬의 곱셈  (0) 2019.03.20
[Programmers]Lv 3.최고의 집합  (0) 2019.03.19
[Programmers]Lv 2. 피보나치 수  (0) 2019.03.18

문제:

어떤 숫자에서 k개의 수를 제거했을 때 얻을 수 있는 가장 큰 숫자를 구하려 합니다.

예를 들어, 숫자 1924에서 수 두 개를 제거하면 [19,12,14,92,94,24] 를 만들 수 있습니다. 이 중 가장 큰 숫자는 94입니다.

문자열 형식으로 숫자 number와 제거할 수의 개수 k가 solution 함수를 매개변수로 주어집니다. number에서 k 개의 수를 제거 했을 때 만들 수 있는 수 중 가장 큰 숫자를 문자열 형태로 return 하도록 solution 함수를 완성하세요.

풀이 과정:

 단순히 number 중 작은 순으로 빼는 것이 아니라는 것을 마지막 예시 케이스 4177252841을 보면 알 수 있다. 따라서 이 문제는 탐욕법을 사용해서 풀어야 하는 문제이므로 문제 풀이를 생각하였다. 따라서 각 자리별로 한번씩 다 빼보아서(ex 1924의 경우 924, 124, 194, 192) 이 중 가장 큰 경우를 선택하도록 하였다. 대부분의 경우에 대해서 통과를 하지만 역시나 자릿수가 큰 경우에 시간초과가 발생하였다.
 그래서 탐욕법이 아닌 다른 방법도 생각해보았는데 스택을 활용해서 푸는 것이 효율적으로 할 수 있었다.

 숫자를 다음과 같은 규칙에 따라 스택을 쌓아가면 큰 수를 만들어 갈 수 있다.
  1. 하나의 값을 넣는다
  2. 맨 위에 쌓인 값과 그 바로 밑(맨 위에서 두번째 값)을 비교한다.
  3. 맨 위의 값이 더 클 경우 두 개의 값의 자리를 바꾸고 pop 해내서 빼낸다. 맨 위의 값이 작으면 다음 단계로 넘어간다
  4. 1~3을 k번 빼내거나, number를 다 쌓으면 끝낸다.

 다음은 예시 케이스 4177252841을 쌓는 과정을 나타냈다.


 

 

 

 

 

 

 

 

 

 

 1


 4

 비교 대상이 없어 통과한다.

 4

위 값이 작으므로  그냥 패스한다. 

 



 

 

 

 

 

 

 7

 

 

 

 

 

 1

 7을 쌓았을 때 자리를 

 7

 자리를 바꾼 후 1을 빼

 

 이 역시 7이 더 크므로

 4

바꾼다.

 4

 고 다시 4와 비교를 함

 7

 자리를 바꾸고 4를 뺌


이 작업을 반복해서 하면 큰 수를 만들 수 있다.


하지만 54321, k=1 와 같은 경우에는 하나도 빠지는 것 없이 54321 순으로 쌓이게 된다. 이 규칙으로 쌓았을 때 마지막으로 갈 수록 수가 작아지므로 뒤에서 부터 잘라서 사용하도록 한다.


우선 number가 string이므로 이를 list로 쪼개 하나씩 넣을 수 있도록 만들었다. 그리고 첫 수는 항상 넣고 시작하였다. 하나씩 넣으면서 Tos(Top of stack) 즉 지금 맨 위에 쌓인 부분의 인덱스를 하나씩 늘렸다. while 문이 규칙의 2,3번을 반복하는 과정이다. correct라는 변수는 4177252841와 같은 경우에 7을 넣을 때 두 번 연속 빼야하는데 이와 같은 행위를 하기 위해서 넣은 변수이다.

그리고 맨마지막에 54321 과 같은 경우를 해결하기 위해 뒤에서 부터 자르도록 하였다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def solution(number,k):
    number=list(number)
    answer=[number[0]]
    Tos=0
    for i in range(1,len(number)):
        answer.append(number[i])
        Tos+=1
        correct=1
        while (correct and k !=0):
            correct-=1
            for j in range(Tos,len(answer)):
                if answer[j-1]>=answer[j]:
                    pass
                else:
                    answer[j-1],answer[j]=answer[j],answer[j-1]
                    answer.pop()
                    correct+=1
                    Tos-=1
                    k-=1
                    break
    answer="".join(answer)
    return answer[:len(answer)-k]
cs



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

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

[Programmers]Lv 2. 소수 찾기  (0) 2019.02.14
[Programmers]Lv 1. 체육복  (0) 2019.02.13
[Programmers]Lv 1. K번째수  (0) 2019.02.11
[Programmers]Lv 2.더 맵게  (0) 2019.02.10
[Programmers]Lv 1.같은 숫자는 싫어  (0) 2019.02.09

문제:

 초 단위로 기록된 주식가격이 담긴 배열 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

문제:

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

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

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

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

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


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


(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

문제:

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

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

문제:

트럭 여러 대가 강을 가로지르는 일 차선 다리를 정해진 순으로 건너려 합니다. 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 알아내야 합니다. 트럭이 1초에 1만큼 움직이며, 다리 길이는 bridge_length이고 다리는 무게 weight까지 견딥니다.
solution 함수의 매개변수로 다리 길이 bridge_length, 다리가 견딜 수 있는 무게 weight, 트럭별 무게 truck_weights가 주어집니다. 이때 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 return 하도록 solution 함수를 완성하세요.

풀이 방법:

트럭이 다리를 지나가는 과정을 그리기 위해서 다리 위에 있는 트럭들을 나타내는 overing_truck, 다리를 건너간 트럭을 나타내는 overed_truck, overing_truck에서 overed_truck으로 넘기기 위한 timer 배열을 만들었다. 그리고 총 시간을 나타내는 answer를 만들었다.
트럭이 다리를 다 지나갈 때까지 반복해야하므로 overed_truck의 배열이 truck_weights와 같아 질 때까지 반복하는 while문을 사용하였다. 그리고 다음과 같은 과정을 반복하도록 하였다.

1. 앞으로 타야할 트럭의 무게와 지금 다리 위에 있는 트럭의 무게의 합이 weight보다 작다면 다리 위에 올리고 timer에 0값을 넣어준다.
2. 1초가 지난 뒤 timer의 값을 lambda 함수를 사용해서 1초 증가시킨다.
3. 만약 timer의 첫 값(0번째 인덱스)가 다리의 길이와 같아졌다면 그 값을 빼내 다리를 지난 배열에 넣어준다.

이 과정을 while문이 깨질 때까지 반복하여 answer를 리턴하도록 하였다. 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
def solution(bridge_length,weight,truck_weights):
    answer=0
    a=len(truck_weights)
    timer=[]
    overed_truck=[]
    overing_truck=[]
    while(len(overed_truck)!=a):
        answer+=1
        timer=list(map(lambda x: x+1,timer))
        if len(timer)>0:
            if timer[0]==bridge_length:
                timer.pop(0)
                b=overing_truck.pop(0)
                overed_truck.append(b)
        if len(truck_weights)>0:
            if sum(overing_truck)+truck_weights[0]<=weight:
                b=truck_weights.pop(0)
                overing_truck.append(b)
                timer.append(0)
    return answer
cs


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

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

[Programmers]Lv 2.프린터  (0) 2019.02.02
[Programmers]Lv 1.약수의 합  (0) 2019.02.01
[Programmers]Lv 1. 이상한 문자 만들기  (0) 2019.01.30
[Programmers]Lv 2. 기능개발  (0) 2019.01.29
[Programmers]Lv 1. 정수 내림차순으로 배열하기  (0) 2019.01.28

문제:

프로그래머스 팀에서는 기능 개선 작업을 수행 중입니다. 각 기능은 진도가 100%일 때 서비스에 반영할 수 있습니다.

또, 각 기능의 개발속도는 모두 다르기 때문에 뒤에 있는 기능이 앞에 있는 기능보다 먼저 개발될 수 있고, 이 때 뒤에 있는 기능은 앞에 있는 기능이 배포될 때 함께 배포됩니다.

먼저 배포되어야 하는 순서대로 작업의 진도가 적힌 정수 배열 progresses와 각 작업의 개발 속도가 적힌 정수 배열 speeds가 주어질 각 배포마다 몇 개의 기능이 배포되는지를 return 하도록 solution 함수를 완성하세요.

풀이 방법:

우선 각 기능마다 진도나 속도가 다르기 때문에 기능이 완성되는 날짜가 다르다. 따라서 이를 divmod를 사용해서 각 기능별로 완성이 되는 날짜 배열 complete를 만들었다.
 이후 이중반복문을 이용해서 답을 구하도록 하였다. 앞선 기능이 완성되는 날짜에 따라 배포 되는 작업이 달라진다. 예시처럼 첫 기능이 7일째에 완성이 되므로 다음 기능중 이보다 적게 걸리는 작업들은 7일과 함께 발표된다. 7일 보다 적게 걸리는 작업을 0으로 바꾸며 count를 하나씩 늘렸다. 왜냐하면 만약 적게 걸리는 작업을 제거해버린다면 반복문의 인덱스가 꼬여서 오류가 발생하기 때문이다. 이를 7일보다 많이 걸리는 작업(9일)을 만날 때까지 반복한다. 만나면 두번째 반복문을 break를 해버리고 count를 answer리스트에 추가한다. 이 반복문 작업을 마치고 나서 맨 끝 인덱스가 만약 0이 아니라면 그 작업은 따로 발표를 해야하므로 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
def solution(progresses, speeds):
    complete = []
    for i in range(len(progresses)):
        a,b=divmod(100-progresses[i],speeds[i])
        if b !=0:
            complete.append(a+1)
        else:
            complete.append(a)
    answer=[]
    for i in range(len(complete)-1):
        count=1
        if complete[i] !=0:
            for j in range(i+1,len(complete)):
                if complete[i] >=  complete[j]:
                    if complete[j]==0:
                        pass
                    else:
                        count+=1
                        complete[j]=0
                else:
                    break
            answer.append(count)
    if complete[-1] !=0:
        answer.append(1)
    return answer
cs


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

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

[Programmers]Lv 2. 다리를 지나는 트럭  (0) 2019.01.31
[Programmers]Lv 1. 이상한 문자 만들기  (0) 2019.01.30
[Programmers]Lv 1. 정수 내림차순으로 배열하기  (0) 2019.01.28
[Programmers]Lv 2. 124 나라의 숫자  (0) 2019.01.27
[Programmers]Lv 1. 정수 제곱근 판별  (0) 2019.01.26

+ Recent posts

티스토리툴바