백준(BOJ) 문제 풀이

[브루트 포스]

 

1018: 체스판 다시 칠하기

from sys import stdin
input = stdin.readline

n, m = map(int, input().split())

chessTable = []
for i in range(n):
  s = input().rstrip()
  chessTable.append(list(s))
  # list(map(~~)) 이대로 입력 받으니까 문자열 자체가 한개의 요소라서 개별문자 접근이 안됨

def paint_chessTable(arr, y, x):
  
  s1 = "WBWBWBWB" # 번갈아가면서 확인해야함
  s2 = "BWBWBWBW"
  cnt = 0
  for i in range(y, y + 8):
    idx = 0
    for j in range(x, x + 8):
      if i % 2 == 0:
        if arr[i][j] != s1[idx]:
          cnt += 1
      else:
        if arr[i][j] != s2[idx]:
          cnt += 1
      idx += 1

  return min(cnt, 64-cnt) # 반대 경우의 수 : 최대 경우의 수(64) - 현재 경우의 수

answer = n * m # 최악의 경우에도 32는 넘지 않지만 대충 크게 넣음

for i in range(n):
  for j in range(m):
    # 인덱스가 넘지않는 범위 내의 8x8
    if i + 8 <= n and j + 8 <= m:
      answer = min(answer, paint_chessTable(chessTable, i, j))

print(answer)

구현하는데 시간이 너무 오래걸림

 

[자료구조]

 

1021: 회전하는 큐

#include <iostream>
#include <deque>
#include <algorithm>

using namespace std;

int main(void)
{
	ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);

	int n, m;
	int answer = 0;

	deque<int> rq;
	deque<int> nums;

	cin >> n >> m;

	for (int i = 0; i < m; ++i)
	{
		int data;
		cin >> data;
		nums.push_back(data);
	}

	for (int i = 1; i <= n; ++i)
	{
		rq.push_back(i);
	}

	for (auto& num : nums)
	{
		int idx = find(rq.begin(), rq.end(), num) - rq.begin();
		while (num != rq.front())
		{
			// 왼쪽으로 밀기
			if (idx < (int)rq.size() - idx)
			{
				rq.push_back(rq.front());
				rq.pop_front();
			}
			else
			{
				rq.push_front(rq.back());
				rq.pop_back();
			}
			answer++;
		}
		rq.pop_front();
	}

	cout << answer;

	return 0;
}

 

1269: 대칭 차집합

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main(void)
{
	ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);

	int n, m, data, v_size;
	vector<int> v1, v2;

	cin >> n >> m;

	v_size = n > m ? n : m;

	while (n--)
	{
		cin >> data;
		v1.push_back(data);
	}	
	while (m--)
	{
		cin >> data;
		v2.push_back(data);
	}

	sort(v1.begin(), v1.end());
	sort(v2.begin(), v2.end());

	vector<int> v3(v_size);

	// find에서 begin을 빼주면 index를 구할수 있는걸 응용함
	// 두 집합 결과의 다음 iterator가 반환되기때문에 begin을 빼주면 원소의 개수가 된다
	auto ans1 = set_difference(v1.begin(), v1.end(), v2.begin(), v2.end(), v3.begin()) - v3.begin();
	auto ans2 = set_difference(v2.begin(), v2.end(), v1.begin(), v1.end(), v3.begin()) - v3.begin();

	cout << ans1 + ans2 << '\n';

	return 0;
}

 

다른사람 풀이(46781878)는 이진 탐색으로 교집합 되는 원소의 개수(C)를 구한 뒤 N+M-(2*C)로 정답처리를 받았다.

 

 

[정렬]

 

2108: 통계학

from sys import stdin
from collections import Counter
input = stdin.readline

n = int(input())

arr = []
arr_sum = 0
for i in range(n):
  data = int(input())
  arr_sum += data
  arr.append(data)

arr.sort()
d = sorted(dict(Counter(arr)).items(), key=lambda x:(-x[1],x[0]))
# 더 심플하게 수정가능. d = Counter(arr).most_common(2)

