#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<vector>
#include<string>
using namespace std;

void GetNum(const string & str, vector<int> & numList)
{
	string element;
	for (const auto & data : str)
	{
		
		if (data == 43 || data == 45)
		{
			numList.push_back(stoi(element));
			element = data;
		}
		else element += data;
		
	}
	numList.push_back(stoi(element));
}

int main()
{
	string input;
	cin >> input;

	vector<int> numList;
	GetNum(input, numList);
	
	int result = 0;
	bool transSwitch = false;
	for (auto & data : numList)
	{
		if (data < 0) transSwitch = true;
		if (transSwitch == true && 0 < data) data *= -1;
		result += data;
	}

	cout << result;

	return 0;
}

내가 푼 코드는 이러하다.

그리디 유형에 속해 있어서 그리디적으로 생각해보려고 했다.

수식 맨 처음부터 읽으면서 당장 '-'가 나온다면 그 후에 나오는 +는 모두 -로 바꾸어 계산하였다

input을 하나하나 읽으면서 동시에 result로 계산하는 방법이 더 나았지만

길이제한없는 연속된 정수를 따로 저장해보고 싶어서 저장하는 함수를 따로 구현하였다.

근데 다른 사람이 푼 코드가 충격이였다

#include <stdio.h>

int main()
{
  char cmd;
  int n,s,m=0;
  for(scanf("%d",&s);scanf("%c",&cmd),cmd!=10;)
  {
    if(cmd=='-')m=1;
    scanf("%d",&n);
    if(m)s-=n;
    else s+=n;
  }
  printf("%d",s);
  return 0;
}

ㅋㅋㅋㅋ보면서 대단하다고 생각했다

다음에 기회가 된다면 응용해 봐야겠다

정말 만만하게 봐서 설계 대충 하다가 정말 오래 걸렸던 문제ㅠ

처음에는 정말 길게도 풀었다.

#include <bits/stdc++.h>

using namespace std;

void tokenizerTimeformat(vector<string> & time, bool & isAm, string & str)
{   
    string tempStr = str;
    const string delimiter = ":";
    size_t pos = 0;
    
    string tempdegit ="";
    for (int i = 0; i < str.length(); ++i)
    {
        if(isdigit(str[i]) == 0)
        {//is character not degit
            if(tempdegit.length() != 0)
            {
                time.push_back(tempdegit);
                tempdegit = "";
            }
        }
        else 
        {
            tempdegit += str[i];
        }
    }
    
    if (tempStr[8] == 'A') isAm = true;
    if (tempStr[8] == 'P') isAm = false;
}


string timeConversion(string s) 
{
    vector<string> time_s(0);
    vector<int> time_i(0);
    bool isAm = false;
    tokenizerTimeformat(time_s, isAm, s);
    cout<<"isAM : "<<isAm<<endl;

    for(auto data : time_s)
    {
        time_i.push_back(stoi(data));
    }

    if(isAm == false)
    {//isPM
        time_i[0] += 12;
        if (24 <= time_i[0])
        {
            time_i[0] -= 12;
        }
    }
    if(isAm == true)
    {
        if (12 <= time_i[0])
        {
            time_i[0] = 0;
        }
    }
    
    time_s[0] = to_string(time_i[0]);
    if(time_s[0].length() < 2)
    {
        time_s[0] = "0" + time_s[0];
    }
    
    return time_s[0] + ":" + time_s[1] + ":" + time_s[2];
}

int main()
{
    ofstream fout(getenv("OUTPUT_PATH"));

    string s;
    getline(cin, s);

    string result = timeConversion(s);

    fout << result << "\n";

    fout.close();

    return 0;
}

그러다가 scanf를 이렇게 사용할수도 있구나를 알게 돼서 적용하여 풀어보니까 정말 쉽게 풀렸다 =~=

규칙 있는 문자열을 입력받아 나눌 때 편하게 사용할 수 있을 것 같다.

#include <bits/stdc++.h>

using namespace std;

int main()
{
   int h, m ,s;
   char c;
   scanf("%d:%d:%d%c",&h ,&m ,&s, &c);
   
   if(c == 'A' && h == 12)
   {
       h = 0;
   }
   if(c == 'P')
   {
       if (h < 12) h += 12;
   }

   printf("%02d:%02d:%02d",h,m,s);
   return 0;
}

개요

스택 알고리즘 풀이 하는 김에 좀 더 공부해봤다.

개념

불연속적인 메모리로 Last in first out 을 가진다.

