1. 2606 - 2차원배열 / BFS

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

시도

• Map으로 연결을 표현하려고 하였다.
  하지만 1번에서 2로, 5로 가는 2개의 연결이 존재하므로,
  키값이 중복되게 되었다..
  따라서 한 키에 대한 value값으로 벡터를 두었는데,
  그냥 2차원벡터를 놓으면 해결될것으로 유추되어 수정하였다.

#include <iostream>
#include <queue>
using namespace std;

bool visited[101] = {0, };
bool connection[101][101] =  {0, };
int N; //컴퓨터 개수
int T; //연결 개수

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);


    cin >> N;
    cin >> T;

    int from;
    int to;

    //1. 모든 연결의 쌍을 connection 배열에 저장
    for(int i=0; i<T; i++)
    {
        cin >> from;
        cin >> to;

        connection[from][to] = 1;
    }

    //2. DFS나 BFS를 돌며 연결된 곳 순환

    // BFS를 활용
    queue<int> nextCom;
    nextCom.push(1);    //1번 컴부터 시작
    visited[1] = true;
    int count = 0;
    while(!nextCom.empty())
    {
        // 1. Queue에서 꺼내옴
        int num = nextCom.front();
        nextCom.pop();

        // 2. 연결된 곳을 순회
        for(int i=0; i<101; i++)
        {
            // 3. 연결되었고, 실제로 갈 수 있는가?
            if(connection[num][i]==1 && visited[i]==false)
            {
                // 4.체크인
                visited[i] = true;
                // 5. Queue에다 넣음
                nextCom.push(i);      
                count++;
                //cout<< num << " " << i << endl;          
            }
        }

    }

    cout << count << endl;

    return 0;   
}

틀렸다.

반례

// Input
3
2
1 3
2 3

// Output
2

위의 반례를 통과하지 못했다.
from to로 생각하다 보니 3-2의 연결도 2-3의 연결로 봐야함을 실수하였다.

해결

connection을 추가할 때,
반대의 경우도 추가하니 간단히 해결.

풀이

한 노드에 대한, 여러 노드가 연결될 수 있어서
connection이라는 2차원배열을 만들었다.
(처음에는 Map<int, Vector<int>> 형식으로 만들었는데,
어짜피 한 인덱스에 대해 배열형의 값을 넣어야하면,
그냥 2차원 배열로 두는것이 낫겠다고 생각햇다)

visited라는 배열은 BFS를 위해 생성했다.
visited를 true로 전환하여, 중복된 곳을 굳이 방문하지 않도록 하였다.

BFS는 Queue에 저장된 연결된 곳을 while문동안 계속해서 빼고,
연결된 곳의 연결된 곳을 지속적으로 찾고 있으면 넣었다.

그런 과정에서 visited 배열과 count변수가 값이 바뀌게 되고,
최종 결과값을 찾을 수 있게 된다.

2. 11279 - Heap? 배열로 구현

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

시도

그냥 N번의 정수를 넣는데,
0을 넣으면 최대값을 출력하고, 해당 최대값을 삭제하고
0이 아닌 자연수를 넣으면 배열에 해당 값을 추가한다.

최대값을 삭제하는 부분이.. 이 문제의 구현의 핵심으로 보인다..

삭제를구현하는 법으론 2가지가 있다고 본다.
1. max값의 인덱스를 기록해두고 해당 위치의 값을 삭제한다.
2. 삭제할 때마다 정렬한다, 가장 마지막의 요소를 삭제한다.

1번이 구현하기 쉽다고 본다.
아니다.. 연속해서 삭제하는 경우도 인식해야되므로,
그냥 찾는게 맞다..

#include <iostream>
using namespace std;


void deleteMax();
void add(int num);

int maxIndex=0;
int sizeArr = 0;
int array[100000] = {0, };

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

    int N;
    cin >> N;

    int num;
    for(int i=0; i<N; i++)
    {
        cin >> num;
        if(num==0)
        {
            deleteMax();
        }
        else
        {
            add(num);
        }
    }

    return 0;   
}

// Max값을 찾고, 0으로 삭제한다.
void deleteMax()
{
    if(sizeArr==0)
    {
        cout << 0 << endl;
    }
    else
    {
        int maxNum = 0;
        for(int i=0; i<=sizeArr;i++)
        {
            if(maxNum < array[i])
            {
                maxNum = array[i];
                maxIndex = i;
            }
        }
        cout << maxNum << endl;
        array[maxIndex] = 0; //삭제 대신 0으로 수정
    }
    
}

