백준 [7785.회사에 있는 사람] | Python

✏️ 문제

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

7785번: 회사에 있는 사람

 

✏️ 풀이방법

1. 집합(log) 안에 없는 이름이면 새로 추가하고, 존재하는 이름이면 해당 이름을 삭제

 

 

📌 코드

n = int(input())
log = set({})
cnt = 0
while True:
    i = input().split()[0]
    if i not in log:
        log.add(i)
    else:
        log.remove(i)
    cnt +=1
    if cnt ==n:
        break

log = sorted(log,reverse = True)

for i in log:
    print(i)

 

 

📌 결과

#입력 
4
Baha enter
Askar enter
Baha leave
Artem enter

#출력
Askar
Artem

 

 

🤔 시행착오.1

n = int(input())
log = []
name = []
for i in range(n):
    log.append(list(map(str,input().split())))
    name.append(log[i][0])

name = sorted(list(set(name)), reverse=True) #역순으로 출력

for i in name:
    if log.count(i)%2 != 0: #홀수일 때 남아있는 사람 출력
        print(i)

- 입출력 기록을 담은 2차원리스트(log)와 입출력 기록에서 중복을 제외한 이름을 갖고있는 리스트(name)을 가지고 입출력기록에 있는 이름이 홀수번이면 회사에 남아있는 사람으로 출력하도록 했다.

- 하지만 2치원리스트(log)에서 1차원리스트의 0번째인 이름만 count할 수가 없어서 코드를 수정해야했다.

 

 

🤔 시행착오.2

n = int(input())
log = []
name = []
for _ in range(n):
    log.append(input().split()[0])

name = sorted(list(set(log)), reverse=True) #역순으로 출력

for i in name:
    if log.count(i)%2 != 0: #짝수일 때 남아있는 사람 출력
        print(i)

- 시행착오.1에서는 enter, leave 기록까지 모두 다 받아서 2차원리스트(log)에서 이름의 정보로 count할 수 없는 문제가 발생해서 이름데이터만 가져와서 사용할 수 있도록 수정했다.

- 출력 결과는 일치하나 시간초과

- 입출력기록에있는 이름을 모두 다 비교하며 찾아야 하기에 시간초과가 발생했다고 생각했다.

- 리스트의 count연산이 O(n)의 시간복잡도를 갖기에 시간초과가 발생하는 것 이었다.

- 데이터의 자료형을 set으로 변경하거나 dict로 변경하면 된다.

- set자료형에는 count메소드가 존재하지 않기 때문에 위 코드로는 실행할 수 없다. 

 

 

🤔 시행착오.3

n = int(input())
log = []
name = []
i = 0
while True:
    name.append(input().split()[0])
    if input().split()[0] not in log:
        log.append(input().split()[0])
    else:
        log.remove(input().split()[0])
    i +=1
    if i ==n:
        break

print(log)
print(name)

- 리스트 자료형의 시간복잡도로 시간초과가 발생하는 지 모르고 입출력기록을 모두 받아서 시간초과가 발생한 줄 알고 출입기록을 입력받을 때 이미 리스트에 이름이 존재하면 해당 이름을 제거하는 방법으로 풀었다.

- input().split()[0]값이 코드 한 줄씩 마다 다르게 들어가서 예상했던 출력결과와 다르게 출력되었었다.

 

 

🤔 시행착오.4

n = int(input())
log = []
cnt = 0
while True:
    i = input().split()[0]
    if i not in log:
        log.append(i)
    else:
        log.remove(i)
    cnt +=1
    if cnt ==n:
        break
        
log = sorted(log,reverse = True)

for i in log:
    print(i)

- 시행결과.4를 해결해서 풀었으나 시간초과 문제 발생

- remove의 시간복잡도O(N)인데 반복문으로 계산하면 O(N^2)이 되서 시간초과 문제 발생

- 리스트가 아니라 다른 자료형으로 문제를 풀어야 시간초과가 발생하지 않을 것이기에 set으로 데이터 자료형을 변경

 

 

🔎 다른풀이

import sys

n = int(sys.stdin.readline())
temp = dict() # 딕셔너리 형

# 반복문을 통해 출입 기록울 확인한다.
for _ in range(n):
    a, b = map(str, sys.stdin.readline().split())

    # 출입을 했으면 딕셔너리로 받는다.
    if b == "enter":
        temp[a] = b
    # 퇴근을 했으면 삭제해준다.
    else:
        del temp[a]

# 사전 순의 역순으로 정렬한다.
temp = sorted(temp.keys(), reverse=True)

for i in temp:
    print(i)
    
    
#https://fre2-dom.tistory.com/212

-  딕셔너리 자료형으로 시간초과문제 해결

 

 

📝 메모

- 시간복잡도 고려해서 문제 풀기

- 자료형마다 시간복잡도가 다름

- list의 포함연산자는 O(N)의 시간복잡도를 갖고 set의 포함연산자는 O(1)의 시간복잡도를 갖는다.