[Top of pointer을 가지고있음]

구현

array형식으로도 구현가능하고 linked list로도 구현 가능하여 각 장,단점을 생각해 보았다.

array로 구현시

● 추가 메모리가 요구 되지 않는다.

● 먼저 array의 강력한 장점인 인덱스로 값을 찾는것이 stack에서는 그렇게 필요하지 않다고 느꼈다

어차피 맨 위의 데이터만 사용하려고 하는 것이기 때문이다.

● 크기에 대한 번거로운 과정이 있을 것이다(새로 할당받고 복사하고 원 메모리 반환)

그에 딸려오는 단편화 문제

Linked list로 구현시

● 임의의 위치에 데이터를 추가,삭제 하는 기능이 없기 때문에 이러한 장점을 살릴 수 없다.

● 크기에 제약이 없다!

● 옆의 노드의 주소를 저장 할 공간이 추가 요구 됨

● 맨 위의 데이터만을 참고 한다는 스택의 특징이 랜덤 액세스가 불가능한 연결리스트의 단점을 커버 해줌

나는 무난한 배열로 구현을 해보겠다.

생성 & 소멸 & 멤버 변수

#include <iostream>
using namespace std;
#define INIT_STACK_SIZE 10

template<typename T>
class Stack
{
public:

	Stack()
	{
		data = new T[INIT_STACK_SIZE];
		capacity = INIT_STACK_SIZE;
		topIndex = -1;
	}
	~Stack()
	{
		delete[] data;
		data = nullptr;
	}
    
    
/************생략************/
                                        

private:
	//스택에 넣을 데이터를 담을 포인터 형
	T * data;
	//맨 위의 인덱스
	int topIndex;
	//스택의 총 메모리 양
	int capacity;
};

데이터 삽입 (Push)

	void Push(T input)
	{
		++topIndex;
		if (capacity <= topIndex)
		{
			T * temp = new T[capacity * 2];
			memcpy(temp, data, sizeof(int) * capacity);
			delete[] data;
			data = temp;
			capacity *= 2;
		}
		data[topIndex] = input;
	}

배열이기 때문에 크기에 대한 처리를 따로 해주었다.

데이터 삭제 (Pop)

	void Pop()
	{
		if (IsEmpty() == true) return;
		--topIndex;
	}

맨 위의 데이터 꺼내기 (Top)

	T Top()
	{
		if (IsEmpty() == true) return -1;
		return data[topIndex];
	}

여기서 예외설정을 안해서 알고리즘에서 틀렸었다 😂

사용처

맨 위의 데이터를 다룬다는 것에 대하여 게임의 네비게이션에서 사용 할 수 있을거 같다.

이는 여태 시도하는 경로를 스택에 쌓아둠과 동시에 틀릴 경우 맨위부터 다시 돌아가 다른 경로를 탐색함에 있어서

LIFO인 스택과 같아 잘 맞는다.

[나중에 깊이 우선 탐색이라는 알고리즘이 이와 같다고한다?]

또한 상점에서 거래를 이전으로 돌리는 기능을 구현 할 수 있을 것 같다.(ctrl + z 처럼)

롤에서 상점에서 구매했던 것이나 팔았던 행위를 되돌릴 수 있는 것처럼!

또 다른 이용은 아직 데이터를 뒤집을때 편할듯 하다.

스택 프레임이란 개념도 있는데

함수가 호출될 때, 그 함수만의 스택 영역을 구분하기 위하여 생성되는 공간이라 한다.

그렇기에 함수 호출시에 생성되고 함수가 종료되면서 소멸한다.

이 공간에는 함수와 관계되는 지역 변수가 저장된다고 한다.

암튼 그렇다 ㅋㅋ

특징

노드 컨테이너로 이루어져 있다

탐색의 경우 처음부터 끝까지 하나씩 탐색해야하기 때문에 O(n)

=>인덱스를 지원하기 하지 않기 때문에 랜덤한 접근이 불가능하다

데이터의 어느곳이든지 삽입 삭제가 빠르다 O(1)

=>순서 변경도 마찬가지

컨테이너의 크기가 고정이 아닌 동적으로 이루어진다

근데 이 또한 vector처럼 동적할당으로 이루어지는데

자주 크기가 조정 될 시에 메모리단편화라는 단점이 거론되지 않는가 궁금했다.

추측인데 vector는 데이터가 메모리에 연속적으로 있어야 하지만

