본문 바로가기

해시6

[백준 10546] 배부른 마라토너 - python https://www.acmicpc.net/problem/10546💡문제 분석 요약마라토너라면 국적과 나이를 불문하고 누구나 참가하고 싶어하는 백준 마라톤 대회가 열린다. 42.195km를 달리는 이 마라톤은 모두가 참가하고 싶어했던 만큼 매년 모두가 완주해왔다. 단, 한 명만 빼고!모두가 참가하고 싶어서 안달인데 이런 백준 마라톤 대회에 참가해 놓고 완주하지 못한 배부른 참가자 한 명은 누굴까?입력첫째 줄에는 참가자 수 N이 주어진다. (1 ≤ N ≤ 105)N개의 줄에는 참가자의 이름이 주어진다.추가적으로 주어지는 N-1개의 줄에는 완주한 참가자의 이름이 쓰여져 있다.참가자들의 이름은 길이가 1보다 크거나 같고, 20보다 작거나 같은 문자열이고, 알파벳 소문자로만 이루어져 있다.참가자들 중엔 동명이.. 2025. 1. 8.
[백준 2002번] 추월 - 파이썬 https://www.acmicpc.net/problem/2002 💡문제 분석 요약터널에 들어가는 차의 순서와 터널에서 나오는 차의 순서를 알 때, 터널 안에서 추월한 차의 수를 구하여라. 💡알고리즘 설계1. 터널에 들어가는 차 번호와 그 순서를 해시로 저장한다.2. 터널에서 나오는 차 마다, 그 차보다 늦게 나오는 차와 들어갈 때 순서를 비교하여 자신 뒤에 자신보다 빨리 들어간 차가 있으면 추월 횟수를 1 늘린다. 💡코드import sysinput = sys.stdin.readlineN=int(input())in_order={}for i in range(N): car=input().rstrip() in_order[car]=iout_list=[]for i in range(N): ca.. 2024. 5. 18.
[백준 2910번] 빈도 정렬 - 파이썬 https://www.acmicpc.net/problem/2910 2910번: 빈도 정렬 첫째 줄에 메시지의 길이 N과 C가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ C ≤ 1,000,000,000) 둘째 줄에 메시지 수열이 주어진다. www.acmicpc.net 💡문제 분석 요약 입력으로 주어진 수열을 빈도가 많은 순으로 정렬한 다음 출력한다. 💡알고리즘 설계 1. 해시에 해당 숫자가 저장된 빈도를 저장한다. 2. 해시의 값을 기준으로, 빈도가 높은 순으로 정렬한다. 3, for문을 이용해 해시의 값 만큼 해당 숫자를 출력한다. 💡코드 import sys input = sys.stdin.readline N, C=map(int, input().split()) message=list(map(int, .. 2024. 4. 13.
[백준 9017번] 크로스 컨트리 - 파이썬 https://www.acmicpc.net/problem/9017 9017번: 크로스 컨트리 입력 데이터는 표준입력을 사용한다. 입력은 T 개의 테스트 케이스로 주어진다. 입력 파일의 첫 번째 줄에 테스트 케이스의 수를 나타내는 정수 T 가 주어진다. 두 번째 줄부터는 두 줄에 하나의 www.acmicpc.net 💡문제 분석 요약 크로스 컨트리 달리기는 주자들이 자연적인 야외의 지형에 만들어진 코스를 달리는 운동 경기이다. 경주 코스는 일반적으로 4에서 12 킬로미터이며, 숲이나 넓은 땅을 통과하는 풀과 흙으로 된 지면과 언덕과 평평한 지형을 포함한다. 이 경기는 주자들의 개인성적을 매기고, 이를 가지고 팀의 점수를 계산한다. 한 팀은 여섯 명의 선수로 구성되며, 팀 점수는 상위 네 명의 주자의 점수를 .. 2024. 4. 13.
[백준 18870번] 좌표 압축 - 파이썬 https://www.acmicpc.net/problem/18870 18870번: 좌표 압축 수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다. Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표 Xj의 개수와 같아야 한다. X1, X2, ..., XN에 www.acmicpc.net 💡문제 분석 요약 수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다. Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표 Xj의 개수와 같아야 한다. X1, X2, ..., XN에 좌표 압축을 적용한 결과 X'1, X'2, ..., X'N를 출력해보자. 💡알고리즘 설.. 2024. 3. 31.
[백준 20920번] 영단어 암기는 괴로워 - 파이썬 https://www.acmicpc.net/problem/20920 20920번: 영단어 암기는 괴로워첫째 줄에는 영어 지문에 나오는 단어의 개수 $N$과 외울 단어의 길이 기준이 되는 $M$이 공백으로 구분되어 주어진다. ($1 \leq N \leq 100\,000$, $1 \leq M \leq 10$) 둘째 줄부터 $N+1$번째 줄까지 외울 단www.acmicpc.net 💡문제 분석 요약영단어를 입력받고, 자주 입력받은 횟수, 단어 길이, 사전순으로 정렬하여 출력한다. 💡알고리즘 설계1. 해시를 이용하여 key에 단어를, value에 단어가 입력된 횟수를 하나씩 늘리면서 저장한다.- hash에 입력받은 단어가 있는지 체크하고, 없으면 hash[word]=1, 있으면 hash[word]+=1로 갯수.. 2024. 3. 16.

티스토리툴바