문제:

풀이방법:

처음에 문제를 이해하는 것이 가장 어려웠던 것 같다. 다음과 같은 흐름으로 문제를 이해하면 도움이 될 것 같다.

 

  • 택배 상자는 무조건 [1,2,3,4, ... ] 와 같은 순서로 주어진다.
    • 택배 기사님의 순서와는 무관하다.
  • 문제의 설명을 보면 Stack을 사용해야 한다. 이 때, 컨테이너 벨트(main), 보조 컨테이너 벨트(sub) 모두 stack으로 이루어진 배열이다.
    • 단, 컨테이너 벨트에는 [1,2,3,4, ...]가 이미 적재되어 있다.
  • main에서 sub로 이동하는 것은 가능하지만, sub에서 main으로 이동하는 것은 불가능하다.

결국 2개의 stack 배열을 사용해서 택배 기사님의 순서를 맞추는 문제라고 생각하면 된다.

 

 main에서 sub로만 이동하는 것이 가능하기 때문에 main 혹은 sub의 out 상자가 첫 택배 기사님의 순서에 맞게 세팅을 해둔다. 택배 기사님이 원하는 택배 상자를 적재 하고 main이나 sub에 또 원하는 상자가 있다면 연속해서 적재하며 만약 그렇지 않다면 main에서 sub로 이동시키며 조건을 만족하는지 계속해서 확인한다.

 이 과정을 main의 모든 택배 상자가 비었으며, 더 이상 적재하지 못할 때까지 반복한다.

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(order):
    main = list(range(len(order), 0, -1))
    sub = []
    answer = []
    while True:
        if main[-1]==order[0]:
            break
        elif len(sub) and sub[-1]==order[0]:
            break
        sub.append(main.pop())
        
    idx = 0
    while True:
        if len(main) and (main[-1] == order[idx]):
            answer.append(main.pop())
            idx += 1
        elif len(sub) and (sub[-1] == order[idx]):
            answer.append(sub.pop())
            idx += 1
        else:
            if len(main):
                sub.append(main.pop())
            else:
                break
    return len(answer)
 cs

문제링크:

https://school.programmers.co.kr/learn/courses/30/lessons/131704

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

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

[BOJ] 1343. 폴리오미노  (0) 2023.07.07
[BOJ] 18405. 경쟁적 전염  (0) 2023.07.06
[1138] 한 줄로 서기  (0) 2023.07.04
[2477] 참외밭  (0) 2023.07.03
[BOJ]14620. 꽃길  (1) 2022.08.18

문제:

풀이방법:

문제에서 주어진대로 구현을 해도 되지만 stack을 활용해서 풀었다. 각 열별로 newboard에 stack으로 정리를 하며, move를 이용해서 각 열에 있는 값들을 pop을 해서 빼온다. move에 해당하는 열에 값이 없다면 continue로 행동을 넘기며 값이 있다면 basket에 값을 넣는다.

 basket에 값을 넣었다면 위의 두 값이 같은지 확인하고 같다면 pop을 사용해서 빼고 answer 카운트를 2 증가시킨다. (두 값이 같아 없어지는 행위를 세는 것이 아니라 없어진 것의 개수를 구하는 것이므로 2를 더하는게 맞다.)

이 행위를 moves에 있는 행동대로 다 하고 난 뒤의 answer를 반환한다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def solution(board, moves):
    answer = 0
    newboard=[[]for _ in range(len(board))]
    while len(board):
        last=board.pop()
        for i in range(len(last)):
            if last[i]==0:
                continue
            newboard[i].append(last[i])
    basket=[]
    for move in moves:
        if len(newboard[move-1])==0:
            continue
        basket.append(newboard[move-1].pop())
        if len(basket)>=2 and basket[-1]==basket[-2]:
            basket.pop()
            basket.pop()
            answer+=2
    return answer
 cs

문제링크:

https://programmers.co.kr/learn/courses/30/lessons/64061

 

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

 

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

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

[BOJ]5014. 스타트링크  (0) 2020.05.07
[2019 Kakao winter internship]튜플  (0) 2020.04.23
[BOJ]2863. 이게 분수?  (0) 2020.04.16
[BOJ]7785. 회사에 있는 사람  (0) 2020.04.14
[BOJ]1718. 암호  (0) 2020.04.09

