백준 집합과 맵

2024. 12. 11. 22:26ㆍAlgorithms/백준알고리즘 연습 

import sys

n = int(sys.stdin.readline())
s = {}

for _ in range(n):
    name, action = sys.stdin.readline().split()
    if action == "enter":
        s[name] = True
    elif action == "leave":
        s[name] = False

present = [name for name, status in s.items() if status]
for name in sorted(present, reverse=True):
    print(name)

10815번

숫자 카드 

시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 256 MB 128739 55117 40298 42.801%

문제

숫자 카드는 정수 하나가 적혀져 있는 카드이다. 상근이는 숫자 카드 N개를 가지고 있다. 정수 M개가 주어졌을 때, 이 수가 적혀있는 숫자 카드를 상근이가 가지고 있는지 아닌지를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다. 두 숫자 카드에 같은 수가 적혀있는 경우는 없다.

셋째 줄에는 M(1 ≤ M ≤ 500,000)이 주어진다. 넷째 줄에는 상근이가 가지고 있는 숫자 카드인지 아닌지를 구해야 할 M개의 정수가 주어지며, 이 수는 공백으로 구분되어져 있다. 이 수도 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다

출력

첫째 줄에 입력으로 주어진 M개의 수에 대해서, 각 수가 적힌 숫자 카드를 상근이가 가지고 있으면 1을, 아니면 0을 공백으로 구분해 출력한다.

예제 입력 1 복사

5
6 3 2 10 -10
8
10 9 -5 2 3 4 5 -10

예제 출력 1 복사

1 0 0 1 1 0 0 1

 

초기 코드 

import sys 
n = int(sys.stdin.readline())
num = []
sang = []
for _ in range(n):
    s = int(sys.stdin.readline())
    num.append(s)

m = int(sys.stdin.readline())
for _ in range(m):
    x = int(sys.stdin.readline())
    sang.append(x)

for i in sang:
    for j in num:
        if i==j:
            print(1)
        else :
            print(0)

 

정답코드

import sys 

n = int(sys.stdin.readline())
num_set = set(map(int, sys.stdin.readline().split()))

m = int(sys.stdin.readline())
sang = list(map(int, sys.stdin.readline().split()))

for i in sang:
    print(1 if i in num_set else 0, end=' ')

num_set = set(map(int, sys.stdin.readline().split()))

이런 류의 표현을 잘 써야 시간복잡도를 줄일 수 있음

loop로 넣는 것은 숫자가 커지면 더 복잡해짐

Yes, using num_set = set(map(int, sys.stdin.readline().split())) can reduce the time complexity compared to the loop-based approach

 

. Here's why:

 

  1. Single operation: The set construction with map() performs the conversion in a single operation, which is generally more efficient than multiple individual operations
  2. Optimized internal implementation: Python's set() constructor is optimized to handle iterable inputs efficiently, often performing better than adding elements one by one
  3. Average time complexity: Both approaches have an average time complexity of O(n), where n is the number of elements. However, the set constructor method is typically faster in practice due to its optimized implementation.
  4. Reduced overhead: The single-line approach eliminates the loop overhead, which can be significant for large inputs.
  5. Memory efficiency: Creating the set directly from the input can be more memory-efficient, as it avoids creating an intermediate list

 

14425번

 

초기 코드

import sys 

n,m = map(int, sys.stdin.readline().split())
s = []
m_set = set()
count = 0
for _ in range(n):
    x = str(sys.stdin.readline())
    s.append(x)

for _ in range(m):
    y = str(sys.stdin.readline())
    m_set.add(y)
    
for i in m_set:
    if i in s:
        count += 1
    else :
        count += 0

print(count)

 

수정 코드

import sys 

n, m = map(int, sys.stdin.readline().split())
s = set()
count = 0

for _ in range(n):
    s.add(sys.stdin.readline().strip())

for _ in range(m):
    if sys.stdin.readline().strip() in s:
        count += 1

print(count)

 

7785번 

초기 코드 

딕셔너리 형태로 만들어 한번만 나타난 이름을 출력하도록 디자인했음(들어오면 enter 일거고 계속 남아있으면 다시 이름이 안남는다고 생각함 )

수정 코드 

import sys
n = int(sys.stdin.readline())
s = {} 
for _ in range(n):
    x, y = sys.stdin.readline().split()  # Read x and y as strings
    if x in s:
        s[x] += 1
    else:
        s[x] = 1 

for key,value in s.items():
    if value == 1:
        print(key)

그런데 틀림

프린트를 한줄씩 해놔야하는데 아니어서 그런가?

"현재 회사에 있는 사람의 이름을 사전 순의 역순으로 한 줄에 한 명씩 출력한다."