print(round(arr_sum/n)) # 산술 평균
print(arr[n//2]) # 중앙값
if d[0][1] == d[1%n][1]: # 최빈값
  print(d[1%n][0])
else:
  print(d[0][0])
print(abs(arr[0] - arr[-1])) # 최대-최소 차이

Counter 처음써봤다. 다른사람 소스 보고 most_common의 존재를 알아서 다행임

 

1427: 소트인사이드

from sys import stdin
input = stdin.readline

# 문자열로 받아서
n = input().rstrip()

arr = []
for i in range(len(n)):
  # 숫자로 쪼개 넣은뒤
  arr.append(int(n[i]))

# 내림차순 정렬
arr.sort(reverse=True)

for i in arr:
  print(i, end='')

 

18870: 좌표 압축

#include <iostream>
#include <vector>
#include <algorithm>

#define horizon first
#define index second

using namespace std;

bool cmp_horizon(pair<int, int>& v1, pair<int, int>& v2)
{
	return v1.horizon < v2.horizon;
}

bool cmp_index(pair<int, int>& v1, pair<int, int>& v2)
{
	return v1.index < v2.index;
}

int main(void)
{
	ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);

	vector<pair<int, int>> coordinates;
	int n;

	cin >> n;

	for (int i = 0; i < n; ++i)
	{
		int t;
		cin >> t;
		coordinates.push_back({ t, i });
	}

	sort(coordinates.begin(), coordinates.end(), cmp_horizon);
    // [](auto& v1, auto& v2) { return v1.horizon < v2.horizon; }); 람다식 가능

	int idx = 0;

	for (int i = 0; i < n - 1; ++i)
	{
		if (coordinates[i].horizon == coordinates[i + 1].horizon)
		{
			coordinates[i].horizon = idx;
		}
		else
		{
			coordinates[i].horizon = idx++;
		}
	}
	coordinates[n - 1].horizon = idx;

	sort(coordinates.begin(), coordinates.end(), cmp_index);
    // [](auto& v1, auto& v2) { return v1.index < v2.index; }); 람다식 가능

	for (auto& data : coordinates)
	{
		cout << data.horizon << " ";
	}

	return 0;
}

 

cmp_horizon, cmp_index 대신에 람다식을 넣어서 더 짧게 할수도 있다.

다른사람 풀이(46641944) 중에 페어를 쓰지 않고 unique와 lower_bound(=bisect_left)를 이용해서 간결하게 풀어낸 해답이 있다.

 

1764: 듣보잡

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int main(void)
{
	ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);

	vector<string> cant_hear;
	vector<string> cant_see;
	int n, m;
	string s;

	cin >> n >> m;

	while (n--)
	{
		cin >> s;
		cant_hear.push_back(s);
	}
	while (m--)
	{
		cin >> s;
		cant_see.push_back(s);
	}

	// intersection 수행 전 모두 정렬이 되어있어야 함
	sort(cant_hear.begin(), cant_hear.end());
	sort(cant_see.begin(), cant_see.end());

	vector<string> cant_hear_see(cant_hear.size() + cant_see.size());

	// 두 집합 결과의 end iterator가 반환됨
	auto iter = set_intersection(cant_hear.begin(), cant_hear.end(),
    			cant_see.begin(), cant_see.end(), cant_hear_see.begin());
	// 해당 iterator부터 새 컨테이너의 end까지 삭제를 해주면 잉여 크기가 삭제된다
    cant_hear_see.erase(iter, cant_hear_see.end());

	cout << cant_hear_see.size() << '\n';
	for (auto& item : cant_hear_see)
	{
		cout << item << '\n';
	}

	return 0;
}

 

set의 find 또는 algorithm의 find를 이용하면 intersection을 사용하지 않으므로 컨테이너를 추가로 쓰지 않아도 돼서 메모리를 아낄 수 있다. 코드 가독성도 더 좋아질 것 같다.

 

[수학]

 

9020: 골드바흐의 추측

from sys import stdin
input = stdin.readline

primeNumber = [1] * 10001

# 에라토스테네스의 체
# n의 최대약수는 sqrt(n) 이하이므로 제곱근+1 까지만 루프를 돈다
for i in range(2, int(10000**0.5)+1):
  if primeNumber[i] == 1:
    for j in range(i*2, 10001, i):
      primeNumber[j] = 0