문제:

세계는 균형이 잘 잡혀있어야 한다. 양과 음, 빛과 어둠 그리고 왼쪽 괄호와 오른쪽 괄호처럼 말이다.

정민이의 임무는 어떤 문자열이 주어졌을 때, 괄호들의 균형이 잘 맞춰져 있는지 판단하는 프로그램을 짜는 것이다.

문자열에 포함되는 괄호는 소괄호 ("()") 와 대괄호 ("[]")로 2종류이고, 문자열이 균형을 이루는 조건은 아래와 같다.

* 모든 왼쪽 소괄호는 ("(")는 오른쪽 소괄호(")")와만 짝을 이룰 수 있다.
* 모든 왼쪽 대괄호는 ("[")는 오른쪽 대괄호("]")와만 짝을 이룰 수 있다.
* 모든 오른쪽 괄호는 자신과 짝을 이룰 수 있는 왼쪽 괄호가 존재한다.
* 모든 괄호들의 짝은 1:1 매칭만 가능하다. 즉, 괄호 하나가 둘 이상의 괄호와 짝지어지지 않는다.
* 짝을 이루는 두 괄호가 있을 때, 그 사이에 있는 문자열도 균형이 잡혀야 한다.

정민이를 도와 문자열이 주어졌을 때 균형잡힌 문자열인지 아닌지를 판단해보자.

입력:

하나 또는 여러줄에 걸쳐서 문자열이 주어진다. 각 문자열은 영문 알파벳, 공백, 소괄호 ("()") 대괄호("[]")등으로 이루어져 있으며, 길이는 100글자보다 작거나 같다.

입력의 종료조건으로 맨 마지막에 점 하나(".")가 들어온다.

출력:

각 줄마다 해당 문자열이 균형을 이루고 있으면 "yes"를, 아니면 "no"를 출력한다.

풀이 방법:

 처음에는 이와 비슷한 문제들은 ( , [ 를 만나면 count +=1 하고 ), ]를 만나면 count -=1 하는 방법으로 쉽게 풀 수 있어서 비슷한 문제인 줄 알았다. 하지만 예제 중에 5번째 줄인 ( [ ) ] 과 같은 케이스는 마지막 조건에 의해서 안된다는 것을 알게 되었다.
 따라서 이 문제를 해결하기 위해서 stack이라는 배열을 만들어서 ( , [를 만나면 담고, ) ] 를 만나면 빼는 ( 예외 케이스 처리 하에) 방법으로 해서 통과를 했다.

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
while True:
    string=input()
    if string==".":
        break
    stack=[]
    answer=True
    for i in string:
        if i=='(':
            stack.append(i)
        elif i=='[':
            stack.append(i)
        elif i==')':
            if len(stack)==0:
                answer=False
                break
            if stack[-1]=='(':
                stack.pop()
            else:
                answer=False
                break
        elif i==']':
            if len(stack)==0:
                answer=False
                break
            if stack[-1]=='[':
                stack.pop()
            else:
                answer=False
                break
    if len(stack)==0 and answer:
        print("yes")
    else:
        print("no")
cs


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

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

[BOJ]1260. DFS와 BFS  (0) 2019.07.19
[BOJ]2164. 카드2  (0) 2019.07.18
[BOJ]2004. 조합 0의 개수  (0) 2019.07.16
[BOJ]2217. 로프  (0) 2019.07.15
[BOJ]11047. 동전0  (0) 2019.07.14

문제:

4개의 기호 ‘(’, ‘)’, ‘[’, ‘]’를 이용해서 만들어지는 괄호열 중에서 올바른 괄호열이란 다음과 같이 정의된다.


1. 한 쌍의 괄호로만 이루어진 ‘()’와 ‘[]’는 올바른 괄호열이다. 

2. 만일 X가 올바른 괄호열이면 ‘(X)’이나 ‘[X]’도 모두 올바른 괄호열이 된다. 

3. X와 Y 모두 올바른 괄호열이라면 이들을 결합한 XY도 올바른 괄호열이 된다.


