[C] 백준 - 10799번: 쇠막대기

7월 25일(화) - 자료 구조 (10799번)

10799번: 쇠막대기

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

 

최초 생각 정리

- 괄호의 열고 닫음의 짝을 이용해서, 이전에 입력받았던 괄호의 성격에 따라서 조건을 나누어서 체크해야한다

- 따라서 스택을 활용한 풀이를 예상

 

- 입력은 string을 받은 뒤, for문을 string의 크기만큼 돌려준다

- for문안에서는

  1) 입력받은 string[ i ]가

      ' ( '인 경우와 아닌 경우

  2) 입력받은 string[ i ]가 ' ( '가 아니라면, 가장 최근에 입력받아서 top에 저장되어있는 stack[ top ]이

      ' ( '인 경우와 아닌 경우로 나눈다

- 최종출력은 쇠막대기의 수의 누적합을 더해놓은 count를 출력한다

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

 

문제점

1. 풀이를 진행하고나니 스택을 굳이 활용하지 않고도 풀이가 가능할 것 같았고, 찾아보니 실제로 가능

-> 스택을 활용하지 않고 풀이하는 방법도 원리는 같지만, 알아놓도록 해야할 것

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

 

풀이 - 1

1-1) 입력받은 string[ i ]가 ' ( '인 경우 -> 스택에 string[ i ]를 push 해준 뒤, 일단 쇠막대기의 수인 변수 stick++

1-2) 입력받은 string[ i ]가 ' ( '가 아닌 경우 == 즉 ' ) '가 입력된 경우

      2-1) top에 저장되어있는 stack[ top ]이 ' ( '인 경우

              -> 레이저이다.

              -> 따라서 stick--

              -> 그리고 최종출력변수인 count에다가 stick의 수를 누적합으로 더해준다

              -> 마지막으로 스택에 string[ i ]를 push 해준다

      2-2) top에 저장되어있는 stack[ top ]이 ' ( ' 가 아닌 경우

              -> 쇠막대기이다. 정확히 말하자면 쇠막대기의 끝이다

              -> 따라서 stick--

              -> 그리고 최종출력변수인 count++

#define _CRT_SECURE_NO_WARNINGS
#pragma warning(disable: 4996)

#include <stdio.h>
#include <string.h>

char string[100001];
int stack[100001];
int top = -1;

int is_full()
{
	if (top >= 100000 - 1)
	{
		return 1;
	}
	else
	{
		return 0;
	}
}

int is_empty()
{
	if (top < 0)
	{
		return 1;
	}
	else
	{
		return 0;
	}
}

void push(char x)
{
	if (is_full() == 0)
	{
		stack[++top] = x;
	}
}

char pop()
{
	if (is_empty() == 0)
	{
		return (stack[top--]);
	}
}

int main(void)
{
	scanf("%s", string);
	int count = 0;
	int stick = 0;

	for (int i = 0; i < strlen(string); i++)
	{
		if (string[i] == '(')
		{
			push(string[i]);
			stick++;
		}

		else
		{
			if (stack[top] == '(')
			{
				stick--;
				count = count + stick;
				push(string[i]);
			}

			else
			{
				stick--;
				count++;
			}
		}
	}

	printf("%d", count);
	return 0;
}

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

 

풀이 - 2

(풀이출처 -> https://zz12345.tistory.com/5)

#define _CRT_SECURE_NO_WARNINGS
#pragma warning(disable: 4996)

#include <stdio.h>
#include <string.h>

char string[100001];

int main(void)
{
	scanf("%s", string);
	int count = 0;
	int stick = 0;

	for (int i = 0; i < strlen(string); i++)
	{
		if (string[i] == '(')
		{
			stick++;
		}

		else if (string[i] == ')')
		{
			stick--;
			
			if (string[i - 1] != string[i])
			{
				count = count + stick;
			}
			if (string[i] == string[i + 1])
			{
				count = count + 1;
			}
		}
	}

	printf("%d", count);
	return 0;
}

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