[SWEA]4836~4843. [파이썬 S/W 문제해결 기본] 2일차 LIST2 색칠하기 ~ 특별한 정렬

※ 모든 문제의 저작권은 SW Expert 아카데미에 있습니다. 학습 기록용으로 입니다. 문제시 삭제하겠습니다.

 

4836. [파이썬 S/W 문제해결 기본] 2일차 - 색칠하기

 

그림과 같이 인덱스가 있는 10x10 격자에 빨간색과 파란색을 칠하려고 한다.
N개의 영역에 대해 왼쪽 위와 오른쪽 아래 모서리 인덱스, 칠할 색상이 주어질 때, 칠이 끝난 후 색이 겹쳐 보라색이 된 칸 수를 구하는 프로그램을 만드시오.
주어진 정보에서 같은 색인 영역은 겹치지 않는다.

예를 들어 2개의 색칠 영역을 갖는 위 그림에 대한 색칠 정보이다.
2
2 2 4 4 1  ( [2,2] 부터 [4,4] 까지 color 1 (빨강) 으로 칠한다 )
3 3 6 6 2 ( [3,3] 부터 [6,6] 까지 color 2 (파랑) 으로 칠한다 )

 

입력_

첫 줄에 테스트 케이스 개수 T가 주어진다.   ( 1 ≤ T ≤ 50 )
다음 줄부터 테스트케이스의 첫 줄에 칠할 영역의 개수 N이 주어진다. ( 2 ≤ N ≤ 30 )
다음 줄에 왼쪽 위 모서리 인덱스 r1, c1, 오른쪽 아래 모서리 r2, c2와 색상 정보 color가 주어진다. ( 0 ≤ r1, c1, r2, c2 ≤ 9 )
color = 1 (빨강), color = 2 (파랑)
3
2
2 2 4 4 1
3 3 6 6 2
3
1 2 3 3 1
3 6 6 8 1
2 3 5 6 2
3
1 4 8 5 1
1 8 3 9 1
3 2 5 8 2

 

출력_
각 줄마다 "#T" (T는 테스트 케이스 번호)를 출력한 뒤, 답을 출력한다.
#1 4
#2 5
#3 7

 

[문제 풀이]

# 테스트 케이스 입력
for t in range(int(input())):
    # 색에 따른 리스트와 보라색을 카운트해 저장할 변수 초기화
    red_lst = []
    blu_lst = []
    count = 0
    
    # 영역 개수 입력
    for _ in range(int(input())):
        # 각 좌표와 색 정보 입력
        r1, c1, r2, c2, color = map(int, input().split())

        # 색에 따른 (x,y)좌표 이중 리스트 생성
        for x in range(r1, r2+1):
            for y in range(c1, c2+1):
                if color == 1:
                    red_lst.append([x,y])

                if color == 2:
                    blu_lst.append([x,y])
                
    # 각 리스트를 비교해 공통인 것들을 카운트
    for common in red_lst:
        count += blu_lst.count(common)

    # 형식에 맞게 출력
    print(f'#{t+1} {count}')

---

4837. [파이썬 S/W 문제해결 기본] 2일차 - 부분집합의 합

 

1부터 12까지의 숫자를 원소로 가진 집합 A가 있다. 집합 A의 부분 집합 중 N개의 원소를 갖고 있고, 원소의 합이 K인 부분집합의 개수를 출력하는 프로그램을 작성하시오.
해당하는 부분집합이 없는 경우 0을 출력한다. 모든 부분 집합을 만들어 답을 찾아도 된다.
예를 들어 N = 3, K = 6 경우, 부분집합은 { 1, 2, 3 } 경우 1가지가 존재한다.

입력_
첫 줄에 테스트 케이스 개수 T가 주어진다.  ( 1 ≤ T ≤ 50 )
테스트 케이스 별로 부분집합 원소의 수 N과 부분 집합의 합 K가 여백을 두고 주어진다. ( 1 ≤ N ≤ 12, 1 ≤ K ≤ 100 )
3
3 6
5 15
5 10

출력_
각 줄마다 "#T" (T는 테스트 케이스 번호)를 출력한 뒤, 답을 출력한다.
#1 1
#2 1
#3 0

[문제 풀이]

from itertools import combinations as com

