'Algorithm/Python' 카테고리의 글 목록 (43 Page)

728x90

문제:

효진이는 멀리 뛰기를 연습하고 있습니다. 효진이는 한번에 1칸, 또는 2칸을 뛸 수 있습니다. 칸이 총 4개 있을 때, 효진이는

(1칸,1칸,1칸,1칸)

(1칸,2칸,1칸)

(1칸,1칸,2칸)

(2칸,1칸,1칸)

(2칸,2칸)

의 5가지 방법으로 맨 끝 칸에 도달할 수 있습니다. 멀리 뛰기에 사용될 칸의 수 n이 주어질 때, 효진이가 끝에 도달하는 방법이 몇 가지인지 알아내, 여기에 1234567를 나눈 나머지를 리턴하는 함수, solution을 완성하세요. 예를 들어 4가 입력된다면,5를 return하면 됩니다.

풀이 방법:

임의의 수 n이 주어졌다고 하자. 한번에 움직일 수 있는 칸은 1칸 혹은 2칸이기 때문에 n으로 이동하기 위해서는 n-2칸에서 2칸을 사용해서 n번째 칸으로 오거나 n-1에서 1칸을 이동해서 n칸으로 이동하는 방법이 있다. 재귀를 사용해서 풀어도 괜찮으나 피보나치 수열을 이루기 때문에 피보나치 수열을 이용해서 풀었다.

1
2
3
4
5
def solution(n):
    a,b =1,2
    for i in range(n-1):
        a,b=b,a+b
    return a%1234567
cs

728x90

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

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

[Programmers]Lv 3. 방문길이 (0)	2019.03.13
[Programmers]Lv 2.숫자의 표현 (0)	2019.03.12
[Programmers]Lv 2.폰켓몬 (0)	2019.03.10
[Programmers]Lv 3.베스트앨범 (0)	2019.03.09
[Programmers]Lv 2.땅따먹기 (0)	2019.03.08

728x90

문제:

당신은 폰켓몬을 잡기 위한 오랜 여행 끝에, 홍 박사님의 연구실에 도착했습니다. 홍박사님은 당신에게 자신의 연구실에 있는 총 N 마리의 폰켓몬 중에서 N/2마리를 가져가도 좋다고 했습니다.

홍 박사님 연구실의 폰켓몬은 종류에 따라 번호를 붙여 구분합니다. 따라서 같은 종류의 폰켓몬은 같은 번호를 가지고 있습니다. 예를 들어 연구실에 총 4마리의 폰켓몬이 있고, 각 폰켓몬의 종류 번호가 [3번,1번,2번,3번]이라면 이는 3번 폰켓몬 두 마리,1번 폰켓몬 한 마리, 2번 폰켓몬 한 마리가 있음을 나타냅니다. 이때, 4마리의 폰켓몬 중 2마리를 고르는 방법은 다음과 같이 6가지가 있습니다.

1.첫 번째(3번),두 번째(1번) 폰켓몬을 선택

2.첫 번째(3번),세 번째(2번) 폰켓몬을 선택

3.첫 번째(3번),네 번째(3번) 폰켓몬을 선택

4.두 번째(1번),세 번째(2번) 폰켓몬을 선택

5.두 번째(1번),네 번째(3번) 폰켓몬을 선택

6.세 번째(2번),네 번째(3번) 폰켓몬을 선택

이때, 첫 번째(3번) 폰켓몬과 네 번째(3번) 폰켓몬을 선택하는 방법은 한 종류(3번 폰켓몬 두 마리)의 폰켓몬만 가질 수 있지만, 다른 방법들은 모두 두 종류의 폰켓몬을 가질 수 있습니다. 따라서 위 예시에서 가질 수 있는 폰켓몬 종류 수의 최댓값은 2가 됩니다.

당신은 최대한 다양한 종류의 폰켓몬을 가지길 원하기 때문에, 최대한 많은 종류의 폰켓몬을 포함해서 N/2 마리를 선택하려 합니다. N마리 폰켓몬의 종류 번호가 담긴 배열 nums가 매개변수로 주어질 때, N/2마리의 폰켓몬을 선택하는 방법 중, 가장 많은 종류의 폰켓몬을 선택하는 방법을 찾아, 그때의 폰켓몬 종류 번호의 개수를 return 하도록 solution 함수를 완성해주세요.