def goldbach_partition(n):
  # (n/2-a) + (n/2+a) = n
  for i in range(n//2, 0, -1):
    # 차이가 가장 적은 소수판별
    if primeNumber[i] == 1 and primeNumber[n - i] == 1:
      print(i, n-i)
      return
  
for tc in range(int(input())):
  goldbach_partition(int(input()))

 

처음엔 이중 for문으로 썼다가 당연히 시간초과가 났다. 머리 싸매고 고민해도 답이 안나오길래 질문 게시판에서 힌트란 힌트는 다 훑어보고 난 뒤에서야 수정했다.

어떤 짝수를 두 소수의 합으로 나타낼 수 있다는거 이제 잊고싶어도 못잊을거같다.

 

 

[그리디]

 

1931: 회의실 배정

n = int(input())

array = [0] * n

for i in range(n):
  array[i] = tuple(map(int, input().split()))

array.sort(key = lambda x: (x[1], x[0]))

end, result = -1, 0

for i in range(n):
  # 현재 진행중인 회의의 종료시간보다 뒤에 있으면서 end가 짧은거 하나만 하면 됨
  # 두가지 조건을 만족해야 하지만 이미 end가 짧은순으로 정렬되어 있기때문에
  # 종료시간 뒤에 있는 가장 가까운 값을 꺼내오기만 하면 end가 짧은게 보장됨
  if array[i][0] >= end:
    end = array[i][1] # 종료시간 갱신
    result += 1

print(result)

얼마전에 공부 했던 내용인데 최적해를 구하는게 한끗차이로 안떠올라서 시간을 좀 잡아먹었다

코드업 4713 이랑 동일한 문제라고 생각해서 코드를 길게 짜다가 조건자체가 더 심플해서 간소화시켰다

근데 지금 생각해보니 코드업 4713도 간소화 시킬수 있을것같은데 일단 보류함

 

1946: 신입 사원

from sys import stdin

t = int(stdin.readline())

for ft in range(t):
  n = int(stdin.readline())
  arr = [0] * n
  
  for i in range(n):
    arr[i] = tuple(map(int, stdin.readline().split()))

  # 첫번째 값 기준으로 오름차순 정렬
  arr.sort() 

  # 1등의 두번째 값을 기준으로 잡고 1등은 무조건 통과이므로 1부터 시작 
  result = 1
  pivot = arr[0][1]
  
  for i in range(1, n):
    if arr[i][1] < pivot:
      result += 1
      pivot = arr[i][1]
      
  print(result)

난이도가 높지 않은 문제는 최적해 구하는 방법에 접근은 잘 하는데 시간이 너무 오래걸린다

그리고 구현할 때 더 단순한 방법이 있음에도 자꾸 어렵게 함

 

 

11501: 주식

 

# n일보다 n+1일이 크거나 같으면 구매함
# n일보다 n+1이 작으면 판매함

from sys import stdin

t = int(stdin.readline())

for ft in range(t):
  n = int(stdin.readline())
  arr = [x for x in list(map(int, stdin.readline().split()))]

  stock = 0
  result = 0
  highest = max(arr)
  
  for i in range(n-1):
    if arr[i] <= arr[i+1]:
      stock += 1
      result -= arr[i]
    # 다음날 가격이 떨어지지만 최고가를 만나지 않았으면 팔지 않음
    elif arr[i] > arr[i+1] and arr[i] >= highest:
      result += (arr[i] * stock)
      highest = max(arr[i+1:]) # 최고가 재설정
      stock = 0
    # 전일 등락과 상관없이 최고가를 만나기 전까지는 매수
    else:
      stock += 1
      result -= arr[i]
  # 루프를 한번 덜돌기때문에 마지막날에 대한 결과 처리
  result += (highest * stock)

  print(result)

시간이 9초가 나왔다... 루프 자체는 O(N)인데 아무래도 max를 부르는 횟수가 많아지면 기하급수적으로 늘어나는것 같음

처음 제출했을때 틀리길래 반례를 찾아서 다시 조립했다. 최고가 갱신쪽이 문제였다

2초대가 나온 다른사람 코드를 봤는데 심플했다. 읽어보니 접근 방법은 이해했는데 그런 코드를 작성할 수 있다는게 신기함

 

4796: 캠핑

count = 1

while True:
  l, p, v = map(int, input().split())

  if l + p + v == 0:
    break
    
  answer = 0
  
  while v >= l:
    v -= p
    answer += l
    
  if v > 0:
    answer += v

  print("Case "+str(count)+": "+str(answer))
  count += 1

코드 짧게 짜놔서 뿌듯했는데 자꾸 오답나길래 보니까 예제출력이랑 동일하게 하는 부분을 처리 안해서 그랬었음

 

[BFS]