void add(int num)
{
    array[++sizeArr] = num;
}

위와 같은 방식으로 했더니,
시간초과가 났다.

해결

#include <iostream>
using namespace std;


void deleteMax();
void add(int num);

int maxIndex=0;     //max값을 가지고 있는 인덱스
int sizeArr = 0;    //Array의 유의미한 부분의 size를 정의함
int array[100000] = {0, }; //100000개 선언해둠

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

    int N;
    cin >> N;

    int num;
    for(int i=0; i<N; i++)
    {
        cin >> num;
        if(num==0)
        {
            deleteMax();
        }
        else
        {
            add(num);
        }
    }

    return 0;   
}

// 최대값을 출력하고, 해당 원소 삭제
void deleteMax()
{
    if(sizeArr==0)
    {
        cout << 0 << "\n";  //이번 문제에서 가장 중요했던 부분, endl로 쓰니 시간초과가....
    }
    else
    {
        // 1. 최대값을 찾기 위한 로직
        int maxNum = 0;
        for(int i=0; i<=sizeArr;i++)    //++size이라 <=sizeArr
        {                               //단순히 sizeArr만큼 원소가 들어왔을 것이고, 
                                        //그이후가 0으로 삭제되더라도 100000개보단 범위를 줄일 수 있게 된다.
            // 2. 더 큰값을 찾았다면, 계속 갱신
            if(maxNum < array[i])
            {
                maxNum = array[i];
                maxIndex = i;
            }
        }
        // 3. 최대값 출력 및 해당 값의 원소를 0으로 바꿈
        cout << maxNum << "\n"; 
        array[maxIndex] = 0; //삭제 대신 0으로 수정
    }
    
}

// size는 여기에서 추가된다. 0말고 1부터진행(sizeArr++로 써도 상관없겠다)
void add(int num)
{
    array[++sizeArr] = num;
}

풀이

주석에 다 설명이 되어있고,
이번 문제는 deleteMax를 구현하는 것이 핵심이었다.

참고로 endl을 절대 쓰지 말아야겠다고 느꼈다..
해당 부분만 \n으로 고치니 바로 시간초과 해결...

3. 2504 - 괄호문제(구현)

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

시도

해당 조건에 맞게 잘 읽고 구현하는게 핵심으로 보인다.

어렵다..
전체적인 구조를 알고나서 계산하는건 쉬운데,
하나하나 입력으로 들어오는 과정에서 이건 더해야되고 이건 곱해야되고
계산하는 로직을 작성하는게 상당히 까다롭다.

음..
괄호를 스택에 넣지말고 플래그를 스택에 넣어본다..
그리고 스택 대신에 스택같은 배열을 사용해본다.

#include <iostream>
using namespace std;

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

    string s;
    cin >> s;

    int sum=0;
    int tmpSum=0;

    // 연산 플래그를 적용한다
    // 0- 아무것도 아님 / 1- 2값을더함 / 2- 3값을 더함
    // 3- 2배 / 4- 3배 / 5- ( 덧or곱 / 6- [ 덧or곱
    int exprArray[s.length()] = {0, };
    int sIndex=0;    //스택의 pop연산 이후 인덱스 // 추가되는 값은 i에 넣어야함

    //*  ( ( ) [ [ ] ] ) ( [ ] )     ( ) [ ] [ ]  ( [ ( ) ] )
    for(int i=0; i<s.length(); i++)
    {
        char c = s[i];

        //sIndex는 Stack을 나타낼 인덱스로, 열기괄호면 추가, 닫기괄호면 감소
        if(c == '(' || c == '[')
        {
            //1-여는괄호 다음에 들어온 경우
            if(sIndex!=0 && (exprArray[sIndex-1]==5 || exprArray[sIndex-1]==6))
            {
                // 앞의 괄호가 ( 면 3, [ 면 4로 둔다
                exprArray[sIndex-1]==5? exprArray[sIndex-1]=3 : exprArray[sIndex-1]=4;
                // 현재 괄호가 ( 면 5, [ 면 6로 둔다
                c=='(' ? exprArray[i]=5 : exprArray[i]=6;
                
                sIndex++;
            }
            
            //2-닫는괄호 다음에 여는괄호가 들어온 경우
            // 이걸 생각할 필요가 없엇따.
            // 닫는 괄호가 들어올 일은 없다.
            if(sIndex==0 || (sIndex!=0 && (exprArray[sIndex-1]!=5 || exprArray[sIndex-1]!=6)))
            {
                c=='(' ? exprArray[sIndex]=5 : exprArray[sIndex]=6;

                sIndex++;
            }
        }
        else if(c == ')' || c == ']')
        {
            //1- 앞이 본인의 '열기'가 맞는경우
            if(sIndex!=0)
            {
                if( c==')' )
                {
                    // 1- 뎃셈확정
                    if(exprArray[sIndex-1]==5)
                    {
                        exprArray[sIndex]=1;
                        tmpSum += 2;
                    }
                    // 2- 곱셈
                    else if(exprArray[sIndex-1]==3)
                    {
                        sum+= tmpSum*2;
                    }
                    else
                    {
                        break;
                    }
                }
                else
                {
                    if(exprArray[sIndex-1]==6) 
                    {
                        exprArray[sIndex]=2;
                        tmpSum += 3;
                    }
                    else if(exprArray[sIndex-1]==4)
                    {
                        sum+= tmpSum*3;
                    }
                    else
                    {
                        break;
                    }
                }
                sIndex--;
            }
            else
            {
                break;
            }
        }
    }

    // stack이 비지 않았다면
    if(sIndex!=0)
    {
        cout << 0 << "\n";
    }
    
    // 최종 sum 계산

    
    cout << sum << "\n";
    return 0;   
}

