21. [백준] 별찍기 7, 붙임성 좋은 총총이

1. 별찍기 7

https://www.acmicpc.net/problem/2444

2444번: 별 찍기 - 7

 

해결 1.

import sys
input = sys.stdin.readline

N = int(input())

# sol)
for i in range(1,N):
    print(' '*(N-i) + '*'*(2*i-1))

for i in range(N,0,-1):
    print(' '*(N-i) + '*'*(2*i-1))

 

해결 2. range(N,0,-1)을  reversed을 이용해 표현해보았다.

# sol2)
for i in range(1,N):
    print(' '*(N-i) + '*'*(2*i-1))

for i in reversed(range(1,N+1)):
    print(' '*(N-i) + '*'*(2*i-1))

 

해결 3. 재귀를 이용

재귀로 문제를 해결하기 위해서 먼저 규칙성을 찾아보았다.

 

# 공백 / *개수

# 4 1

# 3 3

# 2 5  

# 1 7

# 0 9

# 1 7

# 2 5

# 3 3

# 4 1

이 규칙성을 이용해서 재귀로 문제를 풀었다.

def solution(n,i):
    if n-i < 0:
        return 0
    print(' '*(n-i) + '*'*(2*i-1))
    solution(n,i+1)
    if n-1 != 0:
        print(' '*(n-i+1) + '*'*(2*i-3))
        
n = int(input())
solution(n,1)

 

세 풀이 방식 모두 결과값은 아래와 같이 나온다.

 

    *
   ***
  *****
 *******
*********
 *******
  *****
   ***
    *

 

 

2. 붙임성 좋은 총총이

26069번: 붙임성 좋은 총총이 (acmicpc.net)

26069번: 붙임성 좋은 총총이

문제가 너무 귀여웟...ㅋㅋㅋ 킹받기도 하고..?ㅋㅋㅋ

어쨌든~ 총총이도 두 가지 풀이로 해결해보았다.

 

해결 1 - 집합  set을 이용

import sys; 
input = sys.stdin.readline

danceset = {'ChongChong'}
N = int(input())

for _ in range(N):
    a, b = input().split()
    
    if a in danceset:
        danceset.add(b)
    elif b in danceset:
        danceset.add(a)
    else:
        pass

print(len(danceset))

danceset에는 춤추는 사람들.. 그러니까 총총이에게 전염된 사람들이 원소인 집합이다! 

둘 중 한 명이라도 춤을 추고 있다면 나머지 한 명도 danceset에 넣어주었다.

 

 

해결 2 - defaultdict 이용

import sys; 
input = sys.stdin.readline
from collections import defaultdict

dance = defaultdict(bool)
# 모든 해시에 대해 디폴트 값은 False
dance['ChongChong'] = True # 총총이만 True로
answer = 1

for _ in range(int(input())):
    A, B = input().split()
    if dance[A]:
        if not dance[B]:
            dance[B] = True
            answer += 1
    elif dance[B]:
        dance[A] = True
        answer += 1

print(answer)

 

해결 1이 44초, 해결 2가 64초 정도 소요되며 시간복잡도는 해결 1이 더 좋다.