문제:

풀이방법:

생각보다 시간에 대한 조건이 넉넉한 편이기 때문에 모든 경우의 수를 확인하면서 풀어도 된다.

가능한 모든 경우의 수를 구하기 위해서 key와 lock의 크기를 기준으로 a라는 배열을 만든다. key와 lock의 크기가 3x3으로 동일하다고 하면 다음과 같이 a를 만들어야 한다.

위 그림에서 노란색으로 색칠한 부분이 lock에 해당하고, 빨간색 박스가 key에 해당한다. 이제 이 배열에서 빨간색 박스 key로 a를 슬라이딩하면서 lock에 해당하는 부분이 모두 채워지는 경우가 있는지 확인하면 된다.

따라서 a를 (len(key)*2+len(lock)-2)x(len(key)*2+len(lock)-2) 크기인 0인 2차원 배열로 초기화 하고 lock에 해당하는 부분만 채워주도록 한다.

위 그림부터 시작해서 현재 key 모양, 90도 회전한 모양, 180도 회전한 모양, 270도 회전한 모양을 각각 넣어보면서(360도는 현재 key 모양과 같다.) lock의 모든 값이 1로 바뀌었는지 확인한다.

이 확인 과정을 슬라이딩 끝까지 진행하며 중간에 True인 경우가 있다면 바로 true를 반환한다. 만약 끝까지 true인 경우가 없다면 false를 반환한다.

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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
import copy
 
def check(x,y,a,key,x1,y1,lock):
    temp=copy.deepcopy(a)
    for i in range(len(key)):
        for j in range(len(key)):
            temp[x+i][y+j]+=key[i][j]
    if solve(x1,y1,temp,lock):
        return True
    else:
        return False
 
def solve(x,y,a,lock):
    for i in range(len(lock)):
        for j in range(len(lock)):
            if a[x+i][y+j]==0 or a[x+i][y+i]==2:
                return False
    return True
 
