수학과의 개발자 도전기

- 문제 : https://school.programmers.co.kr/learn/courses/30/lessons/12981

Lv2 문제고, 스스로 푼 문제다!

문제 이해 

이미 말한 단어들을 담는 리스트는 passed로 하고, 조건을 만족하는 단어들을 passed.append()한다 

1번 부터 n번까지의 사람의 번호를 식별하기 위해 i를 이용했고, i == n + 1일 때는 다시 1번으로 바꿔주고 이 때 한 사이클을 돌았으니까 count += 1 해준다 

passed에 있는 단어를 말하거나 전 사람이 말한 단어의 끝 단어로 시작하는 단어를 말하지 않는 경우 while문을 break 한다. 여기서 주의해야할게 if len(passed) > 0이 없으면, 처음 시작할 때는 passed =[] 이므로 Indexerror가 날 수 있다. 

끝말 잇기가 중간에 멈춘경우를 식별하기 위해 flag를 이용했고, 이 값이 False이면 멈춘 사람의 번호와 사이클 횟수를 반환하고 끝까지 간 경우에는 flag == True이므로 [0,0]을 반환해준다

주의해야할 점 

1. pass는 연산자이므로, 변수이름으로 사용하면 안된다

2. while문에서 끝말잇기 조건 만족하는 단어 passed.append()하는거 빼먹었다 

3. i += 1 빼먹었다

4. return 하는 순서 바꿔서 반환했다

- 정답 풀이 :

def solution(n, words):
    m = len(words)
    passed = []
    i = 1
    count = 1
    flag = True
    while words : 
        if i == n + 1:
            i = 1
            count += 1
        x = words.pop(0)
        if x in passed:
            flag = False
            break
        elif len(passed) > 0:
            if passed[-1][-1] != x[0]:
                flag = False
                break
        passed.append(x)
        i += 1
    
    if not flag: 
        return [i, count]
    else: 
    	return [0,0]

- 문제 : https://school.programmers.co.kr/learn/courses/30/lessons/70129

Lv2 문제이고, 스스로 푼 문제다!

처음에 이진법을 직접구현 하다보니 무한루프가 발생해 시간초과 에러가 났다. 그리고 매번 0을 제거하는 연산을 했는데, 그럴 필요가 없이

루프 때마다 0과 1의 갯수만 세면 된다. 

이진법 직접 구하는게 어려워서 내장함수 bin()을 찾았다. bin(십진수)를 입력하면 '0b[이진수]'를 반환한다. 

그래서 각 단계마다 1의 갯수를 bin()으로 이진법으로 변환한뒤 2번째 인덱스부터 s에 입력하면 된다 

주의할 점: 

루프가끝날 때는 1만 남은 경우이므로 1의 갯수가 1이고, 길이도 1일 때로 조건을 달아야한다 

- 정답 풀이 :

def solution(s):
    count, zero = 0, 0
    s = list(s)
    one = s.count('1')
    
    while True:
        if one == 1 and len(s) == 1:
            break
        zero += s.count('0')
        one = s.count('1')
        #one를 이진수로 바꾸고 싶다
        s = bin(one)
        s = s[2 : ]
        count += 1
        
    return [count, zero]

- 시도해본 풀이 

아마 n이 중복돼서 무한루프에 빠졌던 것 같다 

def solution(s):
    count, zero = 1, 0
    
    while s != '1':
        num = list(s)
        n = num.count('1')
        zero += num.count('0')
        s = ''
        for i in range(n - 1, 0, -1):
            if n % (2 ** i) == 0:
                s += '1'
            else:
                s += '0'
        count += 1
        
    return [count, zero]

- 문제 : https://school.programmers.co.kr/learn/courses/30/lessons/60057

풀이 설명

1.

i (1부터 n까지)단위마다 각각 반복하면서 문자열을 압축한다 

temp는 길이 i의 문자열이고, temp와 같은 문자의 갯수는 count로 센다. 