풀이 방법:

이 문제는 크게 두 가지 경우가 있다. 폰켓몬의 종류의 갯수가 N/2마리보다 큰 경우와 작은 경우이다.

폰켓몬의 종류의 갯수가 N/2마리 보다 크다면 N/2마리를 선택하면 된다. 최대 선택할 수 있는 종류는 N/2이기 때문이다.

폰켓몬의 종류의 갯수가 N/2마리 보다 작다면 폰켓몬의 종류의 갯수를 선택하면 된다. 아무리 N/2마리를 골라도 중복이 발생하고 이를 제거 하면 결국 최댓값은 폰켓몬의 종류의 갯수가 되기 때문이다.

그렇다면 폰켓몬의 종류의 갯수를 구하는 것이 중요한데, python에서 중복을 제거 할 수 있는 가장 좋은 방법은 set을 이용하는 것이다. python의 자료형 중 집합 자료형인 set은 중복을 허용하지 않고, 정렬이 되어 있지 않다는 것이다. 따라서 nums를 set으로 한번 감싸고 난 뒤의 길이를 이용해서 N/2와 비교하면 된다.

1
2
3
4
5
def solution(num):
    if len(list(set(num))) < len(num)/2:
        return int(len(list(set(num))))
    else:
        return int(len(num)/2)
cs

728x90

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

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

[Programmers]Lv 2.숫자의 표현 (0)	2019.03.12
[Programmers] Lv 3. 멀리 뛰기 (0)	2019.03.11
[Programmers]Lv 3.베스트앨범 (0)	2019.03.09
[Programmers]Lv 2.땅따먹기 (0)	2019.03.08
[Programmers] Lv 3. 등굣길 (2)	2019.03.07

728x90

문제:

스트리밍 사이트에서 장르 별로 가장 많이 재생된 노래를 두 개씩 모아 베스트 앨범을 출시하려 합니다. 노래는 고유 번호로 구분하며, 노래를 수록하는 기준은 다음과 같습니다.

1. 속한 노래가 많이 재생된 장르를 먼저 수록합니다.

2. 장르 내에서 많이 재생된 노래를 먼저 수록합니다.

3. 장르 내에서 재생 횟수가 같은 노래 중에서는 고유 번호가 낮은 노래를 먼저 수록합니다.

노래의 장르를 나타내는 문자열 배열 genres와 노래별 재생 횟수를 나타내는 정수 배열 plays가 주어질 때, 베스트 앨범에 들어갈 노래의 고유 번호를 순서대로 return 하도록 solution 함수를 완성하세요.

풀이 방법:

노래의 장르를 나타내는 문자열 배열 genres와 노래별 재생 횟수를 나타내는 정수 배열 plays를 노래를 수록하는 기준에 따라서 해시로 구성해서 풀어야 하는 문제이다.

우선 기준 1에 의해 속한 노래가 많이 재생된 장르를 먼저 수록해야 하므로 장르별로 재생된 횟수를 나타내는 해시인 sum_set을 만들어야 한다. 이와 동시에 기준 2 장르 내에서 많이 재생된 노래를 먼저 수록해야 하므로 장르를 key 값으로 가지고 그 장르의 노래별 재생 횟수를 리스트를 value 값으로 가지는 해시인 playlist_set을 만들도록 한다. 문제에서 제공하는 입출력 예시를 정리해보면 다음과 같이 만들어 진다.

sum_set= {'classic': 1450, 'pop': 3100}
playlist_set={'classic': [500, 150, 800], 'pop': [600, 2500]}