def rotate_90(m):
    N = len(m)
    ret = [[0* N for _ in range(N)]
    for r in range(N):
        for c in range(N):
            ret[c][N-1-r] = m[r][c]
    return ret
 
def rotate_180(m):
    N = len(m)
    ret = [[0* N for _ in range(N)]
    for r in range(N):
        for c in range(N):
            ret[N-1-r][N-1-c] = m[r][c]
    return ret
 
def rotate_270(m):
    N = len(m)
    ret = [[0* N for _ in range(N)]
 
    for r in range(N):
        for c in range(N):
            ret[N-1-c][r] = m[r][c]
    return ret
 
def solution(key,lock):
    a=[[0 for i in range(len(key)*2+len(lock)-2)]for i in range(len(key)*2+len(lock)-2)]
    x=len(key)-1
    y=len(key)-1
    for i in range(len(lock)):
        for j in range(len(lock)):
            a[x+i][y+j]=lock[i][j]
    for i in range(len(a)-len(key)+1):
        for j in range(len(a)-len(key)+1):
            if check(i,j,a,key,x,y,lock):
                return True
            key90=rotate_90(key)
            if check(i,j,a,key90,x,y,lock):
                return True
            key180=rotate_180(key)
            if check(i,j,a,key180,x,y,lock):
                return True
            key270=rotate_270(key)
            if check(i,j,a,key270,x,y,lock):
                return True
    return False
cs

문제링크:

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

 

코딩테스트 연습 - 자물쇠와 열쇠

[[0, 0, 0], [1, 0, 0], [0, 1, 1]] [[1, 1, 1], [1, 1, 0], [1, 0, 1]] true

programmers.co.kr

 

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

[BOJ]14502. 연구소  (0) 2020.08.18
[BOJ]2961. 도영이가 만든 맛있는 음식  (0) 2020.08.13
[Programmers]2020 Kakao. 자물쇠와 열쇠  (0) 2020.08.11
[BOJ]2493. 탑  (0) 2020.08.06
[BOJ]19532. 수학은 비대면강의입니다.  (0) 2020.08.04
[BOJ]2580. 스도쿠  (0) 2020.07.30

문제:

풀이방법:

 효율적으로 풀어야 하는 문제이기 때문에 O(N^2) 방법으로는 시간초과에 걸릴 것이다. 따라서 투 포인터를 사용하는 슬라이딩 윈도우를 사용해서 풀었다. 

 우선 앞에서부터 뒷 포인터를 이동시키면서 모든 보석을 포함할 때까지 이동한다. 모든 보석을 포함하게 된다면 앞 포인터를 움직여서 가장 앞에 존재했던 보석을 뺀다. 그래도 모든 보석이 포함되어 있다면 앞 포인터를 움직여서 다시 앞을 빼고, 모든 보석이 포함되어 있지 않다면 뒷 포인터를 움직여서 다시 모든 보석을 포함시킬 때까지 움직인다. 

이 과정을 반복하면서 가장 짧은 길이의 포인터들을 저장해두고 최종적으로 출력하도록 한다.

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
42
43
44
45
46
47
def solution(gems):
    answer = []
    initGems = len(set(gems))
    
    gemCount = {}
    gemSet = set()
    
    start,answerStart = 00
    last,answerLast = 00
    diff = 999999999
    swLast = -1
    
    for s in range(len(gems)):
        findsw = False
        for l in range(swLast+1,len(gems)):
            if len(gemSet) == initGems:
                findsw = True
                if abs(l-s-1< diff:
                    diff = abs(l-s-1)
                    answerStart = s
                    answerLast = l-1
                swLast = l-1
                break
            if not gemCount.get(gems[l]):
                gemCount[gems[l]] = 1
                gemSet.add(gems[l])
            else:
                gemCount[gems[l]] +=1
        if not findsw:
            if len(gemSet) == initGems:
                findsw = True
                if abs(l-s) < diff:
                    diff = abs(l-s)
                    answerStart = s
                    answerLast = l
                swLast = l
            break
 
        if gemCount.get(gems[s]):
            if gemCount[gems[s]]==1:
                del gemCount[gems[s]]
                gemSet.remove(gems[s])
            else:
                gemCount[gems[s]] -=1
                
    answer.append([answerStart+1,answerLast+1])
    return answer[0]
cs

문제링크:

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

 

코딩테스트 연습 - 보석 쇼핑

["DIA", "RUBY", "RUBY", "DIA", "DIA", "EMERALD", "SAPPHIRE", "DIA"] [3, 7]

programmers.co.kr

 

문제:

풀이방법:

 연산자를 계산하는 방법으로 주로 스택을 사용하기 때문에 스택을 사용하고, 수식의 갯수가 3개이므로 최대 6가지 조합이 가능하기 때문에 브루트 포스 방법을 사용해서 모든 케이스에 대해 계산을 하고 그 중 최대값을 찾는 방법을 사용한다.

 우선 정규표현식과 itertools의 permutations을 사용해서 입력받은 expression에 대해서 숫자와 수식을 분리해내고, 연산자들의 우선순위를 만든다.

 생성된 우선순위별로 숫자와 연산자들을 스택에 넣고, 연산자가 현재 해당하는 우선순위의 연산자라면 숫자 스택에서 두 개를 빼고, 연산자 스택에서 하나를 빼서 연산을 하고 다시 숫자 스택에 넣도록 한다.

 이 과정을 우선순위와 연산자별로 계속 반복해서 하고 이 중 max 값을 찾아서 반환하도록 한다.

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
def calculate(a,b,op):
    if op=="+":
        return a+b
    elif op=="*":
        return a*b
    else:
        return a-b
 
def solution(expression):
    import re
    from itertools import permutations
    prior = list(permutations(["+","*","-"],3))
    digit = re.compile("[0-9]+")
    operator = re.compile("[^0-9]")
    numbers = list(map(int,digit.findall(expression)))
    oper = list(operator.findall(expression))
    
    answer = 0
    for pr in prior:
        number = numbers
        ope = oper
        for i in range(3):
            stack = [number[0]]
            stack_op = []
            count = 1
            while count < len(number):
                stack.append(number[count])
                stack_op.append(ope[count-1])
                count+=1
                if stack_op[-1]==pr[i]:
                    b = stack.pop(-1)
                    a = stack.pop(-1)
                    op = stack_op.pop(-1)
                    
                    stack.append(calculate(a,b,op))
            number = stack
            ope = stack_op
        answer = max(answer,abs(number[0]))   
    return answer
cs

문제링크:

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

 

코딩테스트 연습 - 수식 최대화

IT 벤처 회사를 운영하고 있는 라이언은 매년 사내 해커톤 대회를 개최하여 우승자에게 상금을 지급하고 있습니다. 이번 대회에서는 우승자에게 지급되는 상금을 이전 대회와는 다르게 다음과 �

programmers.co.kr

 

문제:

풀이방법:

규칙 중 4를 구현하는 것이 핵심인 문제다.

 solution함수는 1,4,7 입력이 들어온다면 왼쪽 엄지손가락을 사용하고, 해당 번호로 left를 이동시키고, 3,6,9가 들어온다면 오른쪽 엄지손가락을 사용하고 right를 이동시킨다. 이제 2,5,8,0이 들어오는 경우 leftDistance와 rightDistance를 사용해서 거리를 계산한다. 더 작은 쪽의 엄지손가락으로 이동을 하고, 만약 같다면 hand의 우선순위에 따라 움직이도록 한다.

 leftDistance는 입력을 해야하는 숫자가 2,5,8,0일 때, 왼쪽 엄지손가락과 거리를 계산하는 함수다.

만약 이전 왼쪽 엄지 손가락이 2,5,8이고 입력해야 할 숫자가 0이라면 각 케이스마다 거리를 return 하게 만들고, 나머지는 두 수의 차를 3으로 나눈 몫을 반환하도록 한다. 왼쪽 엄지 손가락이 1,4,7에 있다면 이를 가운데 키패드로 옮겨주고 leftDistance로 재귀적으로 거리를 계산하도록 만든다. 이제 나머지 케이스인 0에 있거나, 초기 상태인 *에 있던 경우에 대해서만 거리를 계산해주면 된다.

 rightDistance로 leftDistance와 비슷하게 계산을 하도록 한다.

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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
def leftDistance(num,left):
    if left in [2,5,8]:
        if num == 0:
            if left ==2:
                return 3
            elif left == 5:
                return 2
            else:
                return 1
        return abs(left-num)//3
    elif left in [1,4,7]:
        return leftDistance(num,left+1)+1
    else:
        if left == -1:
            if num == 2:
                return 4
            elif num == 5:
                return 3
            elif num == 8:
                return 2
            else:
                return 1
        if num == 0:
            return 0
        elif num == 8:
            return 1
        elif num == 5:
            return 2
        else:
            return 3
        
def rightDistance(num,right):
    if right in [2,5,8]:
        if num == 0:
            if right ==2:
                return 3
            elif right == 5:
                return 2
            else:
                return 1
        return abs(right-num)//3
    elif right in [3,6,9]:
        return rightDistance(num,right-1)+1
    else:
        if right == -1:
            if num == 2:
                return 4
            elif num == 5:
                return 3
            elif num == 8:
                return 2
            else:
                return 1
        if num == 0:
            return 0
        elif num == 8:
            return 1
        elif num == 5:
            return 2
        else:
            return 3
def solution(numbers,hand):
    answer = ""
    left, right = -1-1
    for num in numbers:
        if num in [1,4,7]:
            left = num
            answer += "L"
        elif num in [3,6,9]:
            right = num
            answer += "R"
        else:
            center_l = leftDistance(num,left)
            center_r = rightDistance(num,right)
            distance = center_l-center_r
            if distance > 0:
                right = num
                answer += "R"
            elif distance < 0:
                left = num
                answer += "L"
            else:
                if hand =="right":
                    right = num
                    answer+= "R"
                else:
                    left = num
                    answer += "L"
    return answer
cs

문제링크:

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

 

코딩테스트 연습 - 키패드 누르기

[1, 3, 4, 5, 8, 2, 1, 4, 5, 9, 5] "right" "LRLLLRLLRRL" [7, 0, 8, 2, 8, 3, 1, 5, 7, 6, 2] "left" "LRLLRRLLLRR" [1, 2, 3, 4, 5, 6, 7, 8, 9, 0] "right" "LLRLLRLLRL"

programmers.co.kr

 

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

[BOJ]2164. 카드2  (0) 2020.07.14
[Programmers]2020 카카오 인턴십. 수식 최대화  (0) 2020.07.09
[Programmers]2020 카카오 인턴십. 키패드 누르기  (0) 2020.07.07
[BOJ]1543. 문서 검색  (0) 2020.07.02
[BOJ]5525. IOIOI  (0) 2020.06.30
[BOJ]11652. 카드  (0) 2020.06.25

문제:

풀이방법:

문자열을 잘 parsing할 수 있는지와, 어느 시점에 최대가 되는지 알아야 하는 문제다.

 우선 문자열을 파싱하기 위해서 splitTime이라는 함수를 만들었고, 날짜, 시간, 처리시간은 공백으로 구분되어 있기 때문에 split해주고, 날짜는 항상 2016년 9월 15일로 고정되어 있기 때문에 사용하지 않는다. 시간은 다시한번 :로 구분되어 있기 때문에 split해주고 1초간 처리하는 요청의 최대 개수를 알아야 하기 때문에 시간을 1초 단위로 만들어준다. 처리시간은 초 단위로 나오고 항상 s로 끝나기 때문에 이를 제거한 다음에 float으로 만들어 준다. 그리고 처리시간은 시작시간과 끝시간을 포함하기 때문에 배열로 반환을 할 때 시작시간에 0.001만큼 더하도록 한다.

 보통 최대 개수인 부분은 시작시간이나 끝시간에서 발생하게 된다. 이 시간들을 기준으로 처리해야하는 데이터가 생성되거나 사라지기 때문이다. (배열의 모든 시간을 탐색해도 좋지만 시간이 오래 걸릴 것이다.) 각 트래픽별의 시작시간과 끝나는 시간을 기준으로 트래픽의 갯수를 세서 최대 갯수를 파악한다.

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
def splitTime(line):
    strings = line.split()
    end = strings[1]
    duration = float(strings[2][:-1])
    times = end.split(":")
    time = int(times[0])*3600
    time += int(times[1])*60
    time += float(times[2])
    return [time-duration+0.001,time]
 
def check(times,traffic):
    count = 0
    for time in times:
        temp = 0
        start = time
        end = time +1
        for t in traffic:
            if t[1]>= start and t[0]<end:
                temp+=1
        count=max(count,temp)
    return count
    
 
def solution(lines):
    traffic=[]
    answer=[]
    for line in lines:
        traffic.append(splitTime(line))
    for t in traffic:
        answer.append(check(t,traffic))
    return max(answer)
cs

 

문제링크:

https://programmers.co.kr/learn/courses/30/lessons/17676?language=python3

 

코딩테스트 연습 - [1차] 추석 트래픽

입력: [ 2016-09-15 20:59:57.421 0.351s, 2016-09-15 20:59:58.233 1.181s, 2016-09-15 20:59:58.299 0.8s, 2016-09-15 20:59:58.688 1.041s, 2016-09-15 20:59:59.591 1.412s, 2016-09-15 21:00:00.464 1.466s, 2016-09-15 21:00:00.741 1.581s, 2016-09-15 21:00:00.748

programmers.co.kr

 

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

[BOJ]1837. 암호제작  (0) 2020.06.11
[BOJ]9506. 약수들의 합  (0) 2020.06.09
[Programmers]2018 Kakao[1차]추석 트래픽  (0) 2020.05.26
[Programmers]2019 Kakao 불량 사용자  (0) 2020.05.21
[BOJ]2468. 안전 영역  (0) 2020.05.19
[BOJ]2167. 2차원 배열의 합  (0) 2020.05.14

문제:

풀이방법:

여러가지 푸는 방법이 있겠지만, 가장 단순하면서 쉬운 방법을 사용하고자 한다. 브루트 포스 방식으로 가능한 모든 경우의 수를 만들고 그 중에서 해당하는 조건을 찾는 방법으로 했다.

 우선 python의 itertools의 permutation을 사용해서 모든 경우의 수를 만든다. 그리고 각 조건에 맞는지 확인을 하는데, 조건의 길이와 다르면 바로 False로 가도록 하고, 길이가 같다면 그 때 조건을 비교하도록 한다.

 이렇게 조건에 맞는 경우를 찾았다면 중복을 방지하기 위해서 set으로 값을 넣도록 한다.

1s
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
import itertools
 
def check(case,banned_id):
    for i in range(len(banned_id)):
        if len(banned_id[i]) !=len(case[i]):
            return False
        else:
            for j in range(len(banned_id[i])):
                if banned_id[i][j]=="*":
                    continue
                elif banned_id[i][j] != case[i][j]:
                    return False
    return True
 
def solution(user_id,banned_id):
    answer=[]
    cases=list(itertools.permutations(user_id,len(banned_id)))
    for case in cases:
        if check(case,banned_id):
            case=set(case)
            if case not in answer:
                answer.append(case)
    return len(answer)
cs

문제링크:

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

 

코딩테스트 연습 - 불량 사용자

개발팀 내에서 이벤트 개발을 담당하고 있는 무지는 최근 진행된 카카오이모티콘 이벤트에 비정상적인 방법으로 당첨을 시도한 응모자들을 발견하였습니다. 이런 응모자들을 따로 모아 불량 ��

programmers.co.kr

 

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

[BOJ]9506. 약수들의 합  (0) 2020.06.09
[Programmers]2018 Kakao[1차]추석 트래픽  (0) 2020.05.26
[Programmers]2019 Kakao 불량 사용자  (0) 2020.05.21
[BOJ]2468. 안전 영역  (0) 2020.05.19
[BOJ]2167. 2차원 배열의 합  (0) 2020.05.14
[BOJ]1350. 진짜 공간  (0) 2020.05.12

문제:

풀이방법:

 문자열을 처리하고 규칙에 따라 정리를 하면 되는 문제이다.

우선 양 끝은 {{~~}}으로 고정이 되어 있다. 따라서 슬라이싱을 통해서 이 부분을 떼어내고 숫자들을 구분하기 위해서    '}.{'로 split을 한다. 이렇게 하면 ['2', '2,1' , '2,1,3' , '2,1,3,4'] 와 같이 분리되게 된다.

 반복문으로 순환을 하면서 다시 ','을 기준으로 분리를 하면 숫자만 남게 되는데 이를 각 원소값이 int인 list로 tuples에 정리하게 된다. 이 단계까지 마치면 문자열을 규칙에 적용할 수 있도록 정리가 마무리 되었다.

 

규칙은 다음과 같다.

1. 각 list들을 길이가 짧은 순으로 정렬을 한다.

2. list의 숫자 값을 탐색하며 answer list에 없는 값이라면 answer에 넣고 break를 한 뒤 다음 list를 탐색한다.

 

따라서 이 규칙을 끝까지 적용하면 answer를 얻을 수 있다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def solution(s):
    answer=[]
    splitS=s[2:-2].split("},{")
    tuples=[]
    for S in splitS:
        parser=S.split(',')
        tuples.append(list(map(int,parser)))
    tuples.sort(key = len)
    for tu in tuples:
        for t in tu:
            if t not in answer:
                answer.append(t)
                break
    return answer
cs

문제링크:

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

 

프로그래머스

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

programmers.co.kr

 

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

[BOJ]1350. 진짜 공간  (0) 2020.05.12
[BOJ]5014. 스타트링크  (0) 2020.05.07
[2019 Kakao winter internship]튜플  (0) 2020.04.23
[2019 Kakao winter internship]크레인 인형뽑기 게임  (0) 2020.04.21
[BOJ]2863. 이게 분수?  (0) 2020.04.16
[BOJ]7785. 회사에 있는 사람  (0) 2020.04.14

문제:

풀이방법:

문제에서 주어진대로 구현을 해도 되지만 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
[2019 Kakao winter internship]크레인 인형뽑기 게임  (0) 2020.04.21
[BOJ]2863. 이게 분수?  (0) 2020.04.16
[BOJ]7785. 회사에 있는 사람  (0) 2020.04.14
[BOJ]1718. 암호  (0) 2020.04.09

문제:

풀이방법:

트리 구조를 알고 있는지 물어보는 문제인 것 같다. 따라서 Tree라는 class를 만들고, 이 클래스는 x,y 좌표와 left, right를 만들어서 node 연결을 하도록 한다.

 

우선 부모 노드를 찾고, 자식 노드들을 알기 위해서 정렬을 하는 작업을 먼저 한다. y가 큰 순으로, x가 작은 순으로 정렬하도록 하기 위해 sorted의 key를 사용하였다.

 

이렇게 root를 찾고 남은 node들은 root부터 시작하여서 x 좌표를 비교해서 이 값이 left 혹은 right인지 확인을 한다. 만약 현재 node에서 이미 left나 right 값이 있다면 그 노드로 이동해서 다시 비교를 하고 지정해주는 작업을 계속해서 반복한다. 따라서 얼마나 많은 반복을 해야할지 모르기 때문에 while을 사용하였으며, 연결을 완료하면 break로 나오도록 하였다.

 

node 연결을 마친 뒤에 preorder와 postorder는 정의대로 재귀를 사용해서 배열에 담아서 return 하도록 한다. 다만 이 때 많은 node들이 있으면 python의 재귀 메커니즘상 런타임 에러가 발생한다고 한다.

(python은 재귀가 최대 1000회로 제한되어 있다.)

따라서 이를 해결하기 위해서 sys.setrecursionlimit()를 사용해서 최댓값을 넉넉히 늘려주도록 한다.

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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
import sys
 
sys.setrecursionlimit(10**6)
 
class Tree:
    def __init__(self,data,left=None,right=None):
        self.data = data
        self.left = left
        self.right = right
        
preorderList=[]
postorderList=[]
        
        
def preorder(node,nodeinfo):
    preorderList.append(nodeinfo.index(node.data)+1)
    if node.left:
        preorder(node.left,nodeinfo)
    if node.right:
        preorder(node.right,nodeinfo)
 
def postorder(node,nodeinfo):
    if node.left:
        postorder(node.left,nodeinfo)
    if node.right:
        postorder(node.right,nodeinfo)
    postorderList.append(nodeinfo.index(node.data)+1)
    
        
    
def solution(nodeinfo):
    
    answer=[]
    sortedNodeinfo=sorted(nodeinfo,key=lambda x : (-x[1],x[0]))
    
    root = None
    for node in sortedNodeinfo:
        if not root:
            root = Tree(node)
        else:
            current=root
            while True:
                if node[0< current.data[0]:
                    if current.left:
                        current = current.left
                        continue
                    else:
                        current.left = Tree(node)
                        break
                if node[0> current.data[0]:
                    if current.right:
                        current = current.right
                        continue
                    else:
                        current.right = Tree(node)
                        break
                break
                
    preorder(root,nodeinfo)
    postorder(root,nodeinfo)
    answer.append(preorderList)
    answer.append(postorderList)
    
    return answer
cs

문제링크:

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

 

코딩테스트 연습 - 길 찾기 게임 | 프로그래머스

[[5,3],[11,5],[13,3],[3,5],[6,1],[1,3],[8,6],[7,2],[2,2]] [[7,4,6,9,1,8,5,2,3],[9,6,5,8,1,4,3,2,7]]

programmers.co.kr

 

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

[BOJ]13458. 시험 감독  (0) 2020.03.05
[BOJ]6588. 골드바흐의 추측  (0) 2020.03.03
[Programmers]2019 Kakao.길 찾기 게임  (0) 2020.02.27
[BOJ]13305. 주유소  (0) 2020.02.25
[BOJ]2485. 가로수  (0) 2020.02.20
[BOJ]1182. 부분수열의 합  (0) 2020.02.18

문제:

카드게임이 있다. 게임에 사용하는 각 카드에는 양의 정수 하나가 적혀있고 같은 숫자가 적힌 카드는 여러 장 있을 수 있다. 게임방법은 우선 짝수개의 카드를 무작위로 섞은 뒤 같은 개수의 두 더미로 나누어 하나는 왼쪽에 다른 하나는 오른쪽에 둔다.

 

각 더미의 제일 위에 있는 카드끼리 서로 비교하며 게임을 한다. 게임 규칙은 다음과 같다. 지금부터 왼쪽 더미의 제일 위 카드를 왼쪽 카드로, 오른쪽 더미의 제일 위 카드를 오른쪽 카드로 부르겠다.

 

1. 언제든지 왼쪽 카드만 통에 버릴 수도 있고 왼쪽 카드와 오른쪽 카드를 둘 다 통에 버릴 수도 있다. 이때 얻는 점수는 없다.

2. 오른쪽 카드에 적힌 수가 왼쪽 카드에 적힌 수보다 작은 경우에는 오른쪽 카드만 통에 버릴 수도 있다. 오른쪽 카드만 버리는 경우에는 오른쪽 카드에 적힌 수만큼 점수를 얻는다.

3. (1)과 (2)의 규칙에 따라 게임을 진행하다가 어느 쪽 더미든 남은 카드가 없다면 게임이 끝나며 그때까지 얻은 점수의 합이 최종 점수가 된다.

 

왼쪽 더미의 카드에 적힌 정수가 담긴 배열 left와 오른쪽 더미의 카드에 적힌 정수가 담긴 배열 right가 매개변수로 주어질 때, 얻을 수 있는 최종 점수의 최대값을 return 하도록 solution 함수를 작성하시오.

풀이방법:

동적 계획법을 사용해서 푸는 문제이다. 오른쪽을 버릴 때에만 점수를 얻을 수 있으므로, 오른쪽을 많이 버릴 수 있으면 좋다. 그래서 우선 오른쪽을 먼저 버릴 수 있는지 확인을 하고, 왼쪽과 둘 다 버리는 경우를 생각해서 계산한다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
def solution(left,right):
    dp = [[-1 for _ in range(len(right)+1)]for _ in range(len(left)+1)]
    dp[0][0]=0
    answer=0
    
    for i in range(len(left)):
        for j in range(len(right)):
            if dp[i][j]==-1:
                continue
            if left[i] > right[j] and dp[i][j+1< dp[i][j]+right[j]:
                dp[i][j+1]=dp[i][j]+right[j]
            if dp[i+1][j+1< dp[i][j]:
                dp[i+1][j+1]=dp[i][j]
            if dp[i+1][j] < dp[i][j]:
                dp[i+1][j] = dp[i][j]
                
    for i in range(len(left)):
        if dp[i][len(right)] > answer:
            answer = dp[i][len(right)]
        if dp[i][len(left)] > answer:
            answer = dp[i][len(left)]
            
    return answer
cs

문제링크:

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

 

코딩테스트 연습 - 카드 게임 | 프로그래머스

카드게임이 있다. 게임에 사용하는 각 카드에는 양의 정수 하나가 적혀있고 같은 숫자가 적힌 카드는 여러 장 있을 수 있다. 게임방법은 우선 짝수개의 카드를 무작위로 섞은 뒤 같은 개수의 두 더미로 나누어 하나는 왼쪽에 다른 하나는 오른쪽에 둔다. 각 더미의 제일 위에 있는 카드끼리 서로 비교하며 게임을 한다. 게임 규칙은 다음과 같다. 지금부터 왼쪽 더미의 제일 위 카드를 왼쪽 카드로, 오른쪽 더미의 제일 위 카드를 오른쪽 카드로 부르겠다. 1. 언제든지

programmers.co.kr

 

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

[BOJ]1297. TV 크기  (0) 2020.02.06
[BOJ]10026. 적록색약  (0) 2020.02.04
[Programmers]Lv 4. 카드 게임  (0) 2020.01.23
[BOJ]1012. 유기농 배추  (0) 2020.01.21
[BOJ]10815. 숫자카드  (0) 2019.12.13
[BOJ]2033. 반올림  (0) 2019.12.12

+ Recent posts