count는 1로 초기화한다 (temp가 하나만 있어도 되므로 )

result는 i단위로 압축할 때 만들어지는 전체 문자를 의미한다 

2.

i 단위로 진행해야하기 때문에 for j in range(0, n + i, i)로 반복문을 돌린다 (왜 그런지는 '시도해본 풀이'에 적어놨다)

temp와 같은 문자열이라면 count += 1 해준다

3. 

temp와 같은 문자열이 아닐때는 2가지가 있다. 

• 첫번째는 count == 1인 경우인데 이때 1은 생략하므로 result 에 temp만 더해준다 
• count > 1이라면 반복되는 문자열이 2개이상이므로 숫자 + 문자열을 result에 더해준 뒤 새롭게 반복되는 문자열을 세야하므로 count = 1로 초기화한다 (count == 1일 때는 어차피 count는 1이므로 따로 설정 안 했다)

4.

temp는 i번째만큼 이동한 문자열로 바꾼다(문자열이 반복되는 경우나 같지 않은 경우 모두 똑같다)

5. 

i단위로 돌린 최종 결과 result와 answer의 최솟값을 answer에 누적한 후 answer를 반환하면 된다 

참고한 블로그

- 정답 풀이 : 

def solution(s):
    n = len(s)    
    answer = 1001

    for i in range(1, n + 1):
        temp = s[ : i]
        count = 1
        result = ''
        for j in range(i, n + i, i):
            if temp == s[j : j + i] :
                count += 1
            else:
                if count == 1:
                    result += temp
                else: 
                    result += (str(count) + temp)
                    count = 1                
                temp = s[j : j + i]      
        answer = min(answer, len(result))
        
    return answer

- 시도해본 풀이 :

for j in range(i, n + 1, i)
-> for j in range(i, n + i, i)

i 단위로 i 부터 n까지만 탐색하면 반복되지 않지만 길이가 정답 길이보다 작은 경우가 발생해서 틀린답을 출력할 수 있다 

그래서 반복되지 않아도 i단위로 문자열 끝까지 진행하게 하기위해 끝점을 n + i로 해야한다 

def solution(s):
    n = len(s)    
    answer = 1001

    if n == 1:
        return 1
    for i in range(1, n + 1):
        temp = s[ : i]
        count = 1
        result = ''
        for j in range(i, n + 1, i):
            if temp == s[j : j + i] :
                count += 1
            else:
                if count == 1:
                    result += temp
                else: 
                    result += (str(count) + temp)
                    count = 1
                
            temp = s[j : j + i]
                    
        answer = min(answer, len(result))
        
    return answer

- 문제 풀이 : https://school.programmers.co.kr/learn/courses/30/lessons/62048

Lv2. 문제 

풀이는 짧은데 생각을 잘해야 했던 문제다 

1. 사각형의 가로 세로가 서로소인 경우에는 대각선을 그으면 w + h - 1 만큼의 사각형을 지나간다 

이유를 생각해보니 두 수가 서로소니까 2차 평면에서 사각형 내에 정확히 지나는 점이 없다 

그래서 사각형 내부를 가르면서 지나가야하는데, 그게 각 가로에 있는 사각형 하나씩 총 w번, 

세로에 있는 사각형 하나씩 총 h번을 지나가는데 처음 사각형 하나가 겹치므로 w + h -1 을 해줘야한다. 

2. 만약 서로소가 아니라면 같은 크기의 사각형이 w,h의 최대 공약수(g) 갯수만큼 반복된다 

-> g * (w//g + h//g -1) 

-> w + h - g

이때 g == 1인 경우가 서로소인 경우이므로 일반식은 다음과 같다 

w + h - math.gcd(w,h)

전체에서 이만큼을 빼야 멀쩡한 정사각형의 갯수를 구할 수 있다

참고한 블로그

- 정답 풀이 : 

import math
def solution(w,h):
    return w * h - (w + h - math.gcd(w,h))