미정

문제 설명

Leo는 카펫을 사러 갔다가 아래 그림과 같이 중앙에는 노란색으로 칠해져 있고 테두리 1줄은 갈색으로 칠해져 있는 격자 모양 카펫을 봤습니다.

Leo는 집으로 돌아와서 아까 본 카펫의 노란색과 갈색으로 색칠된 격자의 개수는 기억했지만, 전체 카펫의 크기는 기억하지 못했습니다.

Leo가 본 카펫에서 갈색 격자의 수 brown, 노란색 격자의 수 yellow가 매개변수로 주어질 때 카펫의 가로, 세로 크기를 순서대로 배열에 담아 return 하도록 solution 함수를 작성해주세요.

제한사항

• 갈색 격자의 수 brown은 8 이상 5,000 이하인 자연수입니다.
• 노란색 격자의 수 yellow는 1 이상 2,000,000 이하인 자연수입니다.
• 카펫의 가로 길이는 세로 길이와 같거나, 세로 길이보다 깁니다.

입출력 예brownyellowreturn

10	2	[4, 3]
8	1	[3, 3]
24	24	[8, 6]

풀이

def solution(brown, yellow):

    answer = []
    yellow_x = 0
    yellow_y = 0
    for i in range(1, yellow+1) :
        if yellow % i == 0 :
            yellow_x = int(yellow/i)
            yellow_y = i
            if yellow_x*2 + yellow_y*2 + 4 == brown :            
                answer.append(yellow_x+2)
                answer.append(yellow_y+2) 
                return sorted(answer, reverse = True)
    return answer

노란 격자의 가로(yellow_x)와 세로(yellow_y)를 이용해서 위와 같은 코드로 해결할 수 있다.

1부터 노란색의 개수만큼 for문으로 반복하면서 노란색의 수가 i로 나누어 떨어지면 노란색의 가로는 노란색을 i로 나눈 몫이되고, i는 노란색의 세로가 된다.

이때 위에서 언급한 수식을 사용하여 answer 리스트에 yellow_x+2와 yellow_y+2를 넣어준다.

가로가 세로보다 크거나 같아야 하기 때문에 내림차순으로 정렬을 한 리스트가 반환되도록 했다.

다른사람 풀이

def solution(brown, yellow):
    n = (brown-4)//2
    for i in range(n):
        x, y = i, n-i
        if x*y == yellow:
            return [y+2, x+2]

갈색 공간의 4개의 꼭짓점을 빼고 반으로 나누면, 노란색 구역의 가로+세로가 나오게 되며, for문을 돌면서 가로 * 세로가 노란색이 될 때, 가로+2, 세로+2 가 정답이 된다.

def solution(brown, yellow):
    total = brown + yellow
    # 카펫의 가로길이가 세로길이보다 크거나 같기 때문에 큰수에서 작은수로 반복
    for weight in range(total, 2, -1):
        if total % weight == 0: # 카펫넓이에서 가로길이 탐색
            height = total // weight # 카펫넓이 / 가로길이를 통해 세로길이 탐색
            # 구해진 카펫의 길이에서 테두리길이(2)만큼 빼주고 면적을 구한뒤 yellow의 면적과 같다면 해당 값 return
            if yellow == (weight-2) * (height-2):
                return [weight, height]

카펫의 넓이 = brown + yellow = width x height
외부 사각형 갯수(brown) = 2w + 2h + 4
내부 사각형 갯수(yellow) = (x-2) * (y-2)

문제 설명

풀이

