심화 과정 10 일차

1. 자료구조 및 알고리즘 10일차 수강하기

 

 -  구현 & 시뮬레이션

 

2. 새롭게 알게된 지식

 

과제 1 : 미세먼지 https://www.acmicpc.net/problem/17144

 

- 접근 : 

 

 확장 가능한 미세먼지 큐에 등록

 미세먼지 확장 기능 구현

 공기 순환 기능을 구현

 

 - 코드 구현 : 

 

import sys
from collections import deque 

class Solution:
    def __init__(self):
        self.input = sys.stdin.readline
        self.output = sys.stdout.write
        self.spread_way = ((-1,0), (0,1), (1,0), (0,-1))
    
    def findSpreadable(self, room_air: list):
        """ 확산 가능한 먼지덩어리를 큐로 반환
        Queue:{ ( x위치, y 위치, 먼지량 )}
        """
        queue = deque()
        for x, row in enumerate(room_air):
            for y, val in enumerate(row):
                if val // 5 > 0:
                    queue.append((x, y, val))
        return queue

    def spreadDust(self, room_air: list, queue: deque):
        """ 먼지 확산
        """
        
        while queue:
            x, y, val = queue.popleft()
                
            for way in self.spread_way:
                next_x = x + way[0]
                next_y = y + way[1]

                if next_x < 0 or next_y < 0 or next_x >= len(room_air) or next_y >= len(room_air[0]):
                    continue

                if room_air[next_x][next_y] == -1:
                    continue
                
                spread_amonut = val // 5
                room_air[next_x][next_y] += spread_amonut
                room_air[x][y] -= spread_amonut

        return room_air
    
    def rotateCounterClockwise(self, data_list, idx):

        for i in range(idx-1, 0, -1):
            data_list[i][0] = data_list[i-1][0]

        data_list[0] = data_list[0][1:] + [0]

        for i in range(1, idx+1):
            data_list[i-1][-1] = data_list[i][-1]

        data_list[idx] = [-1, 0] + data_list[idx][1:-1]

    def rotateClockwise(self, data_list, idx):

        for i in range(idx+1, len(data_list)-1, 1):
            data_list[i][0] = data_list[i+1][0]

        data_list[len(data_list)-1] = data_list[len(data_list)-1][1:] +[0]

        for i in range(len(data_list)-1, idx, -1):
            data_list[i][-1] = data_list[i-1][-1]

        data_list[idx] = [-1, 0] + data_list[idx][1:-1]
    
    def airPurification(self, room_air: list, dev_location : list):
        self.rotateCounterClockwise(room_air, dev_location[0])
        self.rotateClockwise(room_air, dev_location[1])

    def run(self):
        R, C, T = map(int, self.input().split())
        room_air  = []
        device_location= []

        for i in range(R):
            temp = []
            for val in self.input().rstrip().split():
                n = int(val)
                temp.append(n)

                if n == -1:
                    device_location.append(i)

            room_air.append(temp)

        for i in range(T):
            self.airPurification(self.spreadDust(room_air, self.findSpreadable(room_air)), device_location)
        ans = 0
        
        for i in room_air:
            ans += sum(i)

        ans += 2
        self.output(str(ans) + '\n')

s = Solution()
s.run()

 

 

과제 2 : 스위치켜고끄기 https://www.acmicpc.net/problem/1244

1244번: 스위치 켜고 끄기

 

 

 - 접근 : 

 

남자의 경우 배수 만큼 스위치 전환

 

여자의 경우 투포인터로 좌우가 대칭인 지점까지 스위치 전환

 

 -  코드 구현 : 

 

import sys

class Solution:
    def __init__(self):
        self.input = sys.stdin.readline
        self.output = sys.stdout.write

    def doMale(self, num, switches):
        for i in range(num-1, len(switches), num):
            switches[i] = 1 - switches[i]

    def doFemale(self, num, switches):

        start, end = num - 2, num
        switches[num-1] = 1- switches[num-1]

        while start >= 0 and end < len(switches) and switches[start] == switches[end]:

            switches[start] = 1 - switches[start]
            switches[end] = 1 - switches[end]
            start -= 1
            end += 1

    def run(self):
        switch_num = int(self.input())
        switches = [int(i) for i in self.input().split()]
        student_num = int(self.input())
        
        for _ in range(student_num):
            gender, num = map(int, self.input().split())

            if gender == 1:
                self.doMale(num, switches)
                continue

            self.doFemale(num, switches)

        for idx, val in enumerate(switches):
            if idx != 0 and idx % 20 == 0:
                self.output('\n')
            self.output(str(val) + ' ')

        self.output('\n')

s = Solution()
s.run()