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

문제 풀이

딱히 시간 복잡도나 공간 복잡도를 고려할 필요도 없이 단순한 사칙연산만 하면 충분히 통과 가능한 브론즈 문제인데 생각보다 정답 비율이 엄청 낮아서 포스팅하기로 했다.

브론즈 문제가 약 27%의 낮은 정답률을 보인다는 것은 난이도 설정이 잘못되었거나 문제에 헷갈릴만한 요소가 있어서 잘못된 방향으로 제출하여 많은 오답을 기록하기 때문이라 생각한다.

그래서 필자가 추측컨대 아마 감독관 수의 최솟값을 구해야 하는 문제에서 "총감독관은 오직 1명만 있어야 하고" 란 지문이 오히려 헷갈리게 했을 가능성이 있는 것 같다.

이 말이 총감독관은 2명 이상 있으면 안 된다고 판단하여 "0명도 가능하지 않나?" 란 생각이 들게 할 수 있는 것 같다.

따라서 "총감독관은 반드시 1명 있어야 하고" 로 바뀌었으면 단번에 맞춰서 정답 비율이 더 높진 않았을까 하는 아쉬움이 남았다.

또한 이 문제에 대해 시간 초과가 뜨는 경우가 종종 있던데 시험장의 수와 응시자의 수가 최대 100만이므로 수학 연산으로 답을 도출해야지 반복문을 통해 일일이 빼는 경우엔 절대 2초 안에 연산이 불가능하다는 것을 생각해야 한다.

방향성만 제대로 잡는다면 상당히 쉬운 문제라 서론이 길었는데 전체 코드를 통해 설명하도록 하겠다.