# a리스트 및 리스트 길이 저장할 변수인 l 생성
a = [i for i in range(1,13)]
l = len(a)

#부분집합 구하는 4가지 방법
# 방법1: 비트연산자를 통한 모든 부분집합 구하기(컨프리헨션)
'''
    a리스트의 길이만큼 좌로 시프트 연산해 2^12만큼 반복한다.
    다음 리스트의 길이만큼 또 반복, i와 j만큼 좌로 시프트한 
    연산의 교집합(공통인것)인 a[j]를 lst1에 저장
''' 
lst1 = [[a[j] for j in range(l) if i&(1<<j)] for i in range(1<<l)]

# 방법2: 반복문을 통한 모든 부분집합 구하기
lst2 = [[]]
for i in a:
    for j in range(len(lst2)):
        lst2.append(lst2[j]+[i])

# 방법3: 비트연산자를 통한 모든 부분집합 구하기
lst3 = []
for i in range(1<<l):
    lst = []
    for j in range(l):
        if i&(1<<j):
            lst.append(a[j])
    lst3.append(lst)

# 방법4: 라이브러리를 통한 모든 부분집합 구하기
lst4 = []
for i in range(l):
    lst4 = lst4 + list(com(a,i))

# 테스트 케이스 입력
for t in range(int(input())):
    # 경우의 수를 저장하기 위한 변수 초기화
    count = 0

    # 원소의 개수인 n, 원소의 합인 k 입력
    n, k = map(int, input().split())

    # 각 부분집합 리스트를 사용해 원소의 개수와 합과 비교
    for sub in lst4:
        if len(sub) == n and sum(sub) == k:
            count += 1

    # 형식에 맞게 출력
    print(f'#{t+1} {count}')

---

4839. [파이썬 S/W 문제해결 기본] 2일차 - 이진탐색

 

코딩반 학생들에게 이진 탐색을 설명하던 선생님은 이진탐색을 연습할 수 있는 게임을 시켜 보기로 했다.

짝을 이룬 A, B 두 사람에게 교과서에서 각자 찾을 쪽 번호를 알려주면, 이진 탐색만으로 지정된 페이지를 먼저 펼치는 사람이 이기는 게임이다.

예를 들어 책이 총 400쪽이면, 검색 구간의 왼쪽 l=1, 오른쪽 r=400이 되고, 중간 페이지 c= int((l+r)/2)로 계산한다.

찾는 쪽 번호가 c와 같아지면 탐색을 끝낸다.

A는 300, B는 50 쪽을 찾아야 하는 경우, 다음처럼 중간 페이지를 기준으로 왼쪽 또는 오른 쪽 영역의 중간 페이지를 다시 찾아가면 된다.

	A	B
첫 번째 탐색	l=1, r=400, c=200	l=1, r=400, c=200
두 번째 탐색	l=200, r=400, c=300	l=1, r=200, c=100
세 번째 탐색		l=1, r=100, c=50

책의 전체 쪽수와 두 사람이 찾을 쪽 번호가 주어졌을 때, 이진 탐색 게임에서 이긴 사람이 누구인지 알아내 출력하시오. 비긴 경우는 0을 출력한다.

입력_
첫 줄에 테스트 케이스 개수 T가 주어진다.  1<=T<=50
테스트 케이스 별로 책의 전체 쪽 수 P, A, B가 찾을 쪽 번호 Pa, Pb가 차례로 주어진다. 1<= P, Pa, Pb <=1000
3
400 300 350
1000 299 578
1000 222 888

출력_
각 줄마다 "#T" (T는 테스트 케이스 번호)를 출력한 뒤, A, B, 0 중 하나를 출력한다.
#1 A
#2 0
#3 A

[문제 풀이]

# 재귀함수를 통한 이진탐색
def bi_search(start, end, k, cnt):
    # 시작이 끝보다 크면 종료
    if end < start:
        return 
    else:
        # 중간은 끝과 처음 합의 2로나눈 몫
        mid = (end + start) // 2
        # 원하는 결과가 나왔다면 카운트 리턴
        if k == mid:
            return cnt
        # 같지않다면 반복하며 k가 중간보다 작으면 마지막값을 중간으로 바꿔주고 카운트+1
        elif k < mid:
            return bi_search(start, mid, k, cnt+1)
        # k가 중간보다 크면 처음값을 중간으로 바꿔주고 카운트+1
        elif mid < k:
            return bi_search(mid, end, k, cnt+1)

