728x90
반응형

문제:

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N()<=N<=100,000)에 있고, 동생은 점 K(0<=K<=100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다.

 

수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.

 

입력:

첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다.

 

출력:

수빈이가 동생을 찾는 가장 빠른 시간을 출력한다.

 

풀이 방법:

 여러 행위를 할 수 있는데 가장 빠른 방법을 찾는 문제는 대부분 BFS로 풀리는 경우가 많다. 따라서 이 문제도 X-1, X+1, 2X로 이동할 수 있는데 가장 빠른 시간을 찾기 때문에 BFS로 풀어야 한다.

 한 layer마다 Queue의 값에 따라 이동할 수 있는 위치를 새로 queue에 넣는다. 이 과정을 반복하다가 원하는 위치로 이동했다면(dist[k]의 값이 갱신 되었다면) queue를 종료하도록 해서 답을 출력하도록 했다.

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
import queue
n,k=map(int,input().split())
check=[0]*200000
dist=[0]*200000
check[n]=1
q=queue.Queue()
q.put(n)
while q.qsize():
    number=q.get()
    if number-1 >=0:
        if check[number-1]==0:
            q.put(number-1)
            check[number-1]=1
            dist[number-1]=dist[number]+1
    if number+1 < 200000:
        if check[number+1]==0:
            q.put(number+1)
            check[number+1]=1
            dist[number+1]=dist[number]+1
    if 2*number < 200000:
        if check[2*number]==0:
            q.put(2*number)
            check[2*number]=1
            dist[2*number]=dist[number]+1
    if dist[k]:
        break
print(dist[k])
 cs

 

문제 링크:

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

728x90
반응형
저작자표시 비영리 동일조건

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

[BOJ]1759. 암호 만들기  (0) 2019.09.24
[BOJ]14889. 스타트와 링크  (0) 2019.09.23
[BOJ]2022. 사다리  (0) 2019.09.21
[BOJ]1561. 놀이공원  (0) 2019.09.20
[BOJ]1080. 행렬  (0) 2019.09.19
728x90
반응형

문제:

N장의 카드가 있다. 각각의 카드는 차례로 1부터 N까지의 번호가 붙어 있으며, 1번 카드가 제일 위에, N번 카드가 제일 아래인 상태로 순서대로 카드가 놓여 있다.

이제 다음과 같은 동작을 카드가 한 장 남을 때까지 반복하게 된다. 우선, 제일 위에 있는 카드를 바닥에 버린다. 그 다음, 제일 위에 있는 카드를 제일 아래에 있는 카드 밑으로 옮긴다.

예를 들어 N=4인 경우를 생각해 보자. 카드는 제일 위에서부터 1234의 순서로 놓여있다. 1을 버리면 234가 남는다. 여기서 2를 제일 아래로 옮기면 342가 된다. 3을 버리면 42가 되고, 4를 밑으로 옮기면 24가 된다. 마지막으로 2를 버리고 나면, 남는 카드는 4가 된다.

N이 주어졌을 때, 제일 마지막에 남게 되는 카드를 구하는 프로그램을 작성하시오.

입력:

첫째 줄에 정수 N(1<=N<=500,000)이 주어진다.

출력:

첫째 줄에 남게 되는 카드의 번호를 출력한다.

풀이 방법:

 처음에는 카드 방식대로 일반 배열의 pop을 이용해서 문제를 풀었더니 시간초과가 발생하였다. 이를 줄이기 위해서 문제 케이스가 계속 짝수만 남게 되는 구조인것 같아 짝수만 담아서 했는데 틀렸었다. 따라서 애초 문제 의도대로 큐 모듈을 가져와서 풀었더니 시간 초과 없이 통과하였다.
 파이썬은 queue를 지원하는 모듈을 가지고 있다. queue.Queue()는 한 변수를 큐 배열로 선언하겠다는 뜻이다. 그리고 이렇게 큐로 선언한 배열에 put()은 값을 넣는 함수, qsize()는 길이를 반환하는 함수, get()은 값을 빼는 함수들을 사용할 수 있다. 따라서 이렇게 pop()을 쓴 것 처럼 똑같이 짜면 시간초과 없이 통과 가능하다. 

1
2
3
4
5
6
7
8
9
10
import queue
n=int(input())
cards=queue.Queue()
for i in range(1,n+1):
    cards.put(i)
while(cards.qsize()!=1):
    cards.get()
    a=cards.get()
    cards.put(a)
print(cards.get())
cs


728x90
반응형
저작자표시 비영리 동일조건

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

[BOJ]2606. 바이러스  (0) 2019.07.20
[BOJ]1260. DFS와 BFS  (0) 2019.07.19
[BOJ]4949. 균형잡힌 세상  (0) 2019.07.17
[BOJ]2004. 조합 0의 개수  (0) 2019.07.16
[BOJ]2217. 로프  (0) 2019.07.15
728x90
반응형

문제:

조세퍼스 문제는 다음과 같다.

1번부터 N번까지 N명의 사람이 원을 이루면서 앉아있고, 양의 정수 K(<=N)가 주어진다. 이제 순서대로 K번째 사람을 제거한다. 한 사람이 제거되면 남은 사람들로 이루어진 원을 따라 이 과정을 계속해 나간다. 이 과정은 N명의 사람이 모두 제거될 때까지 계속된다. 원에서 사람들이 제거되는 순서를 (N,K)-조세퍼스 순열이라고 한다. 예를 들어 (7,3)-조세퍼스 순열은 <3, 6, 2, 7, 5, 1, 4> 이다.

N과 K가 주어지면 (N, K)-조세퍼스 순열을 구하는 프로그램을 작성하시오.

입력:

첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1<=K<=N<=1,000)

