개발 블로그

문제 링크 : www.acmicpc.net/problem/13305

문제

어떤 나라에 N개의 도시가 있다. 이 도시들은 일직선 도로 위에 있다. 편의상 일직선을 수평 방향으로 두자. 제일 왼쪽의 도시에서 제일 오른쪽의 도시로 자동차를 이용하여 이동하려고 한다. 인접한 두 도시 사이의 도로들은 서로 길이가 다를 수 있다. 도로 길이의 단위는 km를 사용한다.

처음 출발할 때 자동차에는 기름이 없어서 주유소에서 기름을 넣고 출발하여야 한다. 기름통의 크기는 무제한이어서 얼마든지 많은 기름을 넣을 수 있다. 도로를 이용하여 이동할 때 1km마다 1리터의 기름을 사용한다. 각 도시에는 단 하나의 주유소가 있으며, 도시 마다 주유소의 리터당 가격은 다를 수 있다. 가격의 단위는 원을 사용한다.

예를 들어, 이 나라에 다음 그림처럼 4개의 도시가 있다고 하자. 원 안에 있는 숫자는 그 도시에 있는 주유소의 리터당 가격이다. 도로 위에 있는 숫자는 도로의 길이를 표시한 것이다. 

제일 왼쪽 도시에서 6리터의 기름을 넣고, 더 이상의 주유 없이 제일 오른쪽 도시까지 이동하면 총 비용은 30원이다. 만약 제일 왼쪽 도시에서 2리터의 기름을 넣고(2×5 = 10원) 다음 번 도시까지 이동한 후 3리터의 기름을 넣고(3×2 = 6원) 다음 도시에서 1리터의 기름을 넣어(1×4 = 4원) 제일 오른쪽 도시로 이동하면, 총 비용은 20원이다. 또 다른 방법으로 제일 왼쪽 도시에서 2리터의 기름을 넣고(2×5 = 10원) 다음 번 도시까지 이동한 후 4리터의 기름을 넣고(4×2 = 8원) 제일 오른쪽 도시까지 이동하면, 총 비용은 18원이다.

각 도시에 있는 주유소의 기름 가격과, 각 도시를 연결하는 도로의 길이를 입력으로 받아 제일 왼쪽 도시에서 제일 오른쪽 도시로 이동하는 최소의 비용을 계산하는 프로그램을 작성하시오.

입력

