[백준알고리즘] 10799번: 쇠막대기 -Python, C++

[백준알고리즘] 10799번: 쇠막대기 -Python, C++

10799번: 쇠막대기 (acmicpc.net)

10799번: 쇠막대기

잘못된 점이나 부족한 점 지적해주시면 감사하겠습니다

 

예전에 파이썬으로 풀었다가 쉬웠어서 안올렸던 문제다.

 

그런데.. 오늘 C++로 풀면서 완전 대참사였다. 계속 '틀렸습니다'가 떠서 이전에 파이썬으로 푼 코드를 봤는데 로직이 같은 개념으로 짠 것인데도 해결이 안 됐다. 이래저래 모두 안되길래 아예 파이썬으로 짰던 로직 그대로 짰는데도 안됐다.

 

그래서 오늘 C++로 짠 코드는 결국 같이 풀이에 나섰던 친구의 힌트 덕분에 새로운 접근법으로 문제를 풀었다.

 

이번 포스팅에서는 예전에 파이썬으로 풀었던 풀이방법과 오늘 C++로 풀었던 서로 다른 두 접근 방법에 대해 모두 적어보려고 한다.

(마지막에는 파이썬 로직처럼 짠 실패한 C++ 코드를 삽입했는데 반례 있으신 분, 왜 안되는지 아시는 분은 도움 좀 부탁드려요 ㅠㅠ)

---

레이저 개수를 기준으로 풀이

이 방법으로는 Python으로 예전에 풀었다. 

 

레이저를 기준으로 조각을 셌다는 것은 아래의 그림을 통해 설명해보겠다.

 

레이저 기준 예시

• 빨간색 영역인 쇠막대는 레이저 2개에 의해 3조각으로 나뉘어졌다.
• 파란색 영역인 쇠막대는 레이저 1개에 의해 2조각으로 나뉘어졌다.
• 초록색 영역인 쇠막대는 레이저 4개에 의해 5조각으로 나뉘어졌다. 
• ...

이와 같이 막대가 나왔을 때 레이저가 중간에 몇 개가 있는지를 계산함으로써 모든 조각의 수를 찾는 방법이다. 따라서 레이저 개수에 집중해서 막대의 오른쪽 끝이 나왔을 때 왼쪽 끝 사이에 몇 개의 레이저가 존재하는지 알아야 한다.

 

따라서 스택에는 '(' 외에 레이저 개수를 포함시켜 넣는다. (')'는 사실상 스택에 포함되지 않아도 되기 때문)

 

')'가 삽입될 때 직전이 '('라면, 새로운 레이저가 한 개 추가되는 것이다. 반면 ')'가 삽입될 때 직전이 '('가 아니라 레이저의 수라면, 이것은 쇠막대의 오른쪽 끝을 나타내는 것이기 때문에 왼쪽 끝인 '('가 나오기 이전까지의 모든 레이저의 개수 를 구한다. 이 쇠막대의 조각은 항상 '레이저의 개수 + 1'만큼 생긴다.

 

이러한 접근법으로 문제를 풀었고, 아래는 Python으로 통과했던 코드다. 예전에 푼 만큼 지금 봤을 때 코드가 지저분해보인다.. 하나도 안 이뻐보이고..

C++로 오늘 짰지만, 틀렸다고 뜬 코드는 맨 아래에 있다. 물론, 틀렸지만 로직 자체는 유사하기 때문에 두 코드를 보고 접근법을 이해하면 될 것 같다. C++은 제발 왜 틀렸는지 알고 싶다..

status = input().rstrip()
stack = [0]
ans = 0
for s in status:
    if s == ')':
        if stack[-1] == '(':
            stack.pop()
            if stack[-1] == '(':
                stack.append(1)
            else:
                stack.append(stack.pop()+1)
        else:
            t = stack.pop()
            stack.pop()
            ans += t+1
            if stack[-1] == '(':
                stack.append(t)
            else:
                stack.append(stack.pop()+t)
    else:
        stack.append(s)
