Programmers - Lv2 - 멀쩡한 사각형 / 오픈채팅방

멀쩡한 사각형

문제 설명

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

문제풀이

• 사각형의 한 꼭지점을 원점에, (w, h)를 대각선 좌표점으로 설정한다.

• 격자칸은 1cm x 1cm 크기이므로 총 w x h의 격자칸이 존재하며 테두리를 제외한 사각형 내에 교점이 n개 존재할 때, n + 1개의 사각형이 훼손된다.
  
  

• (0, 0)에서 (w, h)까지 선을 긋는다면 (w - 1)개의 y축과 나란한 직선과 교점을 가지며 w개의 사각형을 훼손시키며, (h - 1)개의 x축과 나란한 직선과 교점을 가지며 h개의 사각형을 훼손시킨다.

x축과 y축에 대하여 교점을 따로 계산하였기에 중복을 제거하는 과정이 필요하다.

• 원점에서 출발 후 처음 만나는 사각형은 훼손된 사각형으로써 중복계산되었다.
• 각각 계산된 w-1과 h-1은 각각의 정수 값에 해당하는 직선과 만나는 교점이다. y = (h/w) * x의 직선이라고 할 때 (h/w)를 정수로 만드는 x는 y도 정수로 만들기 때문에 중복 계산된다.
• 따라서 h와 w의 최대공약수로 w로 나눈 값의 배수의 개수만큼 제거가 필요하다.

python code

• 12번 테스트 케이스 : 시간 초과

import math

def solution(w, h):
    answer = w * h - (w + h - 1)

    gcd = math.gcd(w, h)
    a = [i for i in range(w//gcd, w, w//gcd)]
    answer += len(a)

    return answer

수정 python code

• w or h가 1인 경우 혹은 사각형이 정사각형인 경우를 분리하여 불필요한 계산과정을 줄여주는 것이 좋다.

import math

def solution(w, h):
    answer = w * h - (w + h - 1)
    gcd = math.gcd(w, h)
    if w == 1 or h == 1:
        return answer
    elif w == h:
        answer += (h - 1)
    else:
        a = [i for i in range(w//gcd, w, w//gcd)]
        answer += len(a)
    return answer

오픈채팅방

문제설명

카카오톡 오픈채팅방에서는 친구가 아닌 사람들과 대화를 할 수 있는데, 본래 닉네임이 아닌 가상의 닉네임을 사용하여 채팅방에 들어갈 수 있다.

신입사원인 김크루는 카카오톡 오픈 채팅방을 개설한 사람을 위해, 다양한 사람들이 들어오고, 나가는 것을 지켜볼 수 있는 관리자창을 만들기로 했다. 채팅방에 누군가 들어오면 다음 메시지가 출력된다.

"[닉네임]님이 들어왔습니다."

채팅방에서 누군가 나가면 다음 메시지가 출력된다.

"[닉네임]님이 나갔습니다."

채팅방에서 닉네임을 변경하는 방법은 다음과 같이 두 가지이다.

채팅방을 나간 후, 새로운 닉네임으로 다시 들어간다.
채팅방에서 닉네임을 변경한다.
닉네임을 변경할 때는 기존에 채팅방에 출력되어 있던 메시지의 닉네임도 전부 변경된다.

예를 들어, 채팅방에 "Muzi"와 "Prodo"라는 닉네임을 사용하는 사람이 순서대로 들어오면 채팅방에는 다음과 같이 메시지가 출력된다.

"Muzi님이 들어왔습니다."
"Prodo님이 들어왔습니다."

채팅방에 있던 사람이 나가면 채팅방에는 다음과 같이 메시지가 남는다.

"Muzi님이 들어왔습니다."
"Prodo님이 들어왔습니다."
"Muzi님이 나갔습니다."

Muzi가 나간후 다시 들어올 때, Prodo 라는 닉네임으로 들어올 경우 기존에 채팅방에 남아있던 Muzi도 Prodo로 다음과 같이 변경된다.

"Prodo님이 들어왔습니다."
"Prodo님이 들어왔습니다."
"Prodo님이 나갔습니다."
"Prodo님이 들어왔습니다."

채팅방은 중복 닉네임을 허용하기 때문에, 현재 채팅방에는 Prodo라는 닉네임을 사용하는 사람이 두 명이 있다. 이제, 채팅방에 두 번째로 들어왔던 Prodo가 Ryan으로 닉네임을 변경하면 채팅방 메시지는 다음과 같이 변경된다.

"Prodo님이 들어왔습니다."
"Ryan님이 들어왔습니다."
"Prodo님이 나갔습니다."
"Prodo님이 들어왔습니다."

채팅방에 들어오고 나가거나, 닉네임을 변경한 기록이 담긴 문자열 배열 record가 매개변수로 주어질 때, 모든 기록이 처리된 후, 최종적으로 방을 개설한 사람이 보게 되는 메시지를 문자열 배열 형태로 return 하도록 solution 함수를 완성하라.

제한사항

record는 다음과 같은 문자열이 담긴 배열이며, 길이는 1 이상 100,000 이하이다.
다음은 record에 담긴 문자열에 대한 설명이다.
모든 유저는 [유저 아이디]로 구분한다.
[유저 아이디] 사용자가 [닉네임]으로 채팅방에 입장 - "Enter [유저 아이디][닉네임]" (ex. "Enter uid1234 Muzi")
[유저 아이디] 사용자가 채팅방에서 퇴장 - "Leave [유저 아이디]" (ex. "Leave uid1234")
[유저 아이디] 사용자가 닉네임을 [닉네임]으로 변경 - "Change [유저 아이디][닉네임]" (ex. "Change uid1234 Muzi")
첫 단어는 Enter, Leave, Change 중 하나이다.
각 단어는 공백으로 구분되어 있으며, 알파벳 대문자, 소문자, 숫자로만 이루어져있다.
유저 아이디와 닉네임은 알파벳 대문자, 소문자를 구별한다.
유저 아이디와 닉네임의 길이는 1 이상 10 이하이다.
채팅방에서 나간 유저가 닉네임을 변경하는 등 잘못 된 입력은 주어지지 않는다.

문제풀이

• record 데이터를 검사하여 확정된 닉네임과 uid를 얻는다.
• record를 검사하여 행동에 따른 알림을 answer에 삽입한다.

python code

def solution(record):
    answer = []
    dic = {}
    for i in record:
        if i[0] == 'E' or i[0] == 'C':
            act, uid, nickname = map(str, i.split())
            dic[uid] = nickname

    for i in record:
        if i[0] == 'E':
            act, uid, nickname = map(str, i.split())
            temp = dic[uid] + "님이 들어왔습니다."
            answer.append(temp)
        elif i[0] == "L":
            act, uid = map(str, i.split())
            temp = dic[uid] + "님이 나갔습니다."
            answer.append(temp)

    return answer