표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 도시의 개수를 나타내는 정수 N(2 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 인접한 두 도시를 연결하는 도로의 길이가 제일 왼쪽 도로부터 N-1개의 자연수로 주어진다. 다음 줄에는 주유소의 리터당 가격이 제일 왼쪽 도시부터 순서대로 N개의 자연수로 주어진다. 제일 왼쪽 도시부터 제일 오른쪽 도시까지의 거리는 1이상 1,000,000,000 이하의 자연수이다. 리터당 가격은 1 이상 1,000,000,000 이하의 자연수이다. 

출력

표준 출력으로 제일 왼쪽 도시에서 제일 오른쪽 도시로 가는 최소 비용을 출력한다. 

접근 방법

처음에 최소 비용을 1,000,000,000으로 초기화 한 뒤,

주유소를 하나씩 검사해 나가면서 해당 주유소의 리터당 가격과 최소 비용을 비교해서 더 작은 값을 최소 비용으로 설정한다.

이전에 설정했던 최소 비용 값이 갱신되면(새 주유소 가격이 더 싸서) 갱신된 가격과 거리를 곱하고

이전에 설정했던 최소 비용 값이 갱신되지 않으면(원래 이전의 주유소 가격이 더 싸서) 이전에 설정한 최소 비용 값과 거리를 곱한다.

//
//  Greedy_BOJ13305_주유소.cpp
//  Coding_Test_Practice
//
//  Created by 김난영 on 2021/05/07.   11:01 ~ 11:35
//  Copyright © 2021 KimNanyoung. All rights reserved.
//

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

int main(){
    
    long long ans = 0;
    
    int N; cin >> N;
    
    vector<long long>  disVec;
    vector<long long> costVec;
    for(int i=0; i<N-1; i++){
        long long d; cin>>d;
        disVec.push_back(d);
    }
    for(int i=0; i<N; i++){
        long long c; cin>>c;
        costVec.push_back(c);
    }
    
    long long greedyMin = 1000000000; //리터당 가격의 최대값
    for(int i = 0; i<N; i++){
        if(costVec[i] < greedyMin){     //더 싼 가격이 나타나서
            greedyMin = costVec[i];     //최소값 갱신
        }
        ans += (disVec[i] * greedyMin); //거리와 최소 가격 곱함
        
    }
    
    cout << ans;

    return 0;
}

문제 링크 : www.acmicpc.net/problem/14916

문제

춘향이는 편의점 카운터에서 일한다.

손님이 2원짜리와 5원짜리로만 거스름돈을 달라고 한다. 2원짜리 동전과 5원짜리 동전은 무한정 많이 가지고 있다. 동전의 개수가 최소가 되도록 거슬러 주어야 한다. 거스름돈이 n인 경우, 최소 동전의 개수가 몇 개인지 알려주는 프로그램을 작성하시오.

예를 들어, 거스름돈이 15원이면 5원짜리 3개를, 거스름돈이 14원이면 5원짜리 2개와 2원짜리 2개로 총 4개를, 거스름돈이 13원이면 5원짜리 1개와 2원짜리 4개로 총 5개를 주어야 동전의 개수가 최소가 된다.

입력

첫째 줄에 거스름돈 액수 n(1 ≤ n ≤ 100,000)이 주어진다.

출력

거스름돈 동전의 최소 개수를 출력한다. 만약 거슬러 줄 수 없으면 -1을 출력한다.

접근 방법

크게 거슬러줘야 할 돈이 5원보다 작은 경우와 큰 경우로 나눠서 생각한고, 각 경우에 대해 케이스를 나눠 생각하면 쉽게 구할 수 있다.

5원보다 작은 경우

1) 2원으로 줄 수 있는 경우

2) 2원으로 줄 수 없는 경우

5원보다 큰 경우

1) 5원으로 최대한 주고 남은 돈을 2원으로 줄 수 있는 경우

2) 5원으로 최대한 주고 남은 돈을 2원으로 줄 수 없는 경우

//
//  Greedy_BOJ14916_거스름돈.cpp
//  Coding_Test_Practice
//
//  Created by 김난영 on 2021/05/07.  
//  Copyright © 2021 KimNanyoung. All rights reserved.
//

#include <iostream>

using namespace std;

int main(){
    int ans = 0;
    
    int n;
    cin>>n;
    
    if(n<5){
        if(n%2==0) ans = n/2;
        else ans = -1;              //거스름돈 5원보다 작은데 2원으로도 낼 수 없는 경우
    }
    else{

        if(n%5==0){
            ans = n/5;
        }
        else{
            
            int q = n/5;
            int remain = n - q*5;
            
            if(remain%2==0){//  1) 5원으로 최대한 주고 남은 돈을 2원으로 줄 수 있는 경우
                ans = q + remain/2;
            }
            else{			//  2) 5원으로 최대한 주고 남은 돈을 2원으로 줄 수 없는 경우
                ans = (q-1) + (remain+5)/2;
            }
        }
    }
    

    cout << ans;
    
    return 0;
}

문제 링크 : www.acmicpc.net/problem/8111

문제

폴란드 왕자 구사과는 다음과 같은 수를 좋아한다.

• 0과 1로만 이루어져 있어야 한다.
• 1이 적어도 하나 있어야 한다.
• 수의 길이가 100 이하이다.
• 수가 0으로 시작하지 않는다.

예를 들어, 101은 구사과가 좋아하는 수이다.

자연수 N이 주어졌을 때, N의 배수 중에서 구사과가 좋아하는 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 T(T < 1,000)가 주어진다.

둘째 줄부터 T개의 줄에는 자연수 N이 한 줄에 하나씩 주어진다. N은 20,000보다 작거나 같은 자연수이다.

출력

