IT-garden

문제 설명

직사각형 종이를 n번 접으려고 합니다. 이때, 항상 오른쪽 절반을 왼쪽으로 접어 나갑니다. 다음은 n = 2인 경우의 예시입니다.

먼저 오른쪽 절반을 왼쪽으로 접습니다.

다시 오른쪽 절반을 왼쪽으로 접습니다.

종이를 모두 접은 후에는 종이를 전부 펼칩니다. 종이를 펼칠 때는 종이를 접은 방법의 역순으로 펼쳐서 처음 놓여있던 때와 같은 상태가 되도록 합니다. 위와 같이 두 번 접은 후 종이를 펼치면 아래 그림과 같이 종이에 접은 흔적이 생기게 됩니다.

위 그림에서 ∨ 모양이 생긴 부분은 점선(0)으로, ∧ 모양이 생긴 부분은 실선(1)으로 표시했습니다.

종이를 접은 횟수 n이 매개변수로 주어질 때, 종이를 절반씩 n번 접은 후 모두 펼쳤을 때 생기는 접힌 부분의 모양을 배열에 담아 return 하도록 solution 함수를 완성해주세요.

제한조건

• 종이를 접는 횟수 n은 1 이상 20 이하의 자연수입니다.
• 종이를 접었다 편 후 생긴 굴곡이 ∨ 모양이면 0, ∧ 모양이면 1로 나타냅니다.
• 가장 왼쪽의 굴곡 모양부터 순서대로 배열에 담아 return 해주세요.

입출력 예

입출력 예 설명

입출력 예 #1
종이의 오른쪽 절반을 왼쪽으로 한번 접었다 펴면 아래 그림과 같이 굴곡이 생깁니다.

따라서 [0]을 return 하면 됩니다.

입출력 예 #2
문제의 예시와 같습니다.

입출력 예 #3
종이를 절반씩 세 번 접은 후 다시 펼치면 아래 그림과 같이 굴곡이 생깁니다.

따라서 [0,0,1,0,0,1,1]을 return 하면 됩니다.

나의 풀이

