다단계 칫솔 판매 (Python)

0. 출처

• 유형 : 트리, 구현 (lv.3)
• 링크 : 다단계 칫솔 판매

1. 기록

2. 풀이

(1) 아이디어, 시간복잡도, 자료구조

1. 아이디어
>> 
>> 
>> 

2. 시간복잡도
>> 

3. 자료구조
>> 

(2) 풀이

(3) 참고 및 정리

행렬 테두리 회전하기 (Python)

0. 출처

• 유형 : 구현
• 링크 : 행렬 테두리 회전하기

1. 기록

• 22/03/27 (토)

2. 풀이

(1) 아이디어, 시간복잡도, 자료구조

1. 아이디어
>> queries에서 값을 graph에서 잘 위치시키도록 한다.
>> 왼쪽 끝은 오른쪽으로 이동 등
>> 총 4섹터로 나눌 수 있음
>> x1,y1,x2,y2 라는 변수로 이용할 것임

>> rows colums 로
>> 1, 2, 3, 4, ... 의 순서대로 garph 를 만들어줘야 함.

2. 시간복잡도

3. 자료구조
>> 이차원 배열 이용

(2-1) 시간초과 풀이

import copy

def start(rows, columns, graph1, graph2):
    for r in range(rows):
        graph1.append([a for a in range(r*columns+1, (r+1)*columns+1)])
        graph2.append([a for a in range(r*columns+1, (r+1)*columns+1)])

def solution(rows, columns, queries):
    graph1 = []
    graph2 = []
    answer = []
    start(rows, columns, graph1, graph2)
    dx = [0, 1, 0, -1]
    dy = [1, 0, -1, 0]
    while queries:
        min_value = 10000
        x1, y1, x2, y2 = queries.pop(0)
        x1 = x1 - 1
        y1 = y1 - 1
        x2 = x2 - 1
        y2 = y2 - 1
        for i in range(rows):
            for j in range(columns):
                if i == x1 and y1<=j<y2:
                    # 우로 이동
                    nx = i + dx[0]
                    ny = j + dy[0]
                    graph2[nx][ny] = graph1[i][j]
                    min_value = min(min_value ,graph1[i][j])
                elif j == y2 and x1<=i<x2:
                    # 아래로 이동
                    nx = i + dx[1]
                    ny = j + dy[1]
                    graph2[nx][ny] = graph1[i][j]
                    min_value = min(min_value ,graph1[i][j])
                elif i == x2 and y1<j<=y2:
                    # 좌로이동
                    nx = i + dx[2]
                    ny = j + dy[2]
                    graph2[nx][ny] = graph1[i][j]
                    min_value = min(min_value ,graph1[i][j])
                elif j == y1 and x1<i<=x2:
                    # 위로 이동
                    nx = i + dx[3]
                    ny = j + dy[3]
                    graph2[nx][ny] = graph1[i][j]
                    min_value = min(min_value ,graph1[i][j])
                else:
                    continue
        answer.append(min_value)
        graph1 = copy.deepcopy(graph2)          # 깊은 복사해야 내가 의도한 대로 된다.
        if queries == []:
            print(answer)
            return answer

(2-2) 다시 풀이

def solution(rows, columns, queries):
    answer = []
    table = []
    for r in range(rows):
        table.append([a for a in range(r*columns+1, (r+1)*columns+1)])

    for query in queries:
        query = [x-1 for x in query]    # 0부터 시작하는 인덱스에 맞춰 1씩 빼줌
        tmp = table[query[0]][query[1]] # 왼쪽 위 값 저장
        small = tmp

        # left
        for i in range(query[0]+1, query[2]+1):
            table[i-1][query[1]] = table[i][query[1]]
            small = min(small, table[i][query[1]])
        # bottom
        for i in range(query[1]+1, query[3]+1):
            table[query[2]][i-1] = table[query[2]][i]
            small = min(small, table[query[2]][i])
        # right
        for i in range(query[2]-1, query[0]-1, -1):
            table[i+1][query[3]] = table[i][query[3]]
            small = min(small, table[i][query[3]])
        # top
        for i in range(query[3]-1, query[1]-1, -1):
            table[query[0]][i+1] = table[query[0]][i]
            small = min(small, table[query[0]][i])
        table[query[0]][query[1]+1] = tmp

        answer.append(small)

    return answer

(3) 참고 및 정리

# 내가 실수한 부분, 이렇게 0을 삽입해 놓은 이차원 배열을 만들어버리면 append 할 때 배열이 추가적으로 더 생기게 됨.
# graph1 = [[0]*columns for _ in range(rows)]
# graph2 = [[0]*columns for _ in range(rows)]

# 이렇게 빈 배열을 만든 뒤에 append 하면 된다. 
graph1 = []
graph2 = []

# 내가 못만든 부분, 1부터 순서대로 어떻게 집어넣지 한참 생각함
for r in range(rows):
    graph1.append([a for a in range(r*columns+1, (r+1)*columns+1)])
    graph2.append([a for a in range(r*columns+1, (r+1)*columns+1)])

graph1 = copy.deepcopy(graph2)          # 깊은 복사해야 내가 의도한 대로 된다. 얕은 복사하면 의도대로 안됨.

처음 풀이처럼 한 이유는 회전시 이동하는 값이 다음 위치의 값을 차지함으로서 값을 덮어버리는 문제가 있습니다.
그래서 graph1 에서 회전한 결과를 graph2 에 만들어놓고 완성된 graph2 를 다시 graph1 에 깊은 복사하는 형식으로 해결하였으나 시간초과가 발생하였습니다.

시간초과한 풀이로 하는 경우 graph1, graph2 등 이차원 배열 2개를 사용해서 시간초과가 나는 것 같습니다.
참고한 풀이 처럼 graph 한개만을 이용해서 해결해야 하는 듯 합니다.

'참고한 풀이1'에서는 for문을 4개로 나누어 시계방향 역순으로 값들을 회전시켰으며 마지막에 처음에 x1,y1 에 해당하는 값을 기억하여 이동시켜줌으로서 이러한 문제를 해결하였습니다.

참고한 풀이1

로또의 최고 순위와 최저 순위 (Python)

0. 출처

• 유형 : 구현
• 링크 : 로또의 최고 순위와 최저 순위

1. 기록

• 22/03/27 (토)

2. 풀이

(1) 아이디어, 시간복잡도, 자료구조

1. 아이디어
>> lottos 와 win_nums 에서 일치하는 개수를 구한다. (최소 당첨 개수 및 등수)
>> lottos 에서 0 인 개수만큼 나머지와 일치한다고 가정한다. (최대 당첨 개수 및 등수)
>> lottos 에서 0 없이 모든 숫자가 부여된 경우는 등수를 어떻게 할 수 없음

2. 시간복잡도
>> ?

3. 자료구조
>> 리스트

(2) 풀이

def trans(cnt):
    prize = 0
    if cnt >= 2:
        prize = 7 - cnt
        return prize
    elif cnt <=1 :
        prize = 6
        return prize

def solution(lottos, win_nums):
    min_cnt = 0
    joker_cnt = 0
    for lotto in lottos:
        if lotto in win_nums:
            min_cnt += 1
        elif lotto == 0:
            joker_cnt += 1

    max_cnt = min_cnt + joker_cnt

    answer = []
    answer.append(trans(max_cnt))
    answer.append(trans(min_cnt))
    return answer

(3) 참고 및 정리