List는 각 데이터 하나 하나가 꼭 붙어 있지 않아도 되기에 미리 나누어져있는 메모리를 할당받을 확률이 높다고 생각한다.

※캐시라인이라는 개념으로 vector와 비교되는데 나중에 다시 찾아보기

결론

연결 리스트도 vector와 마찬가지로 가변성이 가장 큰 특징이라 생각이 들어

vector와 차이를 많이 못느꼈었는데

어느곳에서나 데이터의 삽입 삭제에 빠르며 메모리의 크기 조정 또한 빠르다

"변화에 강함" 이게 핵심인거 같다.

사용처

[작성중]

그 아이템 뺑뺑이 돌아가는거

특징

연속된 컨테이너를 가지고있다( = 메모리상 연속적으로 저장이 됨 )

탐색의 경우 처음부터 끝까지 하나씩 탐색해야하기 때문에 O(n)

인덱스를 지원하기때문에 랜덤한 접근은 빠르다(조회) O(1)

데이터의 끝부분에 삽입, 삭제는 빠르다. amortized O(1)

[ 삽입시 메모리를 다시 동적할당 받아올 경우 n개만큼 복사가 이루어지기때문에 이 상황에는 O(n) ]

하지만 중간에 삽입, 삭제시에는 그 뒤에 있는 모든 데이터를(n) 한칸씩 앞이나 뒤로 복사가 이루어져 느리다. O(n)

컨테이너의 크기가 고정이 아닌 동적으로 이루어진다

하지만 크기가 자주 변경된다면 불리한 자료구조이다.

=> 잦은 동적할당과 해제 => 메모리 단편화가 발생 할 소지가 많다.

결론

크기가 변할 가능성이 있으나 자주는 아닌 경우,

인덱스를 이용한 접근을 사용하는 경우,

처음부터 쭉 순회를 해야할 경우,

중간 삽입,삭제가 적을 경우

vector를 사용할것이다.

사용처

만약 내 게임에서 사용 한다면

게임 내의 모든 아이템 데이터를 담는 자료구조로 vector를 사용할거 같다.

아이템은 거의 꾸준히 업데이트 되기 때문에 가변적 특성을 띄고

꼭 순차하여 아이템 정보를 가져오는게 아닌

인덱스를 통해 원하는 아이템정보를 가져올 수 있기 때문이다.

플레이어의 분신같은 스킬을 사용할때

각 분신을 vector에 넣을거 같다.

이 스킬에 분신의 개수가 변경될 가능성이 있다고 생각하기 때문에 가변적 특성을 띄고

분신이 나타나고 사라지기 전까지 분신이 추가되는 중간 삽입,삭제가 없어 잘 맞는다고 생각했다.

한 맵에서 출현하는 몬스터들의 데이터를 저장할거 같다.

출현하는 몬스터의 수는 거의 고정적이지만 이벤트성이나 다른 몬스터의 추가로 수정 될 수 있다고 생각하였고

중간에 삽입 삭제할 경우가 없다고 생각이 들어 vector가 적당하다 생각했다.

추가

vector의 순회 속도

더보기

 

https://m.blog.naver.com/PostView.naver?isHttpsRedirect=true&blogId=4roring&logNo=221337048963

이 글과 비슷하게 나도 데이터를 순회 하는데 있어서 밑의 5가지 방법을 테스트 해봤다

1. 함수 at 사용

2. operator [ ] 사용

3. 주소를 직접받아 연산해 순회

4. iterator 사용

5. 범위기반 for문 사용

 

20,000,000개의 데이터를 순회하면서 int형 변수 result에 계속 더하여 테스트했다.

느낀 점

 

1.

이번에 찾아보면서 at과 [ ]를 비교하는 글이 많았었다.

at은 out of range 검사를 해주지만

[ ]은 검사를 하지 않기때문에 at보다 빠르다고 많이들 적혀있었는데

평균적으로 debug모드에서는 정말 차이가 없고 release모드에서만 차이가 확실히 났다.

 

2.

iterator를 사용한 경우 debug모드에서는 굉장히 느렸지만 release모드에서는 굉장히빠른 모습을 보였다

반전매력 ㄷㄷ

 

3.

다른 결과값이 나오기 전까지 vector를 순회할때는 range based for문을 사용해야겠다

 

4.

그래도 이 테스트는 절대적인 성능이 아니라 대략적으로 파악하기 위한거니

상황이 달라지면 결과도 바뀔수있기에 일반화하지 말자

 

코드 부분

왜 Index로 인한 조회는 O(1)?