sum_set의 item 리스트를 가져와서 value 값을 기준으로 정렬을 한 뒤에 정렬된 key 값으로 playlist_set에 접근을 하도록 한다. playlist_set의 value 값을 정렬한 뒤에 맨 뒤의 두 값이 최대값들이므로 이를 이용해서 plays에서 인덱스 값을 찾아서 answer에 넣어주면 된다. 다만 기준 3에 의해서 재생 횟수가 같다면 고유 번호가 낮은 노래를 먼저 수록해야 하므로 최대값들이 같을 때와 다를 때를 구분해서 넣어주면 된다. plays에서 인덱스 값을 찾는 것은 index 내장함수를 사용했다. index 내장 함수는 시작점을 지정해줄 수 있으므로 재생 횟수가 같다면 두번째 최대값은 첫번째 최댓값의 인덱스 이후로 탐색하면 되기 때문이다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
def solution(genres,plays):
    sum_set={}
    playlist_set={}
    answer=[]
    for i in range(len(genres)):
        if genres[i] in sum_set:
            sum_set[genres[i]]+=plays[i]
            playlist_set[genres[i]].append(plays[i])
        else:
            sum_set[genres[i]]=plays[i]
            playlist_set[genres[i]]=[plays[i]]
    sum_list=sorted(list(sum_set.items()),key=lambda x:x[1],reverse=True)
    for i in sum_list:
        temp=sorted(playlist_set[i[0]])
        if len(temp)>=2:
            if temp[-1]==temp[-2]:
                answer.append(plays.index(temp[-1]))
                answer.append(plays.index(temp[-2],plays.index(temp[-1])+1))
            else:
                answer.append(plays.index(temp[-1]))
                answer.append(plays.index(temp[-2]))
        else:
            answer.append(plays.index(temp[0]))
    return answer
Colored by Color Scripter
cs

728x90

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

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

[Programmers] Lv 3. 멀리 뛰기 (0)	2019.03.11
[Programmers]Lv 2.폰켓몬 (0)	2019.03.10
[Programmers]Lv 2.땅따먹기 (0)	2019.03.08
[Programmers] Lv 3. 등굣길 (2)	2019.03.07
[Programmers]Lv 2.다음 큰 숫자 (0)	2019.03.06

728x90

문제:

땅따먹기 게임을 하려고 합니다. 땅따먹기 게임의 땅(land)은 총 N행 4열로 이루어져 있고, 모든 칸에는 점수가 쓰여 있습니다. 1행부터 땅을 밟으며 한 행씩 내려올 때, 각 행의 4칸 중 한 칸만 밟으면서 내려와야 합니다. 단, 땅따먹기 게임에는 한 행씩 내려올 때, 같은 열을 연속해서 밟을 수 없는 특수 규칙이 있습니다.

예를 들면

|1|2|3|5|

|5|6|7|8|

|4|3|2|1|

로 땅이 주어졌다면, 1행에서 네번째 칸 (5)를 밟았으면, 2행의 네번째 칸(8)은 밟을 수 없습니다.

마지막 행까지 모두 내려왔을 때, 얻을 수 있는 점수의 최대값을 return하는 solution 함수를 완성해 주세요. 위 예의 경우, 1행의 네번째 칸 (5), 2행의 세번째 칸 (7),3행의 첫번째 칸(4) 땅을 밟아 16점이 최고점이 되므로 16을 return 하면 됩니다.

풀이 방법:

이 문제도 동적계획법을 사용해서 풀 수 있다. 맨 위의 행부터 시작해서 아래로 진행을 하면서 행의 값들을 바꾸어 주면 된다. 행의 값들을 업데이트 할 때 같은 열을 연속해서 밟지는 못하므로 현재 열을 제외하고 이전 행에서 현재 열을 제외한 최댓값을 찾아서 현재 형,열에 값을 더해주면 된다. 이를 맨 밑의 행까지 계속해서 반복을 한다.

즉 예시는 다음과 같이 바뀔 수 있다.

|1|2|3|5| |1|2|3|5| |1|2|3|5|

|5|6|7|8| --> |10|11|12|11| --> |10|11|12|11|

|4|3|2|1| |4|3|2|1| |16|15|13|13|

1
2
3
4
5
def solution(land):
    for i in range(1,len(land)):
        for j in range(len(land[0])):
            land[i][j]=land[i][j]+max(land[i-1][:j]+land[i-1][j+1:])
    return max(land[-1])
Colored by Color Scripter
cs

728x90

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

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

[Programmers]Lv 2.폰켓몬 (0)	2019.03.10
[Programmers]Lv 3.베스트앨범 (0)	2019.03.09
[Programmers] Lv 3. 등굣길 (2)	2019.03.07
[Programmers]Lv 2.다음 큰 숫자 (0)	2019.03.06
[Programmers]Lv 2.올바른 괄호 (0)	2019.03.04