n=int(input())
n_cnt=list(map(int,input().split()))
b,c=map(int,input().split())
res=0
for i in range(n):
    n_cnt[i]-=b
    res+=1
    if n_cnt[i]>0:
        if n_cnt[i]%c==0:
            res+=(n_cnt[i]//c)
        else:
            res+=(n_cnt[i]//c+1)

print(res)

난이도 답게 상당히 짧고 간결한 코드가 나왔다.

4번째 줄까지는 필요한 입력을 받고 정답으로 출력할 변수를 초기화하는 코드다.

5번째 줄에서 for문으로 전체 시험장을 반복하며 반드시 총감독관이 있어야 하기에 총감독관이 감시할 수 있는 응시자 수를 빼고 res 변수를 카운트했다.

그 뒤에 만약 남은 응시자 수가 부감독관이 감시할 수 있는 응시자 수의 배수라면 나눈 몫을 카운트했고 배수가 아니라면 몫과 더불어 1만큼 더 큰 숫자를 카운트했다.

그 뒤에 카운트 한 숫자만큼 출력하면 통과할 수 있다.

단순 사칙연산 문제로 아주 쉬운 편이었지만 헷갈릴 수 있는 부분이 있어 입력과 출력 예제를 유심히 봐야 하는 문제였다.

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

문제 풀이

브론즈 문제 치고 정답 비율이 24%로 엄청 낮은 통계였다.

왜 그런가 싶어서 문제를 자세히 봤더니 아마 생각난 방식 그대로 제출한다면 시간 초과가 날 것 같단 생각이 들었다.

문제 자체는 단순하게 데이터의 개수만큼 컴퓨터 대수인 10개를 나눈 나머지를 출력하고 0만 10으로 변환하면 되는데 여기서 문제는 데이터의 개수가 a^b 만큼 들어오고 a는 100 미만, b는 1000000 미만의 자연수이므로 총 100000000(1억) 개의 데이터가 될 수 있으며 심지어 테스트 케이스도 입력받기 때문에 단순하게 제곱수를 통한 구현은 시간 초과가 날 가능성이 높았기 때문이다.

혹시나 해서 그대로 구현하여 제출했더니 역시 시간 초과가 났다.

n=int(input())
for i in range(n):
    a,b=map(int,input().split())
    print(a**b%10)

따라서 시간을 줄일 수 있는 방식을 생각해야 했고 일의 자리가 나올 수 있는 숫자들을 구해서 해당 개수만큼 나눈다면 어느 정도 정답에 근접할 것이라 생각했다.

다음은 통과한 전체 코드이다.

n=int(input())
for i in range(n):
    a,b=map(int,input().split())
    if a==1:
        print(1)
    else:
        last=a%10
        last_num=[last]
        sum_last=(last**2)%10
        while sum_last not in last_num:
            last_num.append(sum_last)
            sum_last=(sum_last*last)%10
        if last_num[(b-1)%len(last_num)]==0:
            print(10)
        else:
            print(last_num[(b-1)%len(last_num)])

먼저 4번째 줄에서 if문을 쓴 이유는 a가 1이라면 b가 어떤 숫자가 나와도 데이터 개수는 1개이므로 무조건 1이 나올 수밖에 없기 때문에 처리했다.

a가 1이 아닌 나머지의 경우엔 일의 자리를 구해서 리스트에 저장하고 동일한 숫자가 나오기 전까지 a를 곱하여 일의 자리를 계속해서 추가한다.

10으로 나누기 때문에 최대 10개가 나올 수 있으며 0은 10으로 치환해야 한다는 것을 잊으면 안 된다.

해당 반복문이 종료되면 인덱스는 0부터 시작하기 때문에 b-1을 last_num의 길이(일의 자리에 나올 수 있는 숫자들)로 나누고 해당 숫자가 0이면 10으로 치환, 아니면 해당 숫자를 출력하면 통과한다.

역시 구현 자체가 어려운 문제는 아니라 단순하게 생각해서 제출한 경우가 많아 정답 비율이 낮게 나온 것 같다.

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

문제 풀이

언어를 배우는 초기에 풀어볼 법한 아주 기초적인 문제라 포스팅하지 않으려 했지만 생각보다 정답 비율이 엄청 낮아서 작성하기로 했다.

단순하게 최솟값과 최댓값을 구하는 건 상당히 쉽다.

최솟값과 최댓값을 뜻하는 변수 두 개를 선언하고 전체 Data를 돌면서 각각 최솟값보다 작은 수가 나오면 갱신, 최댓값보다 큰 수가 나오면 갱신하면 끝이다.

이때 처음 변수 선언 시 팁이 될 수 있는 것은 최솟값 변수엔 가능한 최댓값보다 큰 값을, 최댓값 변수엔 가능한 최솟값보다 작은 값으로 초기화하는 것이다.

그래야 단 한 번이라도 갱신할 수 있으며 파이썬스럽게 선언하는 방법은 float('inf'), float('-inf') 이렇게 양의 무한대, 음의 무한대로 선언하는 것이다.

이걸 그대로 출력해도 inf, -inf로 나오기 때문에 편하게 무한대라 생각하면 된다.

문제를 푸는 코드는 먼저 C를 이용하여 앞서 설명한 방식대로 답을 구하는 방법과 파이썬의 함수를 이용하여 단 3줄로 구현하는 방법을 소개하겠다.

먼저 C 코드이다.

#include <stdio.h>
int main() {
	int a,b,min=1000000,max=-1000000;
	scanf("%d", &a);
	for (int i = 0; i < a; i++) {
		scanf("%d", &b);
    	if (min > b) {
            min = b;
        }
    	if (max < b) {
            max = b;
        }
	}
	printf("%d %d", min, max);
	return 0;
}

원소는 -1000000 이상, 1000000 이하로 제한되어 있으므로 3번째 줄에서 딱 맞게 초기화했다.

그리고 5번째 반복문에서 원소를 하나씩 입력받으며 입력받은 값이 최솟값 변수보다 작다면 갱신, 최댓값 변수보다 크다면 갱신하고 결괏값을 출력하면 된다.

그저 완전 탐색하면 풀리는 상당히 쉬운 문제다.

다음은 파이썬 코드이다.

n=int(input())
num_list=list(map(int,input().split()))
print(min(num_list),max(num_list))

단 3줄로 상당히 간단하게 풀었다.

2번째 줄의 map은 input으로 받은 문자열을 split을 통해 공백을 기준으로 분리하고 int로 형 변환하는 함수이다.

따라서 리스트로 형 변환하여 저장한 뒤 min함수를 통해 최솟값을, max함수를 통해 최댓값을 출력하면 된다.

각 함수 별로 데이터 전체를 탐색하기 때문에 O(n)의 시간 복잡도가 걸리는데 이걸 두 번 반복해도 충분히 시간 초과에 걸리지 않고 통과할 수 있다.

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

문제 풀이

2차원 그래프에서도 상당히 쉬운 편에 속하는 문제였다.

그림의 가로길이는 짝수이며 접었을 때 물감이 겹치는 부분도 없다고 하니 그냥 구간을 절반으로 나눠 물감이 있으면 반대편에도 추가하는 방식으로 풀면 되는 브론즈다운 문제였다.

상당히 쉬우니 바로 전체 코드로 넘어가겠다.

n,m=map(int,input().split())
graph=[]
for i in range(n):
    temp=list(input())
    for j in range(m//2):
        if temp[j]!='.':
            temp[m-j-1]=temp[j]
        elif temp[m-j-1]!='.':
            temp[j]=temp[m-j-1]
    graph.append(temp)
    
for i in range(len(graph)):
    for j in range(len(graph[i])):
        print(graph[i][j],end="")
    print()

각 줄을 입력받으면서 바로 물감을 갱신한 뒤 그래프에 추가하여 출력하는 방식으로 구현했다.

5번째 줄이 물감을 갱신하는 반복문이며 구간을 절반으로 나눠 6번째 줄은 첫 문자부터 절반 부분까지, 8번째 줄은 뒷 문자부터 절반 부분까지 물감이 있으면 반대편에 추가하고 완료되면 그래프에 추가했다.

그리고 완전 탐색을 통해 그래프 출력만 하면 되는 쉬운 문제였다.

만약에 인덱싱 부분이 헷갈린다면 작은 숫자를 몇 개 대입해보면 쉽게 해결할 수 있을 것이다.

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

문제 풀이

대문자 하나에 대응하는 소문자 문자열이 정해져 있으므로 Python의 딕셔너리를 사용하면 쉽게 해결할 수 있다.

대응하는 문자들을 딕셔너리에 저장하고 압축된 문자열이 들어왔을 때 차례대로 소문자 문자열로 치환하면 쉽게 풀 수 있는 문제다.

바로 전체 코드로 넘어가겠다.

n=int(input())
word={}
res=""
for i in range(n):
    temp=list(input().split())
    word[temp[1]]=temp[0]
question=input()

for i in question:
    res+=word[i]
num=list(map(int,input().split()))
print(res[num[0]-1:num[1]])

2번째 word는 딕셔너리를 선언했고 for문을 돌면서 입력받은 값을 저장하면 된다.

이때 주의해야 할 점은 압축된 문자열을 풀어야 하므로 입력받은 대문자를 딕셔너리의 키, 소문자 문자열 패턴을 딕셔너리의 값으로 저장해야 한다는 것이다.

res에 치환한 문자열을 저장하고 입력받은 인덱스를 기준으로 출력하면 쉽게 풀 수 있다.

인덱스로 범위 출력 시 왼쪽 인덱스는 포함, 오른쪽 인덱스는 미만까지 출력하는 점을 주의해야 한다.

https://www.acmicpc.net/contest/problem/725/1

문제 풀이

눈여겨봐야 할 조건은 3가지다.

1. 보이는 대로 읽어야 할 알파벳과 다르게 읽어야 할 알파벳이 구분되어있다.
2. 최대 100글자의 단어가 주어진다.
3. 영어 소문자로 나타내 출력해야 한다.

다르게 읽어야 할 알파벳은 다음과 같다.

B->v, E->ye, H->n, P->r, C->s, Y->u, X->h

해당 부분은 파이썬의 딕셔너리(Dictionary)를 사용하면 쉽게 치환 가능하다.

최대 100글자이므로 시간 복잡도는 고려할 필요가 없을 정도로 Input Size가 작다.

입력이 대문자로 들어오고 출력은 소문자로 해야 하므로 보이는 대로 읽어야 할 알파벳은 소문자로 치환시켜야 된다.

다음은 전체 코드이다.

word=input()
russ={"B":"v","E":"ye","H":"n","P":"r","C":"s","Y":"u","X":"h"}
res=""
for i in word:
    if i in russ:
        res+=russ[i]
    else:
        res+=i.lower()
print(res)

먼저 russ란 딕셔너리에 치환해야 될 알파벳들을 넣어 놓고 Input 문자열을 하나씩 반복한다.

만약 딕셔너리에 있는 문자라면 해당 값을 res에 이어 붙이고 없는 문자라면 lower() 함수를 이용하여 대문자를 소문자로 치환한 다음 이어 붙인다.

완성된 문자열을 출력하면 정답이다.

파이썬의 딕셔너리를 사용해야겠다는 생각만 떠올리면 복잡한 인덱싱 과정도 필요 없기에 쉽게 풀 수 있는 문제였다.