각각의 테스트 케이스마다 N의 배수이면서, 구사과가 좋아하는 수를 아무거나 출력한다. 만약, 그러한 수가 없다면 BRAK을 출력한다.

접근 방법

N의 배수가 최대 100자리 까지 나올 수 있기 때문에 무작정 0과 1을 붙여가면서 N으로 나눠지는지 확인하면 안 된다. (오버플로우) 

어떤 수 x 가 N의 배수인지 확인하려면 (x mod N) 이 0인지 확인할 수도 있겠지만 x가 계속 커지는 걸 방지하기 위해 (x mod N) mod N이 0인지 확인하면 된다. modular 연산의 성질에 의해   (x mod N) 는 (x mod N) mod N와 같기 때문이다. 

그래서 x 대신 "현재의 수 cur에 0또는 1을 붙이고 N으로 나눈 나머지"를 고려하면 된다.  

cur = 1이라면 node[0]은 10%N. node[1] = 11%N이 된다. 

//자식 노드 2개, 가지치기, 0과 1을 붙일 수 있음
        int node[2];
        node[0] = (cur*10 + 0) % N;
        node[1] = (cur*10 + 1) % N;

그럼 어떻게 원래의 수를 기억할것인가?

매 depth 마다 0을 붙였는지 1을 붙였는지를 char 형으로 저장한 뒤에, depth가 마지막까지 내려왔을 때 거꾸로 올라가면서 어떤 수를 붙여왔는지 출력하면 된다. 

그럴려면 현재 노드에서 부모 노드를 타고 거꾸로 올라가려면 해당 노드의 부모 노드 번호를 알아야한다. 

arr[자식idx].first 에는 idx번째 자식노드의 부모 노드 번호를 저장하고,

arr[자식idx].second 에는 해당 depth에서 붙인 숫자를 char 형으로 저장한다. ('0' or '1')

다 저장하고 마지막에 0번째 자식부터 재귀 함수를 통해 거꾸로 올라가면서 arr[].second 를 출력한다. 이때, 0번째 자식부터 시작하는 이유는 (x mod N) mod N이 0이 되면서 그 0을 arr[]의 idx로 지정해 정보를 저장한 뒤, BFS() 함수를 종료했기 때문이다. 

//
//  BFS_BOJ8111_0과1.cpp
//  Coding_Test_Practice
//
//  Created by 김난영 on 2021/05/02. 05:27~06:10 / 06:24 / 06:40
//  Copyright © 2021 KimNanyoung. All rights reserved.
//

#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <utility>
#include <string.h>

using namespace std;
int N;
int visited[20001] = {0};
pair<int, char> arr[20001];

void BFS(){
    memset(visited, 0, sizeof(visited));
    queue<int> que;
    que.push(1);        //첫 글자는 0 안 됨
    
    //가장 첫 루트 노드
    arr[1].first = -1;   //부모 노드 번호 표시 (부모가 -1이면 루트 노드인 것)
    arr[1].second = '1'; //N의 배수는 1부터 시작하므로

    visited[1] = 1;
    
    
    while(!que.empty()){
        
        int cur = que.front();
        que.pop();
        
        
        //자식 노드 2개, 가지치기, 0과 1을 붙일 수 있음
        int node[2];
        node[0] = (cur*10 + 0) % N;
        node[1] = (cur*10 + 1) % N;
        
        for(int i = 0; i<2; i++){
            if(visited[node[i]]==1) continue;
            
            arr[node[i]].first = cur;   //node[i]의 부모 노드는 cur
            arr[node[i]].second = i + '0';      // 현재 수에서 어떤 수를 덧붙였는지 저장, i는 0또는 1인 정수. 여기에 '0' 더해서 char 형으로 변환
            
            if(node[i]==0) return;      //N으로 나눈 나머지가 0이므로 N의 배수 찾은 것
            
            visited[node[i]] = 1;       //방문했음을 표시
            que.push(node[i]);
            
            
        }
        
        
    }
    
}

void printReverse(int parent){
    if(parent==-1) return;      //부모 노드가 -1이면 루트 노드
    
    printReverse(arr[parent].first);
    cout << arr[parent].second;
    
}