728x90

문제:

계속되는 폭우로 일부 지역이 물에 잠겼습니다. 물에 잠기지 않은 지역을 통해 학교를 가려고 합니다. 집에서 학교까지 가는 길은 m x n 크기의 격자모양으로 나타낼 수 있습니다.

가장 왼쪽 위, 즉 집이 있는 곳의 좌표는 (1,1)로 나타내고 가장 오른쪽 아래, 즉 학교가 있는 곳의 좌표는 (m,n)으로 나타냅니다. 격자의 크기 m,n과 물이 잠긴 지역의 좌표를 담은 2차원 배열 puddles이 매개변수로 주어질 때, 학교에서 집에서 갈 수 있는 최단경로의 개수를 1,000,000,007로 나눈 나머지를 return 하도록 solution 함수를 작성해주세요.

풀이 방법:

동적계획법을 사용하는 문제이므로 왼쪽 위 집에서 부터 하나씩 모든 경우의 수를 계산하며 학교를 가면 되는 문제이다.

예시로 (2,3)으로 가는 방법은 왼쪽에서 오는 방법과 위에서 오는 방법이 있다. 왜냐하면 최단 경로로 가기 위해서는 (1,1)에서 오른쪽이나 아래로만 움직여야 하기 때문이다. 따라서 (2,3)으로 오는 방법은 (1,3) 혹은 (2,2)에서 출발 해야 하는 것이다. 하지만 이 문제에선 물에 잠긴 지역이 있다면 아예 이동을 할 수 없으므로 puddles에 있는 원소 값들은 항상 0의 값을 가지도록 하면 된다.

이 문제의 예시로 표를 만들면 다음과 같이 만들어 진다.

	0	0	0	0
0	1(집)	1	1	1
0	1	0(물 웅덩이)	1	2
0	1	1	2	4(학교)

계산의 용이성을 위해서 m,n 칸의 표가 아닌 m+1,n+1 칸의 0 행렬을 만들었다. 또한 우리가 알고 있는 좌표 평면과 표에서 그려지는 좌표가 반대로 구성되어 있음을 알 수 있다. 따라서 puddles에 있는지 확인 하기 위해선 i,j 의 위치를 바꾸어서 확인을 해야한다.

1
2
3
4
5
6
7
8
9
10
11
12
def solution(m, n, puddles):
    answers=[[0]*(m+1) for i in range(n+1)]
    answers[1][1]=1
    for i in range(1,n+1):
        for j in range(1,m+1):
            if i==1 and j==1:
                continue
            if [j,i] in puddles:
                answers[i][j]=0
            else:
                answers[i][j]=answers[i-1][j]+answers[i][j-1]
    return answers[n][m]%1000000007
cs

728x90

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

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

[Programmers]Lv 3.베스트앨범 (0)	2019.03.09
[Programmers]Lv 2.땅따먹기 (0)	2019.03.08
[Programmers]Lv 2.다음 큰 숫자 (0)	2019.03.06
[Programmers]Lv 2.올바른 괄호 (0)	2019.03.04
[Programmers]Lv 1. 체육복(테스트케이스 수정) (0)	2019.03.03

728x90

문제:

자연수 n이 주어졌을 때, n의 다음 큰 숫자는 다음과 같이 정의 합니다.

조건 1. n의 다음 큰 숫자는 n보다 큰 자연수 입니다

조건 2. n의 다음 큰 숫자는 n은 2진수로 변환했을 때 1의 갯수가 같습니다.

조건 3. n의 다음 큰 숫자는 조건 1,2를 만족하는 수 중 가장 작은 수 입니다.

예를 들어서 78(1001110)의 다음 큰 숫자는 83(1010011)입니다.

자연수 n이 매개변수로 주어질 때, n의 다음 큰 숫자를 return 하는 solution 함수를 완성해주세요.

풀이 방법:

우선 자연수 n의 이진수 값을 구하기 위해서 내장함수인 bin을 사용하였다. bin은 십진수의 값을 이진수로 변환해주는 함수다. 단 이진수 앞 부분에 '0x' 가 붙으며 문자열로 반환을 한다. 하지만 문제에선 1의 갯만 필요하므로 상관 없이 1의 갯수를 세주도록 한다.