사전순의 역순 이라는 것을 놓쳤고, 어떤 사람이 다시 들어와서 있을 확률도 있음

 

정답 코드

import sys

n = int(sys.stdin.readline())
present = set()

for _ in range(n):
    name, action = sys.stdin.readline().split()
    if action == "enter":
        present.add(name)
    elif action == "leave":
        present.discard(name)

for name in sorted(present, reverse=True):
    print(name)

이름 옆에 leave가 있으면 퇴근했다고 가정하고, 아예 discard 하도록 유도 

set으로 만들어서 중복값을 없앰 - 퇴근했으면 enter - leave 가 짝으로 남아있을 것이고, 우리에게 leave 했냐가 중요하기 때문에 

남아있는 name 값을 출력 

 

1620번

로직 분석

1. n,m값을 받고

2. index 값은 num으로 name은 이름을 받음

3. 두 값을 info리스트에 넣음 

4. x를 불러오는데, 정수형이면 그 정수를 인덱스로 가지는 값 가져오기 아니면 인덱스에 해당하는 값 불러오기

 

초기 코드 

import sys
n,m = map(int,sys.stdin.readline().split())
info = []
for i in range(n):
    num = i
    name = sys.std.readline().strip()
    info.append[name,num]

for _ in range(m):
    x = sys.stdin.readline()
    if isinstance(x, int) :
        print(info.index(x))
    else : 
        print(info[x])

attribute error 남

 

if isinstance(x, int) : print(info.index(x)) 가 틀린 이유  이건 틀린거야?
  1. sys.stdin.readline()으로 입력받은 값은 항상 문자열(string)입니다. 따라서 isinstance(x, int)는 항상 False를 반환할 것입니다.
  2. info.index(x)는 리스트에서 사용하는 메서드인데, 여기서 info는 리스트가 아닙니다.
  3. 입력이 숫자인지 문자열인지 구분하려면 isdigit() 메서드를 사용하는 것이 더 적절합니다

 

import sys

n, m = map(int, sys.stdin.readline().split())
info = {}

for i in range(1, n+1):  # 1부터 n까지
    name = sys.stdin.readline().strip()
    info[i] = name
    info[name] = i

for _ in range(m):
    x = sys.stdin.readline().strip()
    if x.isdigit(): %숫자로만이루어져있으
        print(info[int(x)])  #인덱스값에해당하는값을 불러오고  
    else: #아니면 인덱스를 가져와라 
        print(info[x])

 

x.isdigit() : 문자열이 정수로만 이루어져있는지 확인 

 

10816번 숫자 카드 2

숫자 카드 2

 
시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 256 MB 168000 66701 47465 38.050%

문제

숫자 카드는 정수 하나가 적혀져 있는 카드이다. 상근이는 숫자 카드 N개를 가지고 있다. 정수 M개가 주어졌을 때, 이 수가 적혀있는 숫자 카드를 상근이가 몇 개 가지고 있는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다.

셋째 줄에는 M(1 ≤ M ≤ 500,000)이 주어진다. 넷째 줄에는 상근이가 몇 개 가지고 있는 숫자 카드인지 구해야 할 M개의 정수가 주어지며, 이 수는 공백으로 구분되어져 있다. 이 수도 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다.

출력

첫째 줄에 입력으로 주어진 M개의 수에 대해서, 각 수가 적힌 숫자 카드를 상근이가 몇 개 가지고 있는지를 공백으로 구분해 출력한다.

예제 입력 1 복사

10
6 3 2 10 10 10 -10 -10 7 3
8
10 9 -5 2 3 4 5 -10

예제 출력 1 복사

3 0 0 1 2 0 0 2

 

초기 코드

숫자 카드 1인데 카운트만 하도록 변경 

조금 다른 것이 

1. 먼저 주어지는 숫자에 각 숫자가 몇번 나왔는지 알아야 함

2. 주어지는 숫자에 1번을 반환해야 함 

import sys 

n = int(sys.stdin.readline())
num_set = set(map(int, sys.stdin.readline().split()))

m = int(sys.stdin.readline())
sang = list(map(int, sys.stdin.readline().split()))

for i in sang:
    print(sang.count(i) if i in num_set else 0, end=' ')

시간 초과 됨 

 

시간 초과인 이유:

  1. sang.count(i) 메서드 사용:
    이 메서드는 리스트 전체를 순회하며 각 요소를 확인하므로, 시간 복잡도가 O(m)입니다. 이를 m번 반복하므로 전체 시간 복잡도는 O(m^2)가 됩니다.
  2. 비효율적인 검색:
    num_set에서 i의 존재 여부만 확인하고 있어, 실제 카드의 개수를 세지 않습니다.