int main(){
    
    
    int T; cin >> T;
    
    for(int test_case = 1; test_case<=T; test_case++){
        
         cin >> N;
        if(N==1) {
            cout << 1 << endl;      //1의 배수는 1이므로 바로 출력
            continue;
        }
        
        BFS();
        printReverse(0);            //arr[0] 부터 거꾸로 타고 올라감. 0부터 시작하는 이유는 N의 배수가 되면서 나머지가 0이 됐고 이를 인덱스로 해서 저장했기 때문에
        cout << endl;
        
        
    }
    
    return 0;
}

참고 : jaimemin.tistory.com/791

문제 링크 : www.acmicpc.net/problem/1952

문제

M줄 N칸으로 되어 있는 표 위에, 달팽이 모양으로 선을 그리려고 한다.

위의 그림은 M=5, N=3의 예이다. 이제 표의 왼쪽 위 칸(ㅇ)에서 시작하여, 오른쪽으로 선을 그려 나간다. 표의 바깥 또는 이미 그려진 칸에 닿아서 더 이상 이동할 수 없게 되면, 시계방향으로 선을 꺾어서 그려나간다.

위의 표는 선을 그려 나간 모양을 나타낸 것이다. 선이 꺾어진 부분은 대각선으로 나타내었다. 표의 모든 칸이 채워질 때까지, 선을 몇 번 꺾게 될까?

입력

첫째 줄에 M과 N이 빈 칸을 사이에 두고 주어진다. (2 ≤ M, N ≤ 100)

출력

첫째 줄에 표의 모든 칸이 채워질 때까지 선이 꺾어지는 횟수를 출력한다.

접근 방법

시작 지점 [0][0]에서 시작해서 오, 아, 왼, 위 방향 순으로 전진하며, 

이미 map[nr][nc]가 1이거나(방문 먼저 했거나) 범위 넘어가면 카운트를 증가한다.

M*N 만큼 칸을 방문하면 반복문을 멈춘다.

//
//  SM_BOJ1952_달팽이2.cpp
//  Coding_Test_Practice
//
//  Created by 김난영 on 2021/05/01. 4:46 ~ 
//  Copyright © 2021 KimNanyoung. All rights reserved.
//

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

int map[101][101];
//오 아 왼 위
int dr[4] = {0,1,0,-1};
int dc[4] = {1,0,-1,0};

int main(){
    
    int M, N;
    cin >> M >> N;
    
    memset(map, 0, sizeof(map));
    int ans = 0;
    int cnt = 1;
    
    int d= 0;
    int r = 0;
    int c = 0;
    map[r][c] = 1;
    while(1){
        
        if(cnt== M*N) break;
          
        int nr = r + dr[d];
        int nc = c + dc[d];
        
        //범위 넘어가거나 이미 map[i][j]==1 이면
        if(nr<0 || nr>M-1 || nc<0 || nc>N-1 || map[nr][nc]==1){
            ans += 1;
            if(d==3) d = 0;
            else d = d+1;
        }
        else{
            map[nr][nc] = 1;
            cnt += 1;
            r = nr;
            c = nc;
        }
    }
    cout << ans; 
    
    
    
    return 0;
}

문제 링크 : www.acmicpc.net/problem/1913

문제

홀수인 자연수 N이 주어지면, 다음과 같이 1부터 N2까지의 자연수를 달팽이 모양으로 N×N의 표에 채울 수 있다.

N이 주어졌을 때, 이러한 표를 출력하는 프로그램을 작성하시오. 또한 N2 이하의 자연수가 하나 주어졌을 때, 그 좌표도 함께 출력하시오. 예를 들어 N=5인 경우 6의 좌표는 (4,3)이다.

입력

첫째 줄에 홀수인 자연수 N(3 ≤ N ≤ 999)이 주어진다. 둘째 줄에는 위치를 찾고자 하는 N2 이하의 자연수가 하나 주어진다.

출력