이 후 다음 큰 숫자를 찾기 위해서 n부터 1씩 증가하며 n의 1의 갯수와 같을 때까지 계속 반복하면 된다.

1
2
3
4
5
6
7
8
9
10
11
def solution(n):
    answer=n
    n_count=bin(n).count('1')
    conti=True
    while conti:
        answer+=1
        temp=answer
        n_next_count=bin(temp).count('1')
        if n_count == n_next_count:
            break     
    return answer
cs

728x90

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

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

[Programmers]Lv 2.땅따먹기 (0)	2019.03.08
[Programmers] Lv 3. 등굣길 (2)	2019.03.07
[Programmers]Lv 2.올바른 괄호 (0)	2019.03.04
[Programmers]Lv 1. 체육복(테스트케이스 수정) (0)	2019.03.03
[Programmers]Lv 3. 이중우선순위큐 (1)	2019.03.03

728x90

문제:

올바른 괄호란 두 개의 괄호 '(' 와 ')' 만으로 구성되어 있고, 괄호가 올바르게 짝지어진 문자열입니다. 괄호가 올바르게 짝지어졌다는 것은 '(' 문자로 열렸으면 반드시 짝지어서 ')' 문자로 닫혀야 합니다.

예를 들어

"()()" 또는 "(())()"는 올바른 괄호입니다.

")()(" 또는 "(()("는 올바르지 않은 괄호입니다.

'(' 또는 ')' 로만 이루어진 문자열 s가 주어졌을 때, 문자열 s가 올바른 괄호이면 true를 return 하고, 올바르지 않은 괄호이면 false를 return하는 solution 함수를 완성해주세요.

풀이 방법:

'(' 는 +1의 값을 가지고 ')'이 -1의 값을 가진다고 하자.

모두 정상적으로 짝을 이뤘다. 즉 "(" 와 ")"의 갯수가 동일하다면 문자열 s를 반복문으로 한 번씩 탐색해보았을 때 count의 값이0이 되어야 할 것이다.

만약 count의 값이 양수가 나온다면 "("가 더 있는 것이고 음수면 그 반대일 것이다.

하지만 괄호의 갯수는 맞게 이루어져있지만 반대로 있을 수도 있다. (ex ")(" )

이와 같은 경우에는 문자열의 합은 0이 나오지만 올바르지 않은 괄호이다. 따라서 조건을 하나 더 추가를 해줘야 한다.

문제가 발생 할 때에는 ")"에서 나오게 된다. "("로 열지도 않았는데 ")"로 닫아버릴 때 오류가 발생한다. 즉 count값이 순간적으로 마이너스가 될 경우가 오류가 발생하게 된다.

1
2
3
4
5
6
7
8
9
10
11
12
13
def solution(s):
    count=0
    for i in s:
        if i is '(':
            count+=1
        elif i is ')':
            count-=1
            if count < 0 :
                return False
    if count == 0:
        return True
    else:
        return False
cs

728x90

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

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

[Programmers] Lv 3. 등굣길 (2)	2019.03.07
[Programmers]Lv 2.다음 큰 숫자 (0)	2019.03.06
[Programmers]Lv 1. 체육복(테스트케이스 수정) (0)	2019.03.03
[Programmers]Lv 3. 이중우선순위큐 (1)	2019.03.03
[Programmers]Lv 2.가장 큰 정사각형 찾기 (0)	2019.03.02

728x90

2019/02/13 - [Algorithm/Python] - [Programmers]Lv 1. 체육복

이전에 풀었던 문제인데 2.28일 이후로 테스트케이스가 추가되면서 하나의 케이스가 통과하지 못한다.