sIndex라는 스택인덱스와 I라는 인덱스를 따로 보았는데.
sIndex로 스택의 pop을 하고 남은 인덱스를 표현하려고 했었다.
하지만, 구현하고보니 의미없는 변수였다.
아니다
exprArray에는 여는괄호만 쌓이게 된다.
pop으로 없어져도 sIndex에 따라
유의미한 부분만 값 대입하고 사용하면 된다.

추가로 ..
[ ( ( ) ) [ [ [ ] ] ] 이런 덧셈을 어떻게 계산하도록 해야할까..
[ ( ( [ [ [ 여는 괄호만 exprArray에 들어오고,
곱셈인지 덧셈인지만 판별할 수가 있다.
그런데 어디까지 그냥 더하고
어디까지 곱해야하는지 어떻게 알게할까?

()처럼 나오자마자 여는괄호없이 닫기는것은
무조건 덧셈으로 인식하는게 맞다
반례없는 불변하는 공식이다.

하지만 곱셈으로 플래그가 선 다수의 (( 들은?
가장 처음의 곱셈플래그 계산시(마지막)에 여태계산한 값을 곱하고 sum으로 넘겨주면 될텐데..

중간의 (는 어떻게 계산할까..
닫긴다음에 다른열기가 나온다면 서로 덧셈인데,
들어올때는 아래처럼 들어오게 된다.

N
[
[(
[((
[(
[
[[
[[[
[[
[
N

닫기로 pop되고 다음 열때, 플래그를 설정해두면 될까?
닫기다음열리면 덧셈
닫기다음닫기면 곱셈

플래그를 간단히 만들 수 있을까?

( (()) ([]()()()()()()()) (()()) (()()()()) )

닫기다음열리면 덧셈인데..
해당 항이 곱셈 내부의 덧셈들이 엄청나게 많이 있을 수 있는 덧셈이다..

해결을 위해 덧셈의 계층구조를 만들어본다..

시도 2

#include <iostream>
using namespace std;

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

    string s;
    cin >> s;

    int sum=0;
    int tmpSum[s.length()/2] = {0, }; //계층은 최대 length/2개
    int rank=0; //계층
    // [ 1식[ 2식[ 3식[ 4식 ]]]]

    // 연산 플래그를 적용한다
    // 0- 아무것도 아님 / 1- ( 일단 덧셈, 곱 미정 / 2- [ 일단 덧셈, 곱 미정
    // 3- 2배곱 확정 / 4- 3배곱 확정
    int exprArray[s.length()] = {0, };
    int sIndex=0;    //스택의 pop연산 이후 인덱스 // 추가되는 값은 i에 넣어야 함
                    //i에는 의미없는 값이 있을 수 있다. 현재i만 의미가 있다.
                    //현재 들어갈 수 있는 곳이 sIndex의 위치;
    //*  ( ( ) [ [ ] ] ) ( [ ] )     ( ) [ ] [ ]  ( [ ( ) ] )
    for(int i=0; i<s.length(); i++)
    {
        char c = s[i];

        //sIndex는 Stack을 나타낼 인덱스로, 열기괄호면 추가, 닫기괄호면 감소
        //*1- 여는괄호가 들어온 경우
        if(c == '(' || c == '[')
        {
            if(sIndex!=0)
            {
                // 앞의 괄호가 덧셈지정만 되어있다면 곱셈으로 승격시킨다.
                if(exprArray[sIndex-1]==1 || exprArray[sIndex-1]==2)
                {
                    exprArray[sIndex-1]==1? exprArray[sIndex-1]=3 : exprArray[sIndex-1]=4;
                    rank++; // 여는괄호다음 여는괄호여야 rank를 추가
                }
                // 현재 괄호가 ( 면 1, [ 면 2로 둔다
                c=='(' ? exprArray[sIndex]=1 : exprArray[sIndex]=2;

                sIndex++;
            } 
            else //(sIndex==0)
            {
                // 현재 괄호 값만 설정
                c=='(' ? exprArray[sIndex]=1 : exprArray[sIndex]=2;
                
                sIndex++;
            }
        }
        //*2- 닫는괄호가 들어온 경우 - 여는괄호를 제거
        else if(c == ')' || c == ']')
        {
            // 1 닫는괄호가 왔는데 아무것도 없으면 오류
            if(sIndex==0)
            {
                sIndex++; //일부러 증가시키고 종료
                break;
            }
            // 2 여는괄호 목록이 존재한다면,
            else
            {
                // 본인이 ) 일때,
                if( c==')' )
                {
                    // 1- 여는괄호가 단지 1이면, tmpSum에 덧셈연산
                    if(exprArray[sIndex-1]==1)
                    {
                        tmpSum[rank] += 2;
                    }
                    // 2- 여는괄호가 3이면, 여태의 tmpSum에 곱셈연산/덧셈 및 초기화
                    else if(exprArray[sIndex-1]==3)
                    {
                        tmpSum[rank] *= 2;
                        if(!(rank-1<0))
                        {
                            tmpSum[rank-1] += tmpSum[rank];
                            tmpSum[rank] = 0;
                        }
                        rank--;
                    }
                    else
                    {
                        break;
                    }
                }
                // 본인이 ] 일때,
                else
                {
                    if(exprArray[sIndex-1]==2) 
                    {
                        tmpSum[rank] += 3;
                    }
                    else if(exprArray[sIndex-1]==4)
                    {
                        tmpSum[rank] *= 3;
                        if((rank-1) >= 0)
                        {
                            tmpSum[rank-1] += tmpSum[rank];
                            tmpSum[rank] = 0;
                        }
                        rank--;
                    }
                    else
                    {
                        break;
                    }
                }
                sIndex--;
                if(sIndex==0)
                {
                    tmpSum[0] += tmpSum[1];
                    tmpSum[1] = 0;
                }            
            }
        }
    }

    // 최종 sum 출력
    // stack이 비지 않았다면 오류
    if(sIndex!=0)
    {
        cout << 0 << "\n";
    }
    else
    {
        cout << tmpSum[0] << "\n";
    }
    
    return 0;   
}

런타임시에 배열의 범위를 벗어난 에러
음..

위처럼 tmpSum의 크기를 수정해보았다.
그러니까 계층이 s.length개의 반이 되는게 정상이라고 생각했는데,
(홀수면 애초에 오류일뿐더러, /2를 하면 반보다 아래의 수이므로)
비정상적인 괄호 예의 경우,
충분히 length개만큼 계층이 생길 수 있게 된다.
ex) [ [ [ [ [ [ [ = 7개의 계층

풀이

핵심 기물은 위와 같다.
입력에서 괄호를 하나씩 읽어들여
exprArray에 해당 여는 괄호가 어떤 괄호인지 0~4까지 플래그를 담도록 하였고,
sIndex를 두어서 배열이지만 stack처럼 사용할 수 있도록
배열에서 pop을 하면 유의미한 부분만 제한하도록 변수를 두었다.

나머지는 주석을 참고

특정 구현법이 있다기보다,
진짜 뇌를 써서 구현하는 문제 그 자체였고,
(나는 어떻게 계산하지?라는 내용을 계속 생각하며)
인간이 계산하는 과정을 그대로 알고리즘으로 풀어서
컴퓨터에 설명해야만 풀 수 있는 문제였다.

장장 3시간 걸린문제..
실버1에서 허덕이면 안된다..