N개의 줄에 걸쳐 표를 출력한다. 각 줄에 N개의 자연수를 한 칸씩 띄어서 출력하면 되며, 자릿수를 맞출 필요가 없다. N+1번째 줄에는 입력받은 자연수의 좌표를 나타내는 두 정수를 한 칸 띄어서 출력한다.

접근 방법

1) N에 따른 회오리 수를 구해준다. (N/2번)

2) 각 회오리마다 시작 지점의 행과 열을 지정한다. (N/2 -1, N/2 -1)

3) 방향을 나타내는 배열 dr[4], dc[4]의 방향을 오, 아, 왼, 위  순서로 지정한다.

4) 시작 지점에서 전진을 하면서 숫자를 하나씩 증가시키며 이차원 배열을 채워 넣고, 일정 범위를 넘어가면 전진 방향을 바꾼다.

5) 이때 범위는 몇번째 회오리인지에 따라 달라지는데, 회오리가 i 번째라고 하면 행과 열의 범위는 N/2-i ~ N/2+i 가 된다.

회오리 하나의 칸을 다 채웠으면 다음 바깥쪽의 회오리를 채우며, 다음 회오리로 넘어갈 때 시작 지점을 행-1, 열-1 로 지정한다.

//
//  SM_BOJ1913_ 달팽이.cpp
//  Coding_Test_Practice
//
//  Created by 김난영 on 2021/05/01.
//  Copyright © 2021 KimNanyoung. All rights reserved.
//


#include <iostream>
#include <utility>

using namespace std;

//오 아 왼 위
int dr[4] = {0,1,0,-1};
int dc[4] = {1,0,-1,0};

int map[1000][1000];
int main(){
    
    pair<int,int> p;
    
    int N, x;
    cin >> N >> x;
    
    int rotateCnt = N/2;        //회오리 수
        
    int num = 1;
    map[N/2][N/2] = num;
    
    int startR = N/2 -1;
    int startC = N/2 -1;
    for(int i = 1; i<=rotateCnt; i++){
        
        int r = startR;
        int c = startC;
        
        for(int d = 0; d<4;){
            int nr = r + dr[d];
            int nc = c + dc[d];
            
            if((N/2 -i<=nr && nr<=N/2+i) && (N/2 -i<=nc && nc<=N/2+i)){
                num+=1;
                map[nr][nc] = num;
                if(num==x){
                    p.first = nr + 1;
                    p.second = nc + 1;
                }
                r = nr; //다음 칸 전진
                c = nc;
            }
            else{   //범위 넘어갔으니 방향 바꿔야함
                d++;
            }
           
        }
          
        //시작점 바꾸기 -1, -1
        startR -= 1;
        startC -= 1;
        
    }
    
    for(int i = 0; i<N; i++){
        for(int j = 0; j<N; j++){
            cout << map[i][j] << " ";
        }cout << endl;
    }
    cout << p.first << " " << p.second ;
    
    
    
    return 0;
}

문제 링크 : www.acmicpc.net/problem/4659

문제

좋은 패스워드를 만드는것은 어려운 일이다. 대부분의 사용자들은 buddy처럼 발음하기 좋고 기억하기 쉬운 패스워드를 원하나, 이런 패스워드들은 보안의 문제가 발생한다. 어떤 사이트들은 xvtpzyo 같은 비밀번호를 무작위로 부여해 주기도 하지만, 사용자들은 이를 외우는데 어려움을 느끼고 심지어는 포스트잇에 적어 컴퓨터에 붙여놓는다. 가장 이상적인 해결법은 '발음이 가능한' 패스워드를 만드는 것으로 적당히 외우기 쉬우면서도 안전하게 계정을 지킬 수 있다. 

회사 FnordCom은 그런 패스워드 생성기를 만들려고 계획중이다. 당신은 그 회사 품질 관리 부서의 직원으로 생성기를 테스트해보고 생성되는 패스워드의 품질을 평가하여야 한다. 높은 품질을 가진 비밀번호의 조건은 다음과 같다.