이전에는 조금 명시적으로 여분을 가지고 있는 학생이 구분이 되지 않았는데 더 명시적으로 여분을 가지고 있는 사람에게만 빌리게 하였더니 통과를 하였다.

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
def solution(n,lost,reserve):
    cloth=[1]*n
    for i in range(n):
        if i+1 in reserve:
            cloth[i]=2
        if i+1 in lost:
            cloth[i]-=1
    if cloth[0]==0:
        if cloth[1]==2:
            cloth[0]+=1
            cloth[1]-=1
    for i in range(1,n-1):
        if cloth[i]==0:
            if cloth[i+1]==2:
                cloth[i]+=1
                cloth[i+1]-=1
            elif cloth[i-1]==2:
                cloth[i]+=1
                cloth[i-1]-=1
    if cloth[-1]==0:
        if cloth[-2]==2:
            cloth[-1]+=1
            cloth[-2]-=1
    count=0
    for i in cloth:
        if i != 0:
            count+=1
    return count
cs

728x90

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

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

[Programmers]Lv 2.다음 큰 숫자 (0)	2019.03.06
[Programmers]Lv 2.올바른 괄호 (0)	2019.03.04
[Programmers]Lv 3. 이중우선순위큐 (1)	2019.03.03
[Programmers]Lv 2.가장 큰 정사각형 찾기 (0)	2019.03.02
[Programmers]Lv 3. 입국 심사 (2)	2019.03.01

728x90

문제:

이중 우선순위 큐는 다음 연산을 할 수 있는 자료구조를 말합니다.

명령어	수신 탑(높이)
I 숫자	큐에 주어진 숫자를 삽입합니다.
D 1	큐에서 최댓값을 삭제합니다.
D -1	큐에서 최솟값을 삭제합니다.

이중 우선순위 큐가 할 연산 operations가 매개변수로 주어질 때, 모든 연산을 처리한 후 큐가 비어있으면 [0,0] 비어있지 않으면 [최댓값,최솟값]을 return 하도록 solution 함수를 구현해주세요.

풀이 방법:

힙을 사용해서 풀어야 하는 문제지만 굳이 힙을 사용해서 풀지 않아도 상관 없다. operations를 반복문의 매개변수로 받아 각 원소들을 공백으로 구분해보아서 명령어대로 배열에서 처리를 하면 문제없이 풀 수 있다. 삽입을 할 때 정수형으로 변경을 해서 넣는데 그 이유는 음수값들도 들어가기 때문에 정렬을 하기 위해서는 정수형으로 바꾸는 것이 필수적이기 때문이다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def solution(operations):
    answer=[]
    for i in operations:
        a,b=i.split(" ")
        if a=="I":
            answer.append(int(b))
        else:
            if len(answer)>0:
                if b=="1":
                    answer.pop()
                else:
                    answer.pop(0)
            else:
                pass
        answer.sort()
    if len(answer)==0:
        return [0,0]
    else:
        return [max(answer),min(answer)]
cs

만약 힙을 사용해서 풀고 싶다면 다음과 같이 하면 된다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
import heapq
def solution(operations):
    h=[]
    for i in operations:
        a,b=i.split(" ")
        if a=="I":
            heapq.heappush(h,int(b))
        else:
            if len(h)>0:
                if b=="1":
                    h.pop(h.index(heapq.nlargest(1,h)[0]))
                else:
                    heapq.heappop(h)
            else:
                pass
    if len(h)==0:
        return [0,0]
    else:
        return [heapq.nlargest(1,h)[0],heapq.nsmallest(1,h)[0]]
cs

728x90

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

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

[Programmers]Lv 2.올바른 괄호 (0)	2019.03.04
[Programmers]Lv 1. 체육복(테스트케이스 수정) (0)	2019.03.03
[Programmers]Lv 2.가장 큰 정사각형 찾기 (0)	2019.03.02
[Programmers]Lv 3. 입국 심사 (2)	2019.03.01
[Programmers]Lv 2. 타겟 넘버 (0)	2019.02.28

728x90

문제:

1과 0로 채워진 표(board)가 있습니다. 표 1칸은 1 x 1 의 정사각형으로 이루어져 있습니다. 표에서 1로 이루어진 가장 큰 정사각형을 찾아 넓이를 return 하는 solution 함수를 완성해 주세요.( 단, 정사각형이란 축에 평행한 정사각형을 말합니다.)

풀이 방법:

이 문제는 DP(dynamic programming), 동적계획법을 사용해서 풀어야 하는 문제이다. 왼쪽 위(1,1)부터 시작해서 오른쪽 아래로 진행을 하면서 정사각형을 나간다.

