📍 2941 (크로아티아 알파벳)
2941번: 크로아티아 알파벳
예전에는 운영체제에서 크로아티아 알파벳을 입력할 수가 없었다. 따라서, 다음과 같이 크로아티아 알파벳을 변경해서 입력했다. 크로아티아 알파벳 변경 č c= ć c- dž dz= đ d- lj lj nj nj š s= ž z=
www.acmicpc.net
# 크로아티아 알파벳
import sys
input = sys.stdin.readline
# 입력 받아오기
alphabet = input().strip()
# 변경되는 알파벳 리스트로 생성해두기
change = ['c=','c-','dz=','d-','lj','nj','s=','z=']
cnt = 0 # 알파벳 수 초기화
# 입력받은 문자열에 변경되는 알파벳이 존재하는 체크
for c in change:
# print(c)
if c in alphabet:
# 변경 가능할 경우 해당 알파벳이 포함된 수만큼 cnt 증가
cnt += alphabet.count(c)
# 변경된 문자는 . 으로 문자열 변경 해두기 -> ''으로 변경시 strip 효과로 문자열 변경이 생기는 문제 발생
alphabet = alphabet.replace(c,'.')
# 변경 문자 체크 끝난 후 .를 제거 후 일반 알파벳 수 계산
alphabet = alphabet.replace('.','')
cnt += len(alphabet)
print(cnt)
💬 풀이 설명
크게 어렵던 문제는 아니라 주요 사항들은 주석으로 설명을 적어두었다.
그런데 굳이 for 문 안에서 cnt를 계산할 필요가 없다는 것을 깨달았다...
# 크로아티아 알파벳
import sys
input = sys.stdin.readline
alphabet = input().strip()
change = ['c=','c-','dz=','d-','lj','nj','s=','z=']
for c in change:
if c in alphabet:
alphabet = alphabet.replace(c,'.')
print(len(alphabet))
cnt 변수를 생성하지 않고 크로아티아 문자를 . 으로 변환해준 후 나중에 len 함수를 통해 문자열 길이를 반환해주면 끝..😅
📍 1193 ( 분수 찾기)
1193번: 분수찾기
첫째 줄에 X(1 ≤ X ≤ 10,000,000)가 주어진다.
www.acmicpc.net
# 피라미드 접근
N = int(input())
add = 0 # N번째 분수를 찾기 위해 필요한 요소의 수
i = 1 # N번째 분수가 포함된 줄
while True:
add += i
if add >= N :
break
i += 1
# print(add)
# print(i)
# 답 출력에는 사용되진 않지만 배열 구조를 파악하기 위해서 추가해 둠
arr1 = [[str(z+1)+'/'+str(j+1)for j in range(i)]for z in range(i)]
print('===분수 배열===')
for a in arr1:
print(a)
print(f'{N}번째 분수 : ',end='')
turn = add-N
if i%2 == 0 :
print(f'{i-turn}/{1+turn}')
else:
print(f'{1+turn}/{i-turn}')
>> ===분수 배열===
['1/1', '1/2', '1/3', '1/4', '1/5']
['2/1', '2/2', '2/3', '2/4', '2/5']
['3/1', '3/2', '3/3', '3/4', '3/5']
['4/1', '4/2', '4/3', '4/4', '4/5']
['5/1', '5/2', '5/3', '5/4', '5/5']
12번째 분수 : 4/2
💬 풀이 설명
이 문제는 지그재그의 규칙을 찾아 내는 것이 중요하다. 우선 지그재그란 말을 이해하는 것도 힘들었다.
N=12을 예시로 코드에 출력값도 넣어놨는데, 분수배열을 오른쪽 45도 회전하여 피라미드 형태로 생각했을 때, 첫번째 줄에는 '1/1'로 요소가 1개 , 두번째 줄에는 '2/1','1/2' 로 요소가 2개, ··· 즉 a 번째 줄에는 a개의 요소가 존재한다.
따라서 N번째의 분수가 어느 줄에 포함되는지 알기 위해서는 각 줄의 요소합을 구하면서 그 합이 N보다 같거나 커지는 줄을 구하면 된다.
코드상으로는 add 를 요소의 수, i를 각 줄의 순서로 설정해두었다.
12번째 분수 '4/2' 은 5번째 줄에 존재 한다. (i = 5)
여기서 규칙을 발견할 수 있는데,
- i 가 짝수일 경우
- 분자는 i에서 1씩 감소하고, 분모는 1에서 1씩 증가한다
- i가 홀수일 경우
- 분자는 1에서 1씩 증가하고, 분모는 i에서 1씩 감소한다
따라서 N = 12 일 때, i는 홀수, 필요한 요소의 개수(add)는 15 이므로
분자 = 1+(15-12)
분모 = 5-(15-12)
📍 2775 (부녀회장이 될거야)
2775번: 부녀회장이 될테야
첫 번째 줄에 Test case의 수 T가 주어진다. 그리고 각각의 케이스마다 입력으로 첫 번째 줄에 정수 k, 두 번째 줄에 정수 n이 주어진다
www.acmicpc.net
T = int(input())
for _ in range(T):
k = int(input())
n = int(input())
# 층별 각 호수 거주 인원 담기 위한 0 배열 apart 생성
apart = [[0 for _ in range(n)] for _ in range(k)]
# 0층의 인원은 1,2,3,4.... 형태로 미리 저장해두기
for j in range(n):
apart[0][j] = j+1
# 1층부터 거주 필요한 인원 계산
for i in range(1,len(apart)):
for j in range(len(apart[i])):
# i층의 j호의 인원은 i-1층의 1호부터 j호까지의 인원 수 합
apart[i][j] = sum(apart[i-1][:j+1])
# k층n호에 거주하기 위한 k-1층의 1호부터 n호까지의 거주자 수
print(sum(apart[k-1][:n]))
💬 풀이 설명
문제를 읽고 그대로 구현하기만 하면 되는 문제라 어렵지는 않았는데,, 뭔가 코드를 더 간략하게 짤 수 있을 것 같았다.
그래서 다른 사람들의 풀이를 찾아보고 코드를 더 줄여보았다.
T = int(input())
for _ in range(T):
k = int(input())
n = int(input())
apart = [i for i in range(1,n+1)]
for _ in range(k):
for i in range(1,n):
apart[i] += apart[i-1]
# print(apart)
print(apart[-1])
처음 코드에서는 실제로 아파트 형태를 구현하기 위해 2차원 배열을 만들고 층별 각 호수의 인원을 입력하는 방식을 사용했다.
그러나 위의 코드처럼 굳이 2차원 배열을 만들지 않고, 0층 리스트를 생성한 뒤 반복문을 통해 층의 인원수를 계속 갱신해주는 방식도 있었다. 뭔가 더 마음에 드는 풀이다.. 유연한 사고가 중요한 것 같다.
'🏷️CS > Algorithm' 카테고리의 다른 글
[코테 스터디] 1주차 : 자료구조 / 이진탐색 (1) | 2024.06.10 |
---|---|
[백준] 1966 (프린터 큐) (2) | 2023.07.26 |
[백준] 구현 1157 / 4673 / 1316 (0) | 2023.05.09 |
코테에 사용하기 좋은 라이브러리 기능 (0) | 2023.04.30 |
시간 복잡도 (0) | 2023.04.27 |