def solution(n):
    d=[[] for i in range(21)]
    d[1]=[0]

    for i in range(2,n+1):
        a=[]
        c=[0,1]*(2**(i-1) // 2)
        for j in range(len(c)-1):
            a.append(c[j])
            a.append(d[i-1][j])
        a.append(c[-1])
        d[i]=a
    return d[n]

종이를 접을때

n=1인 경우          [0]
n=2인 경우    [0 ,   0,    1]
n=3인 경우 [0, 0, 1, 0, 0, 1, 1]

n번 접는 경우에서 n+1번 접는 경우를 비교하면 2**n번 배열의 길이가 길어지는 것을 알 수 있습니다.
또한 n번 접는 경우의 배열에서 각 자리에 0,1을 번갈아가며 추가해 n+1배열을 만드는 것을 알 수 있습니다.

이를 통해 종이 접는 횟수가 n일때 배열을 만들었습니다.

다른 사람의 풀

def solution(n):
    fold = 0
    arr = [fold]

    for i in range(n - 1):
        arr = arr + [fold] + [bit ^ 1 for bit in arr[::-1]]

    return arr

n번 접은 배열에서 n+1번 접은 배열을 구하는 규칙은 기존 n번째 배열에 0을 추가하고 n번째 배열을 뒤집어 1인 경우 0으로, 0인 경우 1로 바꿉니다.
xor 연산자(^)를 사용하여 bit^1을 하였습니다. (bit가 1이면 bit^1은 0, bit가 0이면 bit^0은 1)

xor 연산자는 둘 중 하나만 1일 때 1입니다.

프로그래머스 '종이접기' : https://programmers.co.kr/learn/courses/30/lessons/62049

문제 설명

1부터 n까지 번호가 붙어있는 n명의 사람이 영어 끝말잇기를 하고 있습니다. 영어 끝말잇기는 다음과 같은 규칙으로 진행됩니다.

1. 1번부터 번호 순서대로 한 사람씩 차례대로 단어를 말합니다.
2. 마지막 사람이 단어를 말한 다음에는 다시 1번부터 시작합니다.
3. 앞사람이 말한 단어의 마지막 문자로 시작하는 단어를 말해야 합니다.
4. 이전에 등장했던 단어는 사용할 수 없습니다.
5. 한 글자인 단어는 인정되지 않습니다.

다음은 3명이 끝말잇기를 하는 상황을 나타냅니다.

tank → kick → know → wheel → land → dream → mother → robot → tank

위 끝말잇기는 다음과 같이 진행됩니다.

• 1번 사람이 자신의 첫 번째 차례에 tank를 말합니다.
• 2번 사람이 자신의 첫 번째 차례에 kick을 말합니다.
• 3번 사람이 자신의 첫 번째 차례에 know를 말합니다.
• 1번 사람이 자신의 두 번째 차례에 wheel을 말합니다.
• (계속 진행)

끝말잇기를 계속 진행해 나가다 보면, 3번 사람이 자신의 세 번째 차례에 말한 tank 라는 단어는 이전에 등장했던 단어이므로 탈락하게 됩니다.

사람의 수 n과 사람들이 순서대로 말한 단어 words 가 매개변수로 주어질 때, 가장 먼저 탈락하는 사람의 번호와 그 사람이 자신의 몇 번째 차례에 탈락하는지를 구해서 return 하도록 solution 함수를 완성해주세요.

제한조건

• 끝말잇기에 참여하는 사람의 수 n은 2 이상 10 이하의 자연수입니다.
• words는 끝말잇기에 사용한 단어들이 순서대로 들어있는 배열이며, 길이는 n 이상 100 이하입니다.
• 단어의 길이는 2 이상 50 이하입니다.
• 모든 단어는 알파벳 소문자로만 이루어져 있습니다.
• 끝말잇기에 사용되는 단어의 뜻(의미)은 신경 쓰지 않으셔도 됩니다.
• 정답은 [ 번호, 차례 ] 형태로 return 해주세요.
• 만약 주어진 단어들로 탈락자가 생기지 않는다면, [0, 0]을 return 해주세요.

입출력 예

입출력 예 설명

입출력 예 #1
3명의 사람이 끝말잇기에 참여하고 있습니다.

• 1번 사람 : tank, wheel, mother
• 2번 사람 : kick, land, robot
• 3번 사람 : know, dream, tank

와 같은 순서로 말을 하게 되며, 3번 사람이 자신의 세 번째 차례에 말한 tank라는 단어가 1번 사람이 자신의 첫 번째 차례에 말한 tank와 같으므로 3번 사람이 자신의 세 번째 차례로 말을 할 때 처음 탈락자가 나오게 됩니다.

입출력 예 #2
5명의 사람이 끝말잇기에 참여하고 있습니다.

• 1번 사람 : hello, recognize, gather
• 2번 사람 : observe, encourage, refer
• 3번 사람 : effect, ensure, reference
• 4번 사람 : take, establish, estimate
• 5번 사람 : either, hang, executive

와 같은 순서로 말을 하게 되며, 이 경우는 주어진 단어로만으로는 탈락자가 발생하지 않습니다. 따라서 [0, 0]을 return하면 됩니다.

입출력 예 #3
2명의 사람이 끝말잇기에 참여하고 있습니다.

• 1번 사람 : hello, even, now, draw
• 2번 사람 : one, never, world

와 같은 순서로 말을 하게 되며, 1번 사람이 자신의 세 번째 차례에 'r'로 시작하는 단어 대신, n으로 시작하는 now를 말했기 때문에 이때 처음 탈락자가 나오게 됩니다.

나의 풀이

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

1. 끝말잇기 단어들을 검사합니다.
1-1. 첫번째 if문 : 앞사람이 말한 단어의 마지막 단어로 뒷사람의 단어가 시작하는지 확인

1-2. 두번째 if문 : 이전에 등장했던 단어를 사용했는지 확인

2. 탈락자가 생기면 먼저 탈락하는 사람의 번호와 그 사람이 자신의 몇 번째 차례에 탈락하는지를 구해 리턴하고 탈락자가 생기지 않으면 [0,0]을 리턴합니다.

프로그래머스 '영어 끝말잇기' : https://programmers.co.kr/learn/courses/30/lessons/12981

문제 설명

OO 연구소는 한 번에 K 칸을 앞으로 점프하거나, (현재까지 온 거리) x 2 에 해당하는 위치로 순간이동을 할 수 있는 특수한 기능을 가진 아이언 슈트를 개발하여 판매하고 있습니다. 이 아이언 슈트는 건전지로 작동되는데, 순간이동을 하면 건전지 사용량이 줄지 않지만, 앞으로 K 칸을 점프하면 K 만큼의 건전지 사용량이 듭니다. 그러므로 아이언 슈트를 착용하고 이동할 때는 순간 이동을 하는 것이 더 효율적입니다. 아이언 슈트 구매자는 아이언 슈트를 착용하고 거리가 N 만큼 떨어져 있는 장소로 가려고 합니다. 단, 건전지 사용량을 줄이기 위해 점프로 이동하는 것은 최소로 하려고 합니다. 아이언 슈트 구매자가 이동하려는 거리 N이 주어졌을 때, 사용해야 하는 건전지 사용량의 최솟값을 return하는 solution 함수를 만들어 주세요.

예를 들어 거리가 5만큼 떨어져 있는 장소로 가려고 합니다.
아이언 슈트를 입고 거리가 5만큼 떨어져 있는 장소로 갈 수 있는 경우의 수는 여러 가지입니다.

• 처음 위치 0 에서 5 칸을 앞으로 점프하면 바로 도착하지만, 건전지 사용량이 5 만큼 듭니다.
• 처음 위치 0 에서 2 칸을 앞으로 점프한 다음 순간이동 하면 (현재까지 온 거리 : 2) x 2에 해당하는 위치로 이동할 수 있으므로 위치 4로 이동합니다. 이때 1 칸을 앞으로 점프하면 도착하므로 건전지 사용량이 3 만큼 듭니다.
• 처음 위치 0 에서 1 칸을 앞으로 점프한 다음 순간이동 하면 (현재까지 온 거리 : 1) x 2에 해당하는 위치로 이동할 수 있으므로 위치 2로 이동됩니다. 이때 다시 순간이동 하면 (현재까지 온 거리 : 2) x 2 만큼 이동할 수 있으므로 위치 4로 이동합니다. 이때 1 칸을 앞으로 점프하면 도착하므로 건전지 사용량이 2 만큼 듭니다.

위의 3가지 경우 거리가 5만큼 떨어져 있는 장소로 가기 위해서 3번째 경우가 건전지 사용량이 가장 적으므로 답은 2가 됩니다.

제한조건

• 숫자 N: 1 이상 10억 이하의 자연수
• 숫자 K: 1 이상의 자연수

입출력 예

입출력 예 설명

입출력 예 #1
위의 예시와 같습니다.

입출력 예 #2
처음 위치 0 에서 1 칸을 앞으로 점프한 다음 순간이동 하면 (현재까지 온 거리 : 1) x 2에 해당하는 위치로 이동할 수 있으므로 위치 2로 이동합니다. 이때 1 칸을 앞으로 점프하면 위치3으로 이동합니다. 이때 다시 순간이동 하면 (현재까지 온 거리 : 3) x 2 이동할 수 있으므로 위치 6에 도착합니다. 이 경우가 건전지 사용량이 가장 적으므로 2를 반환해주면 됩니다.

입출력 예 #3
위와 같은 방식으로 합니다.

나의 풀이

def solution(n):
    c = 0
    while n:
        a,b=divmod(n,2)
        n=a 
        if b == 1:
            c += 1
    return c

1. bfs는 n이 너무 크기 때문에 시간초과가 나서 뒤에서부터 추적하는 방법으로 문제를 풀었습니다.
2. n을 2로 나누고 나머지가 1인 경우 1칸을 점프한다고 생각해 c에 1을 더했습니다.

3. n을 줄여주는 방식으로 반복문을 실행하고 n이 0이 되면 c를 리턴합니다.

다른 사람의 풀이

def solution(n):
    return bin(n).count('1')

n을 이진수로 바꿨을 때의 1의 개수를 리턴합니다.

프로그래머스 '점프와 순간 이동' : https://programmers.co.kr/learn/courses/30/lessons/12980

문제 설명

주어진 숫자 중 3개의 수를 더했을 때 소수가 되는 경우의 개수를 구하려고 합니다. 숫자들이 들어있는 배열 nums가 매개변수로 주어질 때, nums에 있는 숫자들 중 서로 다른 3개를 골라 더했을 때 소수가 되는 경우의 개수를 return 하도록 solution 함수를 완성해주세요.

제한조건

• nums에 들어있는 숫자의 개수는 3개 이상 50개 이하입니다.
• nums의 각 원소는 1 이상 1,000 이하의 자연수이며, 중복된 숫자가 들어있지 않습니다.

입출력 예

입출력 예 설명

입출력 예 #1
[1,2,4]를 이용해서 7을 만들 수 있습니다.

입출력 예 #2
[1,2,4]를 이용해서 7을 만들 수 있습니다.
[1,4,6]을 이용해서 11을 만들 수 있습니다.
[2,4,7]을 이용해서 13을 만들 수 있습니다.
[4,6,7]을 이용해서 17을 만들 수 있습니다.

나의 풀이

from itertools import combinations
def solution(nums):
    c=0
    for i in combinations(nums,3):
        s=sum(i)
        r=0
        for j in range(2,s):
            if s % j == 0:
                r=1
                break
        if r == 0:
            c += 1
    return c

1. 리스트 nums에 대한 조합을 구해 합을 계산합니다.
2. 2부터 합-1까지 중에 약수가 있는지 확인합니다.
3. 약수가 없다면 소수이기 때문에 c에 1을 더합니다.
4. 모든 조합에 대한 경우를 확인하고 c를 리턴합니다.

다른 사람의 풀이

def solution(nums):
    from itertools import combinations as cb
    answer = 0
    for a in cb(nums, 3):
        cand = sum(a)
        for j in range(2, cand):
            if cand%j==0:
                break
        else:
            answer += 1
    return answer

풀이는 비슷하나 for-else를 사용했습니다.

else를 for과 같은 줄에 사용하면 for문이 중간에 break로 끊기지 않고 끝까지 끝나면 else문을 실행합니다.

프로그래머스 '소수 만들기' : https://programmers.co.kr/learn/courses/30/lessons/12977

문제 설명

가로 길이가 Wcm, 세로 길이가 Hcm인 직사각형 종이가 있습니다. 종이에는 가로, 세로 방향과 평행하게 격자 형태로 선이 그어져 있으며, 모든 격자칸은 1cm x 1cm 크기입니다. 이 종이를 격자 선을 따라 1cm × 1cm의 정사각형으로 잘라 사용할 예정이었는데, 누군가가 이 종이를 대각선 꼭지점 2개를 잇는 방향으로 잘라 놓았습니다. 그러므로 현재 직사각형 종이는 크기가 같은 직각삼각형 2개로 나누어진 상태입니다. 새로운 종이를 구할 수 없는 상태이기 때문에, 이 종이에서 원래 종이의 가로, 세로 방향과 평행하게 1cm × 1cm로 잘라 사용할 수 있는 만큼만 사용하기로 하였습니다.
가로의 길이 W와 세로의 길이 H가 주어질 때, 사용할 수 있는 정사각형의 개수를 구하는 solution 함수를 완성해 주세요.

제한조건

• W, H : 1억 이하의 자연수
  
  

입출력 예

입출력 예 설명

입출력 예 #1
가로가 8, 세로가 12인 직사각형을 대각선 방향으로 자르면 총 16개 정사각형을 사용할 수 없게 됩니다. 원래 직사각형에서는 96개의 정사각형을 만들 수 있었으므로, 96 - 16 = 80 을 반환합니다.

나의 풀이

import math

def solution(w,h):
    if w > h:
        w, h = h, w
    
    return w*h - (h+w-math.gcd(w,h))

다른 사람의 풀이

def gcd(a,b): return b if (a==0) else gcd(b%a,a)    
def solution(w,h): return w*h-w-h+gcd(w,h)

import math 대신 직접 최대공약수 알고리즘을 만들었습니다.

프로그래머스 '멀쩡한 사각형' : https://programmers.co.kr/learn/courses/30/lessons/62048

문제 설명

선행 스킬이란 어떤 스킬을 배우기 전에 먼저 배워야 하는 스킬을 뜻합니다.

예를 들어 선행 스킬 순서가 스파크 → 라이트닝 볼트 → 썬더일때, 썬더를 배우려면 먼저 라이트닝 볼트를 배워야 하고, 라이트닝 볼트를 배우려면 먼저 스파크를 배워야 합니다.

위 순서에 없는 다른 스킬(힐링 등)은 순서에 상관없이 배울 수 있습니다. 따라서 스파크 → 힐링 → 라이트닝 볼트 → 썬더와 같은 스킬트리는 가능하지만, 썬더 → 스파크나 라이트닝 볼트 → 스파크 → 힐링 → 썬더와 같은 스킬트리는 불가능합니다.

선행 스킬 순서 skill과 유저들이 만든 스킬트리1를 담은 배열 skill_trees가 매개변수로 주어질 때, 가능한 스킬트리 개수를 return 하는 solution 함수를 작성해주세요.

제한조건

• 스킬은 알파벳 대문자로 표기하며, 모든 문자열은 알파벳 대문자로만 이루어져 있습니다.
• 스킬 순서와 스킬트리는 문자열로 표기합니다.
  • 예를 들어, C → B → D 라면 CBD로 표기합니다
• 선행 스킬 순서 skill의 길이는 1 이상 26 이하이며, 스킬은 중복해 주어지지 않습니다.
• skill_trees는 길이 1 이상 20 이하인 배열입니다.
• skill_trees의 원소는 스킬을 나타내는 문자열입니다.
  • skill_trees의 원소는 길이가 2 이상 26 이하인 문자열이며, 스킬이 중복해 주어지지 않습니다.

입출력 예

입출력 예 설명

• BACDE: B 스킬을 배우기 전에 C 스킬을 먼저 배워야 합니다. 불가능한 스킬트립니다.
• CBADF: 가능한 스킬트리입니다.
• AECB: 가능한 스킬트리입니다.
• BDA: B 스킬을 배우기 전에 C 스킬을 먼저 배워야 합니다. 불가능한 스킬트리입니다.

나의 풀이

def solution(skill, skill_trees):
    answer = 0
    skill=list(skill)

    for i in skill_trees:
        a = [-1] * len(skill)
        tree=list(i)
        
        for j, v in enumerate(skill):
            if v in tree:
                a[j]=tree.index(v)

        if sum(a) == (-1)*len(a): # 아무것도 속하지 않는 경우
            answer += 1
            continue    
        if a[0] == -1:
            continue
                            
        while True:
            if a[-1] == -1:
                a.pop()
            else:
                break
            
        b=sorted(a)
        a=list(filter((-1).__ne__ ,a))
        if a == b:
            answer += 1
        
    return answer

1. 스킬을 리스트로 만들고 스킬트리의 값들을 하나씩 리스트로 만듭니다.

2. 스킬에 있는 값이 스킬트리에 있는지 확인하고 있다면 스킬트리에서의 위치를 리스트 a에 넣습니다.

3. 스킬트리에 스킬의 값이 하나도 없다면 스킬트리가 가능한 경우이기 때문에 가능한 스킬트리의 개수 answer를 1 올려줍니다.

4. 스킬트리에 첫번째 스킬이 있어야 스킬트리가 될 가능성이 있기 때문에 첫번째 스킬트리가 있는지 확인합니다.

5. 리스트 a의 마지막 요소가 -1이면 -1을 전부 지워줍니다. 해당 위치의 스킬이 없는것으로 생각합니다.

6. 그 후 정렬한 리스트와 리스트 a에서 -1을 제거한 것을 비교합니다. (-1을 제거한 이유는 중간에 -1이 있다면 해당 스킬을 배우지 않은 것으로 간주하기 때문입니다.)

7. 두 리스트가 같으면 스킬트리의 개수 answer에 1 올려줍니다.

8. 위의 과정들을 반복한 뒤 answer를 리턴합니다.

다른 사람의 풀이

def solution(skill, skill_trees):
    answer = 0

    for skills in skill_trees:
        skill_list = list(skill)

        for s in skills:
            if s in skill:
                if s != skill_list.pop(0):
                    break
        else:
            answer += 1

    return answer

프로그래머스 '스킬트리' : programmers.co.kr/learn/courses/30/lessons/49993