1. 모음(a,e,i,o,u) 하나를 반드시 포함하여야 한다.
2. 모음이 3개 혹은 자음이 3개 연속으로 오면 안 된다.
3. 같은 글자가 연속적으로 두번 오면 안되나, ee 와 oo는 허용한다.

이 규칙은 완벽하지 않다;우리에게 친숙하거나 발음이 쉬운 단어 중에서도 품질이 낮게 평가되는 경우가 많이 있다.

입력

입력은 여러개의 테스트 케이스로 이루어져 있다.

각 테스트 케이스는 한 줄로 이루어져 있으며, 각 줄에 테스트할 패스워드가 주어진다.

마지막 테스트 케이스는 end이며, 패스워드는 한글자 이상 20글자 이하의 문자열이다. 또한 패스워드는 대문자를 포함하지 않는다.

접근 방법

각 조건에 맞는 함수를 작성했다.

모음 또는 자음이 세번 연속 나오는 조건을 따지는 함수에서, 자음 나오다 모음 나온 경우 또는 모음 나오다 자음 나온 경우에 초기화를 해주는 것을 주의해야 한다.

#include <iostream>
#include <string>
#include <vector>
#include <utility>
using namespace std;

bool onemoreComp(string str) {
	for (int i = 0; i < str.length(); i++) {
		if (str[i] == 'a' || str[i] == 'e' || str[i] == 'i' || str[i] == 'o' || str[i] == 'u') {
			return true;
		}
	}
	return false;
}
bool threeConti(string str) {
	int consonant = 0;	//자음
	int collection = 0;	//모음
	for (int i = 0; i < str.length(); i++) {
		if (str[i] == 'a' || str[i] == 'e' || str[i] == 'i' || str[i] == 'o' || str[i] == 'u') {
			if (consonant != 0) { //자음 나오다가 모음 나온 경우 -> 자음 초기화
				consonant = 0;
			}
			collection += 1;
		}
		else {	//자음
			if (collection != 0) {	//모음 나오다가 자음 나온 경우 -> 모음 초기화
				collection = 0;
			}
			consonant += 1;
		}

		if (consonant >= 3 || collection >= 3) return false;
	}
	return true;
}
bool twoConti(string str) {
	for (int i = 0; i < str.length()-1; i++) {
		if (str[i] == str[i + 1]) {
			if (str[i] == 'e' || str[i] == 'o') continue;
			else return false;
		}
	}
	return true;
}


int main() {

	vector<pair<string, bool>> vec;

	while (1) {

		string str;
		cin >> str;
		if (str == "end") break;

		if (onemoreComp(str) == false || threeConti(str) == false || twoConti(str) == false) {
			vec.push_back(make_pair(str, false));
		}
		else vec.push_back(make_pair(str, true));

	}
	for (int i = 0; i < vec.size(); i++) {
		cout << "<" << vec[i].first << "> is ";
		if (vec[i].second == true) cout << "acceptable.\n";
		else cout << "not acceptable.\n";
	}


	return 0;
}

문제 링크 : www.acmicpc.net/problem/1316

문제

그룹 단어란 단어에 존재하는 모든 문자에 대해서, 각 문자가 연속해서 나타나는 경우만을 말한다. 예를 들면, ccazzzzbb는 c, a, z, b가 모두 연속해서 나타나고, kin도 k, i, n이 연속해서 나타나기 때문에 그룹 단어이지만, aabbbccb는 b가 떨어져서 나타나기 때문에 그룹 단어가 아니다.

단어 N개를 입력으로 받아 그룹 단어의 개수를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 단어의 개수 N이 들어온다. N은 100보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 단어가 들어온다. 단어는 알파벳 소문자로만 되어있고 중복되지 않으며, 길이는 최대 100이다.

출력

첫째 줄에 그룹 단어의 개수를 출력한다.

접근 방법

문자열을 입력받고 한 character 씩 검사한다. chkArr[26] 배열은 알파벳이 이미 나왔는지 검사하는 배열이다. 아스키코드를 고려해서 소문자 'a'가 97이므로 인덱스에서 97을 빼주는 것을 잊지 말자. 

'happy' 를 예로 들어보자.