출력:

예제와 같이 조세퍼스 순열을 출력한다.

풀이 방법:

 값을 빼기 전에 미리 idx를 저장을 해두는 것이 중요하다. 값을 먼저 빼버리면 다음 순환 반복을 못하기 때문이다. 또한 빼준 다음에는 idx 를 1 감소해서 인덱스가 하나 줄었음을 나타낸다. 또한 값을 뺄 당시에 출력 예시와 동일하게 만들어야 하므로 끝 값에만 따로 케이스를 분류를 해두었다.

이 문제는 태그가 큐로 되어 있었는데 아마도 순환 큐를 이용해서 풀어야 하는 문제인 것 같다.

1
2
3
4
5
6
7
8
9
10
11
12
a,b=map(int,input().split())
answer=list(range(1,a+1))
idx=-1
print("<",end="")
while(len(answer)!=0):
    idx+=b
    idx=idx%(len(answer))
    if len(answer)==1:
        print(answer.pop(idx),end=">")
    else:
        print(answer.pop(idx),end=", ")
    idx-=1
cs


728x90
반응형
저작자표시 비영리 동일조건

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

[BOJ]11051. 이항 계수 2  (0) 2019.05.09
[BOJ]11050. 이항 계수 1  (0) 2019.05.08
[Programmers]Lv 3.디스크 컨트롤러  (2) 2019.05.06
[BOJ]8979. 올림픽  (0) 2019.05.05
[BOJ]1076. 저항  (0) 2019.05.04
728x90
반응형

문제:

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


728x90
반응형
저작자표시 비영리 동일조건

'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
728x90
반응형

문제:

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

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

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

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

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


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