def solution(n, words):
    rs=[] # 나온 단어 확인할 리스트
    for i in words:
        if i in rs: #같은 단어를 말했을때
            break
        if len(rs)!=0 and (rs[-1][-1]!=i[0]): # 앞단어의 뒷부분과 일치하지 않은 단어를 말했을때
            break
        rs.append(i)
        
    if len(rs)==len(words): # 문제없이 진행됐을시
        return [0,0]
    return [(len(rs)%n)+1, (len(rs)//n)+1]

1. word를 저장할 rs을 생성한다. rs는 나온 단어를 확인할 리스트이다.

2. words를 탐색하며 현재 word가 rs에 없고, rs의 마지막 원소의 마지막 문자가 현재 word의 첫번째 문자와 같다면 rs에 추가한다.

3. 위 조건에 맞지 않는다면 잘못된 단어이므로, 현재 word의 인덱스를 사용하여 탈락자 번호와 순서를 알아낸다.

result[0] = (len(rs) % n) + 1

result[1] = (len(rs) // n + 1

위 코드를 짧게 줄여보았다.

def solution(n, words):
    for i in range(1,len(words)):
        if words[i] in words[:i] or words[i][0]!=words[i-1][-1]:
            return [(i%n)+1,(i//n)+1]
    return [0,0]

• return 값은 >> 번호 = (i%n)+1, 차례 = (i//n)+1 << 이다.
• 비교를 할 때 words[i][0] != words[i-1][-1] 을 하기 때문에 반복문 범위는 1~len(words)로 해야한다.(0~len(words)로 하면 안 됨)

다른 사람의 풀이

def solution(n, words):
    answer = [0,0]

    cnt = 0  # 탈락번호,차례 계산할 변수
    checks = []  # 나온 단어 확인할 리스트
    checks.append(words[0])
    for i in range(1, len(words)):  # 단어 순회하면서
        cnt += 1
        # 아직 안나온 단어이면서 & 앞 단어의 마지막 알파벳과 일치하면 checks 리스트에 넣음 (pass)
        if words[i] not in checks and list(words[i-1])[-1] == list(words[i])[0]:
            checks.append(words[i])
        else:  # (fail)
            answer[0] = cnt%n +1  # 탈락번호
            answer[1] = cnt//n +1  # 탈락차례
            break

    return answer

Python의 if in 문법

문제가 좀 길어서 당황 했지만, 의외로 이런 문제가 더 쉬운 경향이 있다.

문제 설명

나의 풀이

def solution(s):
    answer = 0
    s = list(s)
    stack = []
    for i in s:
        if len(stack) == 0:
            stack.append(i)
        elif i == stack[-1]:
            stack.pop()
        else:
            stack.append(i)

    if len(stack) == 0:
        return 1  
    else:
        return 0

두 가지를 비교해서 같으면 pop, 아니면 남긴다는 말에 stack이 생각났다.

1. stack을 활용할 것. 이 문제는 스택을 이용해서 풀었다.
2. s에 들어있는 문자를 하나씩 뽑아 스택에 있는 문자랑 비교하고
3. 만약 같다면 스택에 있는 문자 pop
4. 만약 다르다면 s에 들어있는 문자를 스택에 넣기

stack을 사용하지 않고 while, for문으로 앞 뒤 값을 비교 후 replace() 함수를 사용하는 방식으로 처음에 풀었는데, 시간 초과문제가 발생한다. 문자열 길이가 1,000,000이하이기 때문에 너무 큰 배열이 들어온다면 그럴 수 밖에 없을 것이라고 생각되었다. 그러다 stack이 생각이 났고, stack을 활용해 쉽게 문제를 해결할 수 있었다.

문제 설명

def solution(n):
    c = bin(n).count('1')
    for m in range(n+1, 1000001):
        if bin(m).count('1') == c:
            return m

• 2진수를 구하는 함수는 bin()이다. https://eesko.tistory.com/150

문제 설명

나의 풀이

def solution(n):
    answer = [0,1]			# F(0)=0, F(1)=1
    for i in range(2,n+1):	
        answer.append((answer[i-1] + answer[i-2]) % 1234567)
    
    return answer[-1] # return answer[n]

• F(0)=0, F(1)=1
• F(n) = (F(n-1) + F(n-2)) % 1234567
• 마지막 결과를 return

(A+B) % C 와 (A % C + B %C) % C가 같다는 나머지 연산 법칙만 알면 쉽게 풀 수 있다.

다이나믹 프로그래밍은 작은것부터 시작해서 큰걸 알아내는 기법이기 때문에

여기에서는 f[0]와 f[1]을 먼저 구해두고 2부터는 f[i] = f[i-1] + f[i-2] 라는 식으로 반복문을 돌리면 된다.

다른사람 풀이

def solution(n):
    a,b = 0,1
    for i in range(n):
        a, b = b, (a+b)%1234567
    return a

문제 설명

나의 풀이

def solution(n):     
    count = 0
    for i in range(1, n+1):         
        sum = 0                     
        for j in range(i, n+1):    
            sum += j               
            if sum == n:           
                count += 1          
                break
            if sum > n:            
                break
    return count

• 우선 문제에서 "연속한 자연수들로 표현 하는 방법"은 더하기만 생각하면 된다.
• 연속된 숫자의 합이므로 하나의 값을 시작으로 다시 반복문을 실행시켜야 한다.
• 예시를 보면  `15=15`도 있기 때문에 n+1 까지 반복문 실행
• i값을 시작으로 반복문 실행
• i값부터 계속해서 값을 더해준다.
• 더한 값이(sum)이 n과 같다면 count +1, 아니면 break
• 더한 값(sum)이 n보다 크다면 계산할 필요가 없음. 계속해서 더해지는 값(sum)이 n보다 커지는 순간 break
•  

다른 사람의 풀이

def solution(n):
    answer = 0
    for i in range(1, n + 1):
        s = 0
        while s < n:
            s += i
            i += 1
        if s == n:
            answer += 1


    return answer

스택/큐

문제 설명

def solution(s):
    stack = []
    for i in s:
        if i == '(':
            stack.append(i)
        else:
            if stack == []: # 오른쪽 괄호로 시작할경우
                return False
            else:
                stack.pop()
    if stack != []: # 다 끝났는데 왼쪽 괄호가 스택에 남아있을경우
        return False
    return True

문제 설명

def solution(A,B):
    answer = 0
    A.sort(reverse = True)
    B.sort()
    for i in range(len(A)):
        answer += A[i] * B[i]
    return answer