예를 들어 ‘(()[[]])’나 ‘(())[][]’ 는 올바른 괄호열이지만 ‘([)]’ 나 ‘(()()[]’ 은 모두 올바른 괄호열이 아니다. 우리는 어떤 올바른 괄호열 X에 대하여 그 괄호열의 값(괄호값)을 아래와 같이 정의하고 값(X)로 표시한다. 


1. ‘()’ 인 괄호열의 값은 2이다.

2. ‘[]’ 인 괄호열의 값은 3이다.

3. ‘(X)’ 의 괄호값은 2×값(X) 으로 계산된다.

4. ‘[X]’ 의 괄호값은 3×값(X) 으로 계산된다.

5. 올바른 괄호열 X와 Y가 결합된 XY의 괄호값은 값(XY)= 값(X)+값(Y) 로 계산된다.


예를 들어 ‘(()[[]])([])’ 의 괄호값을 구해보자.  ‘()[[]]’ 의 괄호값이 2 + 3×3=11 이므로  ‘(()[[ ]])’의 괄호값은 2×11=22 이다. 그리고  ‘([])’의 값은 2×3=6 이므로 전체 괄호열의 값은 22 + 6 = 28 이다.


여러분이 풀어야 할 문제는 주어진 괄호열을 읽고 그 괄호값을 앞에서 정의한대로 계산하여 출력하는 것이다. 

입력:

첫째 줄에 괄호열을 나타내는 문자열(스트링)이 주어진다. 단 그 길이는 1 이상, 30이하이다.

출력:

첫째 줄에 그 괄호열의 값을 나타내는 정수를 출력한다. 만일 입력이 올바르지 못한 괄호열이면 반드시 0을 출력해야 한다.

풀이 방법:

문제에서 제공된 예시케이스를 보면 예시케이스는 다음과 같이 계산이 되어야 한다.  2×(2+3×3)+2×3 사람이 직접 괄호를 보고 계산을 하면 이렇게 하겠지만 컴퓨터에게 이렇게 연산을 하게끔 하는 것은 어렵다. 따라서 위 식을 다음과 같이 변경하도록 할 것이다. 2×2+2×3×3+2×3 와 같이 괄호를 분배법칙을 이용해 풀어내었다. 이 규칙대로 하기 위해서 ( 나 [ 를 만나면 temp에 2 나 3를 곱하고 stack에 담아두고, ) 나 ] 를 만날 경우에는 그 전의 값이 ( 나 [ 일 경우에만 answer에 더해줬다.. 그 이유는 이 경우에만 올바른 괄호열이기 때문이다. 물론 앞에서 미리 temp에서 곱하면서 움직였으므로 값은 올바르게 구해진다. 그리고 스택의 top 값이 ( 나 [ 이면 pop 해줬다. 계속 이과정을 반복하다가 중간에 스택이 비어버렸는데 빼야하는 경우가 온다거나 끝까지 다 진행했는데도 아직 stack에 남아있다면 올바르지 않은 괄호열이기때문에 0을 출력하고 그렇지 않으면 answer를 출력하도록 한다.

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
answer=0
stack=[]
temp=1
correct=True
string=input()
for i in range(len(string)):
    if string[i]=="(":
        temp*=2
        stack.append("(")
    elif string[i]=="[":
        temp*=3
        stack.append("[")
    elif string[i]==")":
        if string[i-1]=="(":
            answer+=temp
        if not len(stack):
            correct=False
            break
        if stack[-1]=="(":
            stack.pop()
        temp//=2
    else:
        if string[i-1]=="[":
            answer+=temp
        if not len(stack):
            correct=False
            break
        if stack[-1]=="[":
            stack.pop()
        temp//=3
if (len(stack) or not correct):
    print(0)
else:
    print(answer)
cs


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

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

[BOJ]2163. 초콜릿 자르기  (0) 2019.04.20
[BOJ]1912. 연속합  (0) 2019.04.19
[BOJ]9012.괄호  (0) 2019.04.17
[BOJ]1874. 스택 수열  (0) 2019.04.16
[BOJ]10828. 스택  (0) 2019.04.15

문제:

괄호 문자열(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

+ Recent posts

티스토리툴바