# 반복문을 통한 이진탐색
def bi_search2(start, end, k, cnt):
    while start <= end:
        mid = (end + start) // 2
        if k == mid:
            return cnt
        elif k < mid:
            end = mid
            cnt += 1
        else: 
            start = mid
            cnt += 1


# 테스트 케이스 입력
for t in range(int(input())):
    # 결과를 표현하기 위한 변수로 비겼을 때를 가정해 0으로 초기화
    result = 0
    # 각 수들 입력
    p, a, b = map(int, input().split())

    # 재귀함수를 통한 이진탐색함수
    # 함수에 입력받은 수를 차례로 넣고 b의 카운트가 더 크면 결과는 a가 더 빠른 것이므로 A출력
    if bi_search(1, p, a, 0) < bi_search(1, p, b, 0):
        result = 'A'
    elif bi_search(1, p, a, 0) > bi_search(1, p, b, 0):
        result = 'B'

    # 반복문을 통한 이진탐색함수
    # if bi_search2(1, p, a, 0) < bi_search2(1, p, b, 0):
    #     result = 'A'
    # elif bi_search2(1, p, a, 0) > bi_search2(1, p, b, 0):
    #     result = 'B'

    # 형식에 맞게 출력
    print(f'#{t+1} {result}')

---

4843. [파이썬 S/W 문제해결 기본] 2일차 - 특별한 정렬

 

보통의 정렬은 오름차순이나 내림차순으로 이루어지지만, 이번에는 특별한 정렬을 하려고 한다.
N개의 정수가 주어지면 가장 큰 수, 가장 작은 수, 2번째 큰 수, 2번째 작은 수 식으로 큰 수와 작은 수를 번갈아 정렬하는 방법이다.
예를 들어 1부터 10까지 10개의 숫자가 주어지면 다음과 같이 정렬한다.
10 1 9 2 8 3 7 4 6 5
주어진 숫자에 대해 특별한 정렬을 한 결과를 10개까지 출력하시오.

입력_
첫 줄에 테스트 케이스 개수 T가 주어진다.  1<=T<=50
다음 줄에 정수의 개수 N이 주어지고 다음 줄에 N개의 정수 ai가 주어진다. 10<=N<=100, 1<=ai<=100
3
10
1 2 3 4 5 6 7 8 9 10
10
67 39 16 49 60 28 8 85 89 11
20
3 69 21 46 43 60 62 97 64 30 17 88 18 98 71 75 59 36 9 26 

출력_
각 줄마다 "#T" (T는 테스트 케이스 번호)를 출력한 뒤, 특별히 정렬된 숫자를 10개까지 출력한다.
#1 10 1 9 2 8 3 7 4 6 5
#2 89 8 85 11 67 16 60 28 49 39
#3 98 3 97 9 88 17 75 18 71 21

[문제 풀이]

# 테스트 케이스 입력
for t in range(int(input())):
    # 각 수들 입력
    n = int(input())
    a_lst = list(map(int, input().split()))

    '''방법1
    # 정렬
    a_lst = sorted(a_lst)

    # 반으로 나눠 a리스트의 큰수들은 b리스트에 저장
    b_lst = []
    for i in range(len(a_lst)//2):
        b_lst.append(a_lst.pop())

    # 결과 리스트에 각 리스트의 수를 순서대로 저장
    result_lst =[]
    for i in range(5): # 10개만 출력해야하므로 5로 고정
        result_lst.append(b_lst[i])
        result_lst.append(a_lst[i])

    # 형식에 맞게 출력
    print(f'#{t+1}', *result_lst)
    '''
    '''방법2 위와 비슷'''
    lst = []
    # 가장 큰 수와 작은 수를 리스트에 저장후 삭제
    while 0 < len(a_lst):
        lst.append(max(a_lst))
        lst.append(min(a_lst))
        a_lst.remove(max(a_lst))
        a_lst.remove(min(a_lst))

    # 형식에 맞게 출력
    print(f'#{t+1}', *lst[0:10])