import sys
from collections import Counter

n = int(sys.stdin.readline())
cards = Counter(map(int, sys.stdin.readline().split()))

m = int(sys.stdin.readline())
queries = list(map(int, sys.stdin.readline().split()))

print(' '.join(str(cards[q]) for q in queries))

정답코드 580 ms 걸림

이 방식은 각 쿼리에 대해 O(1) 시간에 결과를 얻을 수 있어, 전체 시간 복잡도가 O(n + m)으로 크게 개선 됨

Counter의 역할 : 요소 개수 세기: 리스트, 문자열 등의 iterable 객체에서 각 요소의 등장 횟수를 계산

 

예를 들어, 입력으로 [1, 2, 3, 1, 2, 1]이 주어졌다면, cards는 다음과 같이 저장됩니다:Counter({1: 3, 2: 2, 3: 1})

 

1764번 듣보잡 

 

초기 코드 

import sys
n,m = map(int,sys.stdin.readline().split())
a_list = []
b_list = [] 
match = 0
match_list = []
for _ in range(n):
    x = sys.stdin.readline()
    a_list.append(x)
    
for _ in range(m):
    y = sys.stdin.readline()
    b_list.append(y)

for i in b_list:
    for j in a_list:
        if i == j:
            match += 1 
            match_list.append(i)
print(f"{match}\n" + "\n".join(match_list))

시간 초과 됨 

어떻게 줄일 수 있을까 -> 루프를 최대한 없애야 함

 

import sys
n,m = map(int,sys.stdin.readline().split())
match = 0
match_list = []
for _ in range(n):
    a_list = list(map(int, sys.stdin.readline().split()))
for _ in range(m):
    b_list = list(map(int, sys.stdin.readline().split()))

c_list = [list(set(a_list).intersection(i) for i in b_list]

print(f"{len(c_list)}")
for item in c_list:
    print(item)

여기까지가 최대... 답지 안보고 풀어보자.. 

attribute error남 

 

import sys

n, m = map(int, sys.stdin.readline().split())

a_set = set(map(int, sys.stdin.readline().split()))
b_set = set(map(int, sys.stdin.readline().split()))

c_set = a_set ^ b_set

print(len(c_set))

c_set = a_set ^ b_set  => 대칭차집합을 연산하는 코드  (A - B) ∪ (B - A)

 

왜 list가 아닌 set으로 계산해야하는가?

  1. 중복 제거:
    • 집합은 자동으로 중복을 제거합니다. 입력에 중복된 숫자가 있어도 각 원소는 한 번만 저장됩니다.
  2. 연산 효율성:
    • 집합은 해시 테이블을 기반으로 하여 원소 검색, 추가, 제거가 O(1) 시간에 가능합니다.
    • 리스트에서 같은 작업을 하면 O(n) 시간이 걸립니다.
  3. 대칭 차집합 연산:
    • 집합은 ^ 연산자를 통해 대칭 차집합을 쉽고 빠르게 계산할 수 있습니다.
    • 리스트로 이 작업을 하려면 복잡한 루프와 조건문이 필요합니다.
  4. 메모리 효율성:
    • 중복이 제거되므로 메모리 사용이 더 효율적일 수 있습니다.
  5. 코드 간결성:
    • 집합을 사용하면 코드가 더 간결하고 읽기 쉬워집니다.

 

 

11478번

서로 다른 부분 문자열의 개수

외부 모듈을 사용할 수 없기 때문에 combination을 만들 수 있는 함수를 지정하여 사용 

def comb(arr, n):
    result = []
    
    if n> len(arr):
        return result
    if n == 1:
        for i in arr:
            result.append([i])
    elif n > 1 : 
        for i in range(len(arr) - n + 1) :
            for j in comb(arr[i+1:], n-1):
                result.append([arr[i]] + j)
    return result

arr = list(input())
count = 0
for i in range(1, len(arr) + 1): 
    count += len(comb(arr, i))

print(count)

 

맞는 코디이지만 시간 초과됨

 

 

정답 코드 

s=input()
total=set()
for i in range(len(s)):
    for j in range(i,len(s)):
        total.add(s[i:j+1])#i번째 문자부터 부분문자열 구하기

print(len(total))​
 

 

'Algorithms > 백준알고리즘 연습' 카테고리의 다른 글

백준 알고리즘 약수, 소수와 배수 2 (2)  (1) 2024.12.22
약수, 배수와 소수 2  (2) 2024.12.14
백준 정렬(2)  (2) 2024.12.10
백준 부루트 포스 (복습 필요)  (2) 2024.12.09
백준 시간복잡도  (0) 2024.12.07

관련글

티스토리툴바