(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




728x90
반응형
저작자표시 비영리 동일조건

'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
728x90
반응형

문제:

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

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



728x90
반응형
저작자표시 비영리 동일조건

'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
728x90
반응형

문제:

트럭 여러 대가 강을 가로지르는 일 차선 다리를 정해진 순으로 건너려 합니다. 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 알아내야 합니다. 트럭이 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


728x90
반응형
저작자표시 비영리 동일조건

'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
728x90
반응형

문제:

프로그래머스 팀에서는 기능 개선 작업을 수행 중입니다. 각 기능은 진도가 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


728x90
반응형
저작자표시 비영리 동일조건

'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
728x90
반응형

문제:

 수평 직선에 높이가 서로 다른 탑  N대를 세웠습니다. 모든 탑의 꼭대기에는 신호를 송/수신하는 장치를 설치했습니다. 발사한 신호는 신호를 보낸 탑보다 높은 탑에서만 수신합니다. 또한, 한 번 수신된 신호는 다른 탑으로 송신되지 않습니다.

예를 들어 높이가 6,9,5,7,4인 다섯 탑이 왼쪽으로 동시에 레이저 신호를 발사합니다. 그러면, 탑은 다음과 같이 신호를 주고 받습니다. 높이가 4인 다섯 번째 탑에서 발사한 신호는 높이가 7인 네 번째 탑이 수신하고, 높이가 7인 네 번째 탑의 신호는 높이가 9인 두 번째 탑이, 높이가 5인 세 번째 탑의 신호도 높이가 9인 두 번째 탑이 수신합니다. 높이가 9인 두 번째 탑의 높이가 6인 첫 번째 탑인 보낸 레이저 신호는 어떤 탑에서도 수신할 수 없습니다.

맨 왼쪽에서 순서대로 탑의 높이를 담은 배열 heights가 매개변수로 주어질 때 각 탑이 쏜 신호를 어느 탑에서 받았는지 기록한 배열을 return 하도록 solution 함수를 작성해주세요.

풀이 방법:

 스택이란 모든 원소들의 삽입과 삭제가 리스트의 한쪽 끝에서만 수행되는 자료 구조로 LIFO(Last In First Out) 이라는 특징을 가지고 있다. 스택은 리스트의 끝을 Top이라고 하는데 삽입과 삭제의 연산이 top에서만 이루어져 있으므로 top 포인터는 1씩 증가 혹은 감소시킴으로써 수행한다.
 큐는 스택과 반대 구조로 리스트의 한 쪽 끝에서는 자료가 삽입되고 다른 한 쪽에서 자료가 삭제되는 자료 구조를 뜻한다. 즉 FIFO(First In First Out) 구조를 가지고 있다.
 파이썬의 리스트는 기본적으로 스택 구조를 유지한다. 따라서 append를 사용하면 리스트의 끝에 추가를 하고 pop을 하면 리스트의 끝 값이 빠져나가는 것이 그 이유이다. 우선 신호의 진행 방향이 오른쪽에서 왼쪽으로 이동을 하므로 조금 더 편하게 보기 위해서 reverse 함수를 사용해서 방향을 바꾸어 확인하였다. 송신하는 탑의 인덱스를 i 의 값으로 수신하는 탑의 인덱스를 j 로 하여 송신 탑보다 높은 수신 탑을 찾도록 하였다. 만약 찾았다면 reverse 함수를 사용해서 인덱스를 뒤집었으므로 길이에서 수신 탑의 인덱스를 빼서 원래 수신 탑의 인덱스를 집어 넣도록 하였다. 또한 count 값을 설정해서 끝까지 갈 동안 수신 탑을 못 찾을 경우에 0을 넣도록 하였다. 항상 모든 경우에 가장 왼쪽의 탑은 수신을 받을 탑이 없기에 반복문이 끝난 뒤 0을 넣고 난 뒤 다시 원래의 값을 얻기 위해 reverse 함수를 사용해서 원래대로 돌렸다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def solution(height):
    answer = []
    height.reverse() #오른쪽에서 왼쪽으로 송신하므로
    for i in range(len(height)):
        count=0 #송신하는 탑과 수신하는 탑의 차이
        for j in range(i+1,len(height)):
            count+=1
            if height[i] < height[j]:
                answer.append(len(height)-j)
                break
            else:
                if count==len(list(range(i+1,len(height)))): #수신하는 탑이 없이 끝까지 도달 했을 경우
                    answer.append(0)
                    break
    answer.append(0) #맨 왼쪽에 있던 탑은 항상 수신하는 탑이 없다.
    answer.reverse()
    return answer
cs
  


728x90
반응형
저작자표시 비영리 동일조건

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

[Programmers]Lv 2. 스킬트리  (0) 2019.01.25
[Programmers]Lv 1. 최대공약수와 최소공배수  (0) 2019.01.24
[Programmers]Lv 1. 콜라츠 추측  (0) 2019.01.21
[Programmers]Lv 1. 하샤드 수  (0) 2019.01.20
[Programmers]Lv 1.핸드폰 번호 가리기  (0) 2019.01.19

+ Recent posts

티스토리툴바