h 는 나온 적이 없으므로 chkArr[7] = 1로 바꾼다. (h는 8번째 알파벳)

a 는 나온 적이 없으므로 chkArr[0] = 1로 바꾼다. (a는 1번째 알파벳)

p 는 나온 적이 없으므로 chkArr[15] = 1로 바꾼다. (p는 16번째 알파벳)

p 는 나온 알파벳인데 바로 전 글자와 같으므로 그룹 단어 조건에 어긋나지 않으므로 계속 검사를 진행한다.

y 는 나온 적이 없으므로 chkArr[24] = 1로 바꾼다. (y는 25번째 알파벳)

모든 글자가 다 통과했으므로 ans를 하나 증가시킨다.

'abac'를 예로 들어보자.

a 는 나온 적이 없으므로 chkArr[0] = 1로 바꾼다. (a는 1번째 알파벳)

b 는 나온 적이 없으므로 chkArr[1] = 1로 바꾼다. (b는 2번째 알파벳)

a 는 이미 나온 알파벳인데 전 글자와 다르므로 그룹 단어 조건에 어긋난다. 그러므로 chk=0로 설정하고 즉시 검사를 중단한다. 

chk!=1 이므로 ans를 증가시키지 않는다.

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

int main() {
	//a = 97

	int N;
	scanf("%d", &N);

	int ans = 0;
	int chkArr[26];

	for (int i = 0; i < N; i++) {

		memset(chkArr, 0, sizeof(chkArr));
		char str[101];
		scanf("%s", str);
		int idx = 0;
		int chk = 1;
		while (1) {
			
			if (str[idx] == '\0') { break; }

			char c = str[idx];
			if (chkArr[c - 97] == 1) {			//이미 나온 경우
				if (str[idx - 1] != str[idx]) {		//바로 전 글자와 같으므로 그룹임
					chk = 0;
					break;
				}
			}
			else {
				chkArr[c - 97] = 1;			//나온 적 없는 경우 1로 바꿈
			}

			idx++;
		}
		
		if (chk == 1) ans += 1;


	}
	printf("%d", ans);


	return 0;
}

문제 링크 : www.acmicpc.net/problem/3029

문제

창영마을에서 정인이의 반란은 실패로 끝났다. (3028번)

테러리스트로 변신한 정인이는 창영마을에 경고를 하려고 한다.

사실 정인이는 창영마을에서 제일 착한사람이다. 따라서, 사람들을 다치지 않게하려고 한다.

유튜브에서 폭발에 대한 동영상을 찾아보다가, 그는 나트륨을 물에 던지면 폭발한다는 사실을 알게 되었다.

정인이는 창영마을의 중심을 지나는 "강산강" 근처에 숨어있다가, 나트륨을 위의 동영상처럼 물에 던질 것이다.

현재 시간과 정인이가 나트륨을 던질 시간이 주어졌을 때, 정인이가 얼마나 숨어있어야 하는지 구하는 프로그램을 작성하시오. (정인이는 적어도 1초를 기다리며, 많아야 24시간을 기다린다.)

입력

첫째 줄에 현재 시간이 hh:mm:ss 형식으로 주어진다. (시, 분, 초) hh는 0보다 크거나 같고, 23보다 작거나 같으며, 분과 초는 0보다 크거나 같고, 59보다 작거나 같다.

둘째 줄에는 나트륨을 던질 시간이 위와 같은 형식으로 주어진다.

출력

첫째 줄에 정인이가 기다려야 하는 시간을 입력과 같은 형식으로 출력한다.

접근 방법

던질 시간에서 현재 시간을 빼야 기다려야하는 시간을 구할 수 있다.

던질 시간이 현재 시간보다 더 크다면 그냥 빼면 되지만, 그 반대이면 앞 단위에서 1분 또는 1시간을 빌려와야한다. 

예시를 들어보면 더 쉽다.

예1. 그냥 빼면 될 때

던질시간 -> 10:25:20

현재 시간 -> 05:10:04

답 : 05:15:16

예2. 앞 단위에서 빌려와야 할 때

