미정

https://school.programmers.co.kr/learn/courses/30/lessons/87390

풀이 

이런 문제는, 문제에서 규칙을 찾을 수 있는지 확인해야 한다.
일단 대각선의 값이 눈에 띈다. 대각선의 원소들은 1, 2, 3, 4, ...의 순서로 배열되어 있다.
이 대각선의 값을 기준으로, 왼쪽 직선과 위쪽 직선은 같은 값을 가지고 있다.
위와 아래는 인덱스 값이 약 n만큼 차이가 나고, 대각선의 한 원소로부터 왼쪽의 원소들은 인덱스 값이 1씩 줄어든다.
여기서 i // n과 i % n를 적절히 활용하면 풀 수 있을 것이라는 것을 직감적으로 느낄 수 있다.
정확한 규칙을 찾기 위해 몇 가지의 인덱스 값들을 예시를 들어 비교해보면,

예시 1번을 보면  n=3일때 배열을 열이 1인 행렬로 그려보면

0 (0,0) 1 (0,1) 2 (0,2) 3 (1,0) 4 (1,1) 5 (1,2) 6 (2,0) 7 (2,1) 8 (2,2)
이런식으로 볼수 있다.
만약 내가 구하고자 하는 같이 index 8번이라면, 8 ( 8//3, 8% 3)=( 몫, 나머지)로 확인할 수 있다.

그리고 몫과 나머지중 가장 큰값에 따라서 숫자가 들어간다!

즉, index = 8, n = 4 이라면

(i // n, i % n) → (2, 0) → 3

이거에 +1을 한것이 답이 된다 !

def solution(n, left, right):
    answer = []
    for i in range(left, right+1):
        a = i//n
        b = i % n
        if a < b:
            a,b = b,a
        answer.append(a+1)
        
    return answer

문제 설명

코니는 매일 다른 옷을 조합하여 입는것을 좋아합니다.

예를 들어 코니가 가진 옷이 아래와 같고, 오늘 코니가 동그란 안경, 긴 코트, 파란색 티셔츠를 입었다면 다음날은 청바지를 추가로 입거나 동그란 안경 대신 검정 선글라스를 착용하거나 해야합니다.

종류 이름

• 코니는 각 종류별로 최대 1가지 의상만 착용할 수 있습니다. 예를 들어 위 예시의 경우 동그란 안경과 검정 선글라스를 동시에 착용할 수는 없습니다.
• 착용한 의상의 일부가 겹치더라도, 다른 의상이 겹치지 않거나, 혹은 의상을 추가로 더 착용한 경우에는 서로 다른 방법으로 옷을 착용한 것으로 계산합니다.
• 코니는 하루에 최소 한 개의 의상은 입습니다.

코니가 가진 의상들이 담긴 2차원 배열 clothes가 주어질 때 서로 다른 옷의 조합의 수를 return 하도록 solution 함수를 작성해주세요.

제한사항

• clothes의 각 행은 [의상의 이름, 의상의 종류]로 이루어져 있습니다.
• 코니가 가진 의상의 수는 1개 이상 30개 이하입니다.
• 같은 이름을 가진 의상은 존재하지 않습니다.
• clothes의 모든 원소는 문자열로 이루어져 있습니다.
• 모든 문자열의 길이는 1 이상 20 이하인 자연수이고 알파벳 소문자 또는 '_' 로만 이루어져 있습니다.

입출력 예

clothes return

입출력 예 설명

예제 #1

headgear에 해당하는 의상이 yellow_hat, green_turban이고 eyewear에 해당하는 의상이 blue_sunglasses이므로 아래와 같이 5개의 조합이 가능합니다.

1. yellow_hat 2. blue_sunglasses 3. green_turban 4. yellow_hat + blue_sunglasses 5. green_turban + blue_sunglasses

예제 #2

face에 해당하는 의상이 crow_mask, blue_sunglasses, smoky_makeup이므로 아래와 같이 3개의 조합이 가능합니다.

1. crow_mask 2. blue_sunglasses 3. smoky_makeup

문제 풀이

def solution(clothes):
    answer = 1
    dic = {}
    for i in clothes:
        if i[1] in dic:
            dic[i[1]] += 1
        else:
            dic[i[1]] = 1
    for i in dic.keys():
        answer *= dic[i] + 1
    return answer - 1

1. key, value 로 분류하면 된다. 그래서 딕셔너리를 사용했다.
2. 빈 딕셔너리 dic {} 을 설정한다.
3. [["yellow_hat", "headgear"], ["blue_sunglasses", "eyewear"], ["green_turban", "headgear"]] 이 입력값일 때

• i = ["yellow_hat", "headgear"]
• i[1] 은 headgear,
  dic[i[1]] ⇒ i[1]인 headgear를 Key로 하여 Value에 1을 넣으라는 뜻이다.
  즉, dic = {"headgear": 1}
• 위의 예시에서 총 경우의 수는 6가지이다.
  1. yellow_hat을 입고, blue_sunglasses를 입음
  2. green_turban을 입고, blue_sunglasses를 입음
  3. yellow_hat을 입고, 아무 것도 입지 않음
  4. green_turban을 입고, 아무 것도 입지 않음
  5. 아무 것도 입지 않고, blue_sunglasses를 입음
  6. 아무 것도 입지 않음 (아무 것도 입지 않는 경우)
• headgear 종류는 2개의 아이템(yellow_hat과 green_turban)이 있다.
  이 경우, headgear를 입는 경우의 수는 3가지이다.
  • yellow_hat을 입거나, green_turban을 입거나, 아무 것도 입지 않는 경우.
• eyewear 종류는 1개의 아이템(blue_sunglasses)이 있다.
  이 경우, eyewear를 입는 경우의 수는 2가지이다.
  • blue_sunglasses을 입거나, 아무 것도 입지 않는 경우.
• 이렇게 계산한다면 총 6가지의 경우의 수가 나오지만 여기에서 둘다 아무 것도 입지 않는 경우를 제외해야 한다.
• 문제의 조건에서는 적어도 하나의 의상은 입어야 하기 때문..
  따라서, 위에서 계산한 총 경우의 수 6에서 아무 것도 입지 않는 경우 1가지를 빼야 한다.
• 따라서, 최종적으로 가능한 조합의 수는 6 - 1 = 5가 된다.

문제 설명

• 어떤 자연수로 이루어진 원형 수열의 연속하는 부분 수열의 합으로 만들 수 있는 수가 몇 가지인지 알아보고자 합니다.
• 원형 수열이란 일반적인 수열에서 처음과 끝이 연결된 형태의 수열을 말합니다.
• 원형 수열은 처음과 끝이 연결되어 끊기는 부분이 없기 때문에 연속하는 부분 수열도 일반적인 수열보다 많아집니다.
• 원형 수열의 모든 원소 elements가 순서대로 주어질 때, 원형 수열의 연속 부분 수열 합으로 만들 수 있는 수의 개수를 반환해주세요.
• 제한 사항
  • 3 ≤ elements의 길이 ≤ 1000
  • 1 ≤ elements의 원소 ≤ 1000
• 입출력 예시

문제 풀이

def solution(elements):
    # 원형 수열을 처리하기 위해 elements 리스트를 두 배로 확장
    extended_elements = elements + elements
    unique_sums = set()  # 부분 수열의 합을 저장할 집합

    n = len(elements)  # 원래 수열의 길이

    # 부분 수열의 길이를 1부터 n까지 증가시키며 처리
    for length in range(1, n + 1):
        # 각 길이에 대해 시작 위치를 0부터 n-1까지 증가시키며 처리
        for start in range(n):
            # 부분 수열의 합을 계산
            part_sum = sum(extended_elements[start:start + length])
            # 집합에 합을 추가
            unique_sums.add(part_sum)

    # 중복을 제거한 부분 수열의 합의 개수를 반환
    return len(unique_sums)

문제 풀이 과정

1. 원형 수열에서 처음과 끝이 연결된 부분 수열을 쉽게 처리하기 위해 수열을 두 배로 확장한다. 
   [7,9,1,1,4,7,9,1,1,4]
2. 부분 수열의 길이를 1부터 원래 수열의 길이까지 변화시키면서 모든 가능한 시작 위치에서 부분 수열의 합을 계산한다.
3. 계산된 모든 부분 수열의 합을 집합(set)에 저장하여 중복을 제거한다.

문제

경화는 과수원에서 귤을 수확했습니다. 경화는 수확한 귤 중 'k'개를 골라 상자 하나에 담아 판매하려고 합니다. 그런데 수확한 귤의 크기가 일정하지 않아 보기에 좋지 않다고 생각한 경화는 귤을 크기별로 분류했을 때 서로 다른 종류의 수를 최소화하고 싶습니다.

예를 들어, 경화가 수확한 귤 8개의 크기가 [1, 3, 2, 5, 4, 5, 2, 3] 이라고 합시다. 경화가 귤 6개를 판매하고 싶다면, 크기가 1, 4인 귤을 제외한 여섯 개의 귤을 상자에 담으면, 귤의 크기의 종류가 2, 3, 5로 총 3가지가 되며 이때가 서로 다른 종류가 최소일 때입니다.

경화가 귤 k개를 고를 때 크기가 서로 다른 종류의 수의 최솟값을 return 하도록 solution 함수를 작성해주세요.

제한조건

• 1 ≤ k ≤ tangerine의 길이 ≤ 100,000
• 1 ≤ tangerine의 원소 ≤ 10,000,000

 입출력 예

풀이

1. 이 문제는 tangerine 배열을 보고 각각의 귤의 크기가 얼마인지를 보고난 후,  크기를 최대한 비슷하게 해야 하므로 같은 크기의 귤이 몇개인지를 카운트 해준 다음에 크기가 같은 귤이 많은 순서로 k 개의 귤을 담는 문제이다.

2. 먼저 tangerine 배열에서 각 숫자가 몇번 중복되는지를 알아낸 후, 최대한 적은 종류로 k 개를 담아 낼 수 있도록 중복되는 수를 담은 배열을 내림차순으로 정렬해서 몇 종류를 담으면 되는지 출력하면 된다.

1. Counter를 이용하여 같은 크기가 몇번 중복되었는지 확인한다.

Counter([1, 3, 2, 5, 4, 5, 2, 3])는 {1: 1, 3: 2, 2: 2, 5: 2, 4: 1}를 반환

2. most_common을 이용하여 최빈값 순서로 정렬한다.

Counter(tangerine).most_common()은 [(3, 2), (2, 2), (5, 2), (1, 1), (4, 1)] 튜플을 정렬된 리스트로 반환

3. 그 후  k보다 크거나 같을 때 몇 종류의 귤이 담겼는지를 리턴해준다.

from collections import Counter

def solution(k, tangerine):
    answer = 0

    for c in Counter(tangerine).most_common():
        k -= c[1] 

        answer += 1

        if k <= 0:
            break

    return answer

코딩테스트 연습 - 올바른 괄호 | 프로그래머스 스쿨 (programmers.co.kr)

답

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

Stack을 이용하여서 “좌측 괄호” 일 경우 Stack에 넣어두고 “우측 괄호”가 나오면 Stack에 저장되어 있는 좌측 괄호 값을 빼는 형태로 짝을 찾아가는 형태로 구성

1. 문자열을 문자 배열로 구성하여 반복문 순회
2. 순회하면서 좌측 괄호인 경우는 Stack에 넣기
3. Stack 값이 비었을 경우 false 리턴 ⇒ 짝이 맞지 않는 경우
4. 순회하면서 우측 괄호인 경우 Stack에서 빼기
5. 순회가 끝나고 Stack에 값이 존재하지 않으면 false 리턴

문제링크
https://school.programmers.co.kr/learn/courses/30/lessons/1844

문제 핵심

1. n * m 크기의 maps가 주어지고 maps에서 0은 벽을 1은 길을 나타낸다.

2. 목표지점은 maps의 우측 하단 끝 지점이며 시작지점은 (1,1) 이다.

3. 캐릭터는 상하좌우로 움직일 수 있으며, 벽으로 이동하는 것은 불가능하다.

4. 목표지점에 도달하기 위해 최소한의 움직임을 구하기

첫 번째 방법

최단거리를 구하는 문제이기에 BFS탐색법을 사용했지만 시간 초과가 발생하였다..ㅎㅎ

def solution(maps):
    w = len(maps) - 1 
    h = len(maps[0]) - 1 
    visit = [] 
    going = [[0,0,1]] 
    while going:
        now = going.pop(0) 
        x, y, count = now[0], now[1], now[2] 
        if x == w and y == h: 
            return count
        for dx, dy in [(1, 0), (-1, 0), (0, 1), (0, -1)]: 
            nx = x + dx
            ny = y + dy
            if 0 <= nx <= w and 0 <= ny <= h and [nx, ny] not in visit and maps[nx][ny] == 1:
            
                going.append([nx, ny, count + 1]) 
                visit.append([nx, ny]) 
    return -1

기본적인 BFS 문제는 풀이방법이 비슷하다.
1. BFS문제면 이동할 때 사방팔방 다 이동하고 그 값을 저장하는 변수 필요 => 큐 사용

2. 위로 이동하고 좌우 옆으로 이동했을 때 해당 좌우가 방문했는지 저장하는 변수 필요  => 좌, 우, 상, 하 이동

1. 목표지점을 계산하기 위한 maps의 세로 길이와 가로 길이를 w ,h 로 정의

2. visit라는 방문한 지점을 담을 리스트 정의

3. going은 방문해야할 지점을 담을 리스트

4. now 는 현재 지점이고 x, y, count 는 현재 x, y좌표 및 이동 거리

5. 만약 목표지점일 경우 이동 거리를 리턴

6. dx, dy 에는 (1, 0), (-1, 0), (0, 1), (0, -1) 상하좌우 이동의 값을 넣고

7. 경계 및 벽에 막히지 않고, 방문한 지점이 아닐 경우 방문할 지점에 추가하고 방문한 지점에 추가

8.  모든 경로를 탐색후에도 만족하지 않으면 -1 리턴

그래서 뭐가 문제인가.. 알아봤는데 나는 방문한 지점을 담은 리스트 visit를 리스트로 사용했고 이 경우에서 방문 여부를 확인하는 로직인 not in을 사용할 경우 시간복잡도가 크게 상승한다는 얘기.. 이를 해결하기 위해 visit를 set로 선언하여 통과하였다.

두 번째 방법

def solution(maps):
    w = len(maps) - 1
    h = len(maps[0]) - 1
    visit = set() 
    going = [[0,0,1]]
    while going:
        now = going.pop(0)
        x, y, count = now[0], now[1], now[2]
        if x == w and y == h:
            return count
        for dx, dy in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
            nx = x + dx
            ny = y + dy
            if 0 <= nx <= w and 0 <= ny <= h and (nx, ny) not in visit and maps[nx][ny] == 1:
                going.append([nx, ny, count + 1])
                visit.add((nx,ny))
    return -1

set 자료형의 경우 내부 해시테이블을 이용하여 포함여부를 확인할 때 리스트보다 빠른 속도로 확인이 가능하여 시간을 줄여 해결할 수 있었다.

세 번째 방법

뭔가 내가  쓴건 깔끔하지 않다고 해야하나.. 그래서 다른 사람 코드를 봤더니

going 리스트도 deque를 사용하여 속도를 더욱 줄이는 방법이 있고 깔끔했다.

from collections import deque
def solution(maps):
    w = len(maps) - 1
    h = len(maps[0]) - 1
    visit = set()
    going = deque([[0,0,1]]) 
    while going:
        now = going.popleft()
        x, y, count = now[0], now[1], now[2]
        if x == w and y == h:
            return count
        for dx, dy in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
            nx = x + dx
            ny = y + dy
            if 0 <= nx <= w and 0 <= ny <= h and (nx, ny) not in visited and maps[nx][ny] == 1:
                going.append([nx, ny, count + 1])
                visit.add((nx,ny))
    return -1

deque를 사용하면 기존의 pop(), append()의 시간복잡도가 O(N)에서 popleft()를 통한 시간복잡도 O(1)로 줄어들기 때문에 n이 커질 경우 더욱 빠르게 문제해결이 가능해진다.

1. 문제

2. 풀이과정

해당 문제는 단어가 1자리부터 최대 5자리까지만 존재하므로 모든 경우를 구한 뒤에 찾는 것으로 해결하였다.

모든 경우를 찾을 때는 중복순열을 활용하여 찾아주었다.

1. 중복순열을 구해주는 product 함수를 사용하기 위해 product 모듈을 불러온다. from itertools import product
2. 중복순열을 저장해 줄 리스트를 생성한다. result = list()
3. 최소 1자리 단어부터 최대 5자리 단어까지 존재하므로 각 자리 개수만큼 반복하며 for i in range(1, 6)
4. 모음 리스트에서 중복을 허용하여 해당 자리 단어를 리스트로 생성한다. li = list(product(["A", "E", "I", "O", "U"], repeat=i))
5. 중복순열을 구한 뒤 해당 순열을 하나씩 불러오며 for j in li
6. 각 순열을 하나의 단어로 만들어 결과에 한 단어로 저장한다. result.append(''.join(k for k in j))
7. 전부 구한 중복순열의 결과를 사전순으로 정렬한다. result.sort()
8. 정렬한 중복순열 리스트에서 해당 단어의 인덱스를 찾아 1을 더해준 값이 정답이다. 인덱스 값으로 찾았기 때문에 번호를 붙일 때는 1을 더해줘야 한다. answer = result.index(word) + 1

3. 소스코드

from itertools import product

def solution(word):
    answer = 0
    
    result = list()
    for i in range(1, 6):
        li = list(product(["A", "E", "I", "O", "U"], repeat=i))
        for j in li:
            result.append(''.join(k for k in j))
        
    result.sort()
    answer = result.index(word) + 1

    return answer

문제 설명

나의 풀이

from itertools import permutations

def solution(numbers):
    r = []
    for i in range(1, len(numbers)+1):
        for j in permutations(list(numbers), i):
            num=int(''.join(j))
            for k in range(2, num):
                if num % k == 0:
                    break
            else:
                if num not in r and num !=0 and num !=1:
                        r.append(num)
    return len(r)

• 일단 모든 경우의 수를 구하므로 완전 탐색을 이용해 문제를 풀어야 한다고 생각.
• 소수는 1과 나 자신으로만 이루어져 있어야 하고 1보다 커야 한다.
• 문자열 numbers를 한자리 수 부터 len(numbers)까지 순열로 만든다.
• 분리된 숫자들을 permutations()를 이용해 순열 조합을 한다.
• ["1","7"]=>("1"),("7"),("1","7"),("7","1")
• join을 이용해 각각 하나의 숫자로 만들기
• [1,7,17,71]
• 각각의 수가 소수인지( num % k == 0) 검사하고 소수이면 리스트 r에 넣는다.
• 리스트 r에 있는 개수를 출력하면 된다.

다른 사람 풀이

from itertools import permutations
def solution(numbers):
    a = set()
    for i in range(len(numbers)):
        a |= set(map(int, map("".join, permutations(list(numbers), i + 1))))
    a -= set(range(0, 2))
    for i in range(2, int(max(a) ** 0.5) + 1):
        a -= set(range(i * 2, max(a) + 1, i))
    return len(a)

• permutations를 사용하기 위해 상단에 import를 시켜준다.
• permutations의 사용법은 permutations(대상, 갯수)로 사용하면 된다.
• 대상에는 리스트, 문자열, 집합 등 iterable한 자료형이 올 수 있다.
• permutations의 결과는 튜플 형식으로 반환된다.
• 예를 들어 ('1', '3') 과 같은 형식으로 반환된는 것인데 우리는 숫자 13으로 사용하기 위해서 map 함수로 각각의 경우에 ''.join를 사용하여 "13"을 만들어준다.
• print 하면 [['1', '7'], ['71', '17']]이 출력된다.
• ''.join은 리스트의 각 요소를 ' ' 안에 들어있는 문자를 구분자로 묶는 역할을 하는데 ' ' 안이 공백이므로 하나의 문자로 연결해준다.
• 그리고 또 그렇게 만들어진 문자열 요소들을 정수로 바꿔주기 위하여 map을 한번 더 사용하여 int형으로 만들어주었다.
• print 하면 [1,7, 71, 17]이 출력된다.
• 소수인지 판별하기 위해 소수 특성상 소수의 루트값까지만 나눠보고 나눠지는 숫자가 없다면 그 수는 소수인 점을 사용했다.
• a |= set(map(int, map("".join, permutations(list(numbers), i + 1))))에서 map() 함수안에 map()을 넣어서 문자열을 한번에 int형으로 바꾼 뒤 set 함수에 담아 중복을 없앤다.
• set(range(0, 2))을 하면  {0,1}이 나온다.!!
• 에라토스테네스의 체에 의하면 2부터 max(a) ** 0.5 까지 의 배수만 확인하면 소수가 아닌 수를 전부 거를 수 있다.

이 풀이에서 새로운 단어를 알았다. 에라토스테네스..? 의 체..? 와 이게 뭔지 처음 듣는 단어라ㅋㅋㅋㅋ... 아직 한참 부족하구나 생각이 들었다... 

그럼 에타토스테네스의 체에 대해 간단하게 알아보자!

에라토스테네스의 체

• 범위의 모든 소수를 구할 때 효율적

1. 1은 제거

2. 지워지지 않은 수 중 제일 작은 2를 소수로 채택하고, 나머지 2의 배수를 모두 지운다.

3. 지워지지 않은 수 중 제일 작은 3을 소수로 채택하고, 나머지 3의 배수를 모두 지운다.

4. 지워지지 않은 수 중 제일 작은 5를 소수로 채택하고, 나머지 5의 배수를 모두 지운다.

5. (반복)