오늘의 문제
https://www.acmicpc.net/problem/2776
일단 문제를 보자마자 실버4 문제이고 따로 어려운 부분이 안보이길래 '이게 왜 미들러 문제지?' 싶었다.
따로 함정이 있는건가...? 실버 4문제가 정답 비율이 32.46% 일리가 없는데....
그리고 곧 왜 실버4 문제가 처참한 정답률을 가지는게 알게 된다.
나의 첫 번째 풀이 (실패)
파이참에서 결과도 확인한 후에, 백준에 아래의 코드를 넣었다.
당연히 통과일줄 알았는데.
TC = int(input())
for _ in range(TC):
N = int(input())
note1 = list(map(int, input().split()))
M = int(input())
note2 = list(map(int, input().split()))
for i in note2:
if i in note1:
print(1)
else:
print(0)
시간초과가 나왔다.
뭐지? 약간 어리둥절한 상태로 무엇이 문제인지 생각해보기 시작했다.
오답 원인 파악 하기
일단 탐색 시간이 기준치보다 길기 때문에 이런 문제가 생긴 것이고, 빠르게 결과가 나오려면 어떻게 수정해야할까 고민했다.
이때, 저번에 복습차원으로 공부했던 개념이 생각났다.
튜플은 리스트에 비해 상대적으로 공간 효율적이다.
리스트보다 메모리를 효율적으로 사용해야 할 때 사용한다.
이거구나...! 그래서 행복하게 리스트(list)를 튜플(tuple)로만 바꿔서 다시 넣었다.
그런데 또 시간 초과가 나왔다. ㅋㅋㅋㅋㅋㅋ
그래서 다시 공부했던 개념을 찾아보는데, 집합이 눈에 띄었다.
아, 혹시 이건가? 싶어서 튜플 대신 집합(set) 을 넣었는데, 이번에는 결과가 이상했는지 틀렸다고 나왔다.
(급해서 파이참 안 돌린 사람...)
그래서 다시 파이참에 넣고 돌렸는데, 진짜로 결과가 이상했다.
분명 없는 숫자라는 결과가 나와야 하는데 있다고 나오고, 있는 숫자는 없다고 나오고.
뭐지... 싶어서 원인을 한참 생각했다 ㅋㅋㅋ
해결 방안
그러다가 문득 집합은 순서 신경을 안 쓴다는게 생각났다.
이거구나. 진짜 이거다. 싶었다.
그래서 순서 신경을 쓰지 않아도 되는 NOTE1 은 set 처리를 하고
순서대로 확인해야 하는 NOTE2는 list 처리를 해서 코드에 넣었다.
결과는....!!!
TC = int(input())
for _ in range(TC):
N = int(input())
note1 = set(map(int, input().split()))
M = int(input())
note2 = list(map(int, input().split()))
for i in note2:
if i in note1:
print(1)
else:
print(0)
오예 성공했다.
그런데 이따가 저녁에 관련 해설 강의를 듣겠지만, 왠지 이게 완전한 정답은 아닌 것 같다.
숫자를 저장한 배열을 나눠서 뭔가 있는지 없는지 확인해야 하나? 하는 생각도 있고.
그런데 뭘 적용해야 할지는 뭘라서 일단 자료구조를 다르게 적용하는 것으로 내 풀이는 마쳤다.
앞으로 더 꾸준히 공부해서 문제를 봤을 때, 어떤 풀이 방법이 적절할지 고민하는 습관을 길러야겠다.
+++ 추가 글
힌트 안 보고 풀고 싶어서 그냥 제출해버렸는데, 제출 후에 힌트를 봤더니 이분탐색(이진탐색) 이었다. 😂😂😂
그래서 이분 탐색 강의를 듣고 있다.
다시 이분탐색으로 풀어서 또 제출해봐야겠다.
https://youtu.be/94RC-DsGMLo?si=1XX4C7542_iAdZXP
8시 ~ 10시 : 스터디 내용 정리
- OT
- 미션 내용 다시 소개
: 전체화면 캡쳐 / 디스코드 출첵방 화면(댓글 작성) 캡쳐해서 9시 이후에 저장 / TIL 제출
- TIL 에 대한 소개
- 디스코드 사용법 : 질문방 / TIL 공유방
- 8시 ~ 10시 스케줄 소개
오늘 한 공부
1. 코테 1문제
2. 이진탐색(이분탐색) 강의 듣기
3. 강의 들은 내용 정리 - 깃헙 업로드
4. 대규모 시스템 설계 기초 : 1장 (단일서버 ~ CDN) 정리
5. 일본어 칸지 20자
6. 정처기 필기 공부 계획 세우기
7. TIL 적기
'IT > 코딩테스트' 카테고리의 다른 글
[IT/코딩테스트] 자율 코테 스터디<주말> TIL + BOJ2110 (0) | 2025.01.18 |
---|---|
[IT/코딩테스트] 99클럽 코테 스터디5일차 TIL + BOJ2470 (1) | 2025.01.17 |
[IT/코딩테스트] 99클럽 코테 스터디4일차 TIL + BOJ2343 (1) | 2025.01.17 |
[IT/코딩테스트] 99클럽 코테 스터디3일차 TIL + BOJ11663 (1) | 2025.01.16 |
[IT/코딩테스트] 99클럽 코테 스터디2일차 TIL + BOJ1654 (3) | 2025.01.14 |