던질 시간 -> 04:05:20  

현재 시간 -> 20:10:30

20초에서 30초를 못 빼므로 1분을 빌려와서 04:04:80초로 만들어준다.

04분에서 10분을 못 빼므로 1시간을 빌려와서 03:64:80초로 만들어준다.

이제 03:64:80에서

       20:10:30을 빼주면 된다. 이때 시간도 못 빼는 경우에는 (24-20)시에 03시를 더해주면 된다.

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>

int change(char c1, char c2) {			//char -> int
	
	int res = 0;
	if (c1 == '0') {
		res = c2 - '0';
	}
	else {
		res = (c1 - '0') * 10 + (c2 - '0');
	}
	return res;
}


int main() {


	char curTime[9], nextTime[9];
	scanf("%s", curTime);
	scanf("%s", nextTime);

	int cur_h = change(curTime[0], curTime[1]);
	int cur_m = change(curTime[3], curTime[4]);
	int cur_s = change(curTime[6], curTime[7]);

	int next_h = change(nextTime[0], nextTime[1]);
	int next_m = change(nextTime[3], nextTime[4]);
	int next_s = change(nextTime[6], nextTime[7]);


	if (cur_h==next_h && cur_m==next_m && cur_s==next_s) {	//적어도 1초를 기다리므로
		printf("24:00:00");
	}
	else {

		if (cur_s > next_s) {
			next_m -= 1;
			next_s += 60;
		}
		int s = next_s - cur_s;

		if (cur_m > next_m) {
			next_h -= 1;
			next_m += 60;
		}
		int m = next_m - cur_m;

		int h;
		if (cur_h > next_h) {
			h = (24 - cur_h) + next_h;
		}
		else {
			h = next_h - cur_h;
		}


		//출력 처리
		if (h < 10) {
			printf("0");
		}
		printf("%d:", h);

		if (m < 10) printf("0");
		printf("%d:", m);

		if (s < 10) printf("0");
		printf("%d", s);


	}

	return 0;

}

-시간 초과한 코드

시작 시간에서 1초씩 증가해가면서 시, 분, 초의 범위가 넘어가면 다시 초기화해줬다.

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>

int change(char c1, char c2) {
	
	int res = 0;
	if (c1 == '0') {
		res = c2 - '0';
	}
	else {
		res = (c1 - '0') * 10 + (c2 - '0');
	}
	return res;
}



void main() {


	char curTime[9], nextTime[9];
	scanf("%s", curTime);
	scanf("%s", nextTime);

	//printf("%c %c", curTime[0], curTime[1]);

	int cur_h = change(curTime[0], curTime[1]);
	int cur_m = change(curTime[3], curTime[4]);
	int cur_s = change(curTime[6], curTime[7]);

	int next_h = change(nextTime[0], nextTime[1]);
	int next_m = change(nextTime[3], nextTime[4]);
	int next_s = change(nextTime[6], nextTime[7]);
	
	

	//printf("%d %d %d \n%d %d %d\n\n", cur_h, cur_m, cur_s, next_h, next_m, next_s);


	int secCnt = 0;
	//while (cur_h != next_h || cur_m != next_m || cur_s != next_s) {	//셋다 같으면 멈춤
	while(!(cur_h==next_h && cur_m==next_m && cur_s==next_s)){
		secCnt += 1;

		cur_s += 1;
		if (cur_s == 60)
		{
			cur_s = 0;
			cur_m += 1;
		}
		if (cur_m == 60) {
			cur_m = 0;
			cur_h += 1;
		}
		if (cur_h == 24) {
			cur_h == 0;
		}
		printf("%d %d %d\n", cur_h, cur_m, cur_s);

	}
	printf("%d\n", secCnt);

	int h = secCnt / 3600;					
	int r = secCnt - h * 3600;
	int m = r / 60;					
	int s = r - m * 60;


	if (h < 10) {
		printf("0");
	}
	printf("%d:", h);


	if (m < 10) printf("0");
	printf("%d:", m);

	if (s < 10) printf("0");
	printf("%d", s);




}