정사각형으로 취급되는 경우는 다음과 같다.

1(1번)	1(2번)
1(3번)	1(4번)

4번의 값이 0이 아니라면 1,2,3번의 값을 비교해 최소값을 찾은 뒤에 4번 자리에 그 최솟값에 1을 더한 값을 넣어 준다. 즉 다음과 같이 된다.

1(1번)	1(2번)
1(3번)	2(4번)

최솟값을 찾는 이유는 하나의 0이 있다면 정사각형의 형태가 아니므로 1 이상의 값들만 이어나가기 위함이다. 또한 1을 더해주는 이유는 정사각형이라면 길이의 값을 누적하기 위해서이고 아니라면 남은 1의 값들이 다른 곳에서 정사각형을 이룰 수 있기 때문에 이어나가주는 것이다.

이 문제의 예시를 통해서 구하는 방법을 알아보자. 다음과 같이 처음 상태가 있다.

0	1	1	1
1	1	1	1
1	1	1	1
0	0	1	0

처음 왼쪽 위 (1,1)을 비교해 보았을 때 (0,0)이 0이기에 (1,1)의 값을 1로 바꾼다.

0	1	1	1
1	1	1	1
1	1	1	1
0	0	1	0

(1,2)의 값을 비교해 보았을 때 주위 최솟값이 1이므로 (1,2)의 값을 2로 바꾼다. 이 경우가 길이가 2인 정사각형을 찾은 경우이다. 하지만 가장 큰 정사각형을 찾는 것이 문제이므로 계속 탐색해보도록 한다.

0	1	1	1
1	1	2	1
1	1	1	1
0	0	1	0

(1,3)의 값을 비교해보았을 때, 주위 최솟값이 1이므로 (1,3)의 값을 2로 바꾼다. 이 경우도 역시 길이가 2인 정사각형을 찾은 경우다. 이전 (1,2)에서도 정사각형을 찾았지만 이 둘로는 정사각형이 아닌 직사각형이 만들어지므로 서로 영향을 주진 못한다.

0	1	1	1
1	1	2	2
1	1	1	1
0	0	1	0

계속해서 이 방법대로 진행을 하면 (2,2)까지 다음과 같이 표를 바꿀 수 있다.

0	1	1	1
1	1	2	2
1	2	2	1
0	0	1	0

(2,3)에서는 주위의 최솟값이 2이므로 (2,3)의 값을 3으로 바꾼다 즉 길이가 3인 정사각형을 찾은 경우다. 이 처럼 주위의 값들이 모두 2,2,2 혹은 3,3,3 과 같이 이루어져 있을 경우에 가장 큰 정사각형의 길이가 바뀌게 되는 것이다.

0	1	1	1
1	1	2	2
1	2	2	3
0	0	1	0

마지막 줄은 계속 진행해보아도 변경되는 점이 없으므로 이 예시의 가장 큰 정사각형은 길이가 3인 정사각형이다.

다른 채점케이스에서 전부다 0인 경우에는 위와 같은 방법으로 길이가 1인 정사각형이 있다고 나오므로 따로 구분해서 구하도록 하였다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
def solution(board):
    max_point=0
    for i in range(len(board)):
        max_point+=sum(board[i][:])
    if max_point==0:
        return 0
    max_point=0
    for i in range(1,len(board)):
        for j in range(1,len(board[0])):
            if board[i][j]==0:
                continue
            else:
                min_point=min(board[i][j-1],board[i-1][j],board[i-1][j-1])
                min_point+=1
                board[i][j]=min_point
                if max_point < board[i][j]:
                    max_point=board[i][j]
    if max_point==0:
        return 1
    else:
        return max_point**2
Colored by Color Scripter
cs

728x90

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

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

[Programmers]Lv 1. 체육복(테스트케이스 수정) (0)	2019.03.03
[Programmers]Lv 3. 이중우선순위큐 (1)	2019.03.03
[Programmers]Lv 3. 입국 심사 (2)	2019.03.01
[Programmers]Lv 2. 타겟 넘버 (0)	2019.02.28
[Programmers]Lv 3. 정수 삼각형 (0)	2019.02.27