print(ans)

---

레이저에 닿는 쇠막대의 개수를 기준으로 풀이

이 방법은 오늘 친구의 힌트를 통해 새로운 접근법으로 풀었던 방법이다. C++로 풀었다.

 

레이저에 닿는 쇠막대의 개수를 기준으로 한다는 말 역시 아래의 그림을 통해 설명하도록 하겠다.

잘리는 쇠막대 기준 예시

• 빨간색 영역인 두 번째 레이저에 닿기 전, 쇠막대는 세 개가 존재한다.
• 파란색 영역인 세 번째 레이저에 닿기 전, 쇠막대는 세 개가 존재한다.
• 초록색 영역인 네 번째 레이저에 닿기 전, 쇠막대는 세 개가 존재하며 한개의 쇠막대는 이 레이저에 닿기 전에 끝나서 쇠막대 한개가 추가로 생겼다.
• ...

위의 그림에서 레이저가 식별되기 전까지 얼마나 많은 쇠막대가 존재하고 있었는 가에 대해 개수를 세가면 된다. 끊기지 않고 존재하는 쇠막대의 개수만큼 레이저가 토막을 내기 때문이다.

 

하지만 초록색 영역에서와 마찬가지로 레이저를 닿기 전에 길이가 끝난 쇠막대는 따로 개수를 세어줘야 한다.

 

이러한 방법을 사용하기 위해 이번에는 '('만 스택에 들어간다. ')'는 사실상 들어갈 필요가 없고, 레이저의 개수를 카운팅할 필요가 없기 때문이다.

 

기본적으로 ')'가 들어오면, 직전이 '('일 경우에는 레이저기 때문에 레이저의 '('를 제외한 스택에 들어간 '('의 총 개수를 구하면, 새롭게 생기는 토막의 개수가 된다. 

추가적으로 중간에 길이가 끊기는 경우는 ')'가 들어왔을 때 직전이 '('가 아닌 ')'이다. 따라서 이 경우에는 막대가 레이저에 닿기 전 길이가 끝난 것이기 때문에 하나씩 카운팅해준다.

 

아래는 이러한 방법으로 푼 C++ 코드다.

#include <iostream>
#include <vector>

const char left = '(';
const char right = ')';

void solve(void);

int main(void)
{
	std::ios::sync_with_stdio(false);
	std::cin.tie(NULL);

	solve();
}

void solve(void)
{
	std::string line;
	std::cin >> line;
	
	int total_stick = 0;
	std::vector<char> stack;
	for (int i = 0; i < line.size(); i++)
	{
		if (left == line[i])
		{
			stack.push_back(line[i]);
			continue;
		}

		stack.pop_back();
		total_stick += ((left == line[i - 1]) ? stack.size() : 1);
	}

	std::cout << total_stick;
}

---

마지막으로 오늘 첫 번째 파이썬 로직과 유사하게 짰던 C++ 코드다. 

반례가 있으시거나.. 틀린 부분을 아시는 부분은 알려주시면 감사드리곘습니다..

 

#include <iostream>
#include <vector>

const char left = '(';
const char right = ')';

void solve(void);

int main(void)
{
	std::ios::sync_with_stdio(false);
	std::cin.tie(NULL);

	solve();
}

void solve(void)
{
	std::string line;
	std::cin >> line;

	std::vector<char> stack;
	int total_stick = 0;
	for (int i = 0; i < line.size(); i++)
	{
		if (left == line[i])
		{
			stack.push_back(line[i]);
			continue;
		}

		int razer = 0;
		while (left != stack.back())
		{
			razer += (stack.back() - '0');
			stack.pop_back();
		}

		stack.pop_back();
		if (razer)
			total_stick += (razer + 1);
		stack.push_back(razer ? '0' + razer : '1');
	}

	std::cout << total_stick;
}