[코드포스 CODEFORCES] 4C Registration system 풀이 코드 (C/C++/Java /Python)

코드포스(Codeforces) 4C Registration system 풀이 코드

C | C++ | Java | Python

Difficulty : *1300 (Data structures / Hashing / Implementation)

---

문제 해설

문자열들을 순서대로 기록하며 새로운 문자열일 땐 'OK'를, 중복된 문자열일 땐 문자열 끝에 오름차순으로 숫자를 붙여 출력하는 문제입니다.

풀이

풀이

• C
• C++
• Java
• Python

동적할당으로 배열을 선언하고 문자열을 입력받을 때마다 기존 배열과 비교하여 새 문자열이 중복인지 아닌지 판단합니다. 각 문자열의 중복이 몇 번 있었는지 표시할 int 배열도 선언하여 비교에 사용합니다. 중복되지 않았다면 배열에 해당 문자열을 추가함과 동시에 'OK'를 출력하고, 중복이라면 문자열을 배열에 추가하지는 않고 중복 횟수는 1회 늘린 후 해당 문자열과 숫자를 출력합니다.

문자열을 키로, 입력 횟수를 값으로 가지는 맵을 선언하고 새로 들어오는 문자열이 맵에 없을 경우 'OK'를 출력 후 맵에 값 1로 저장, 맵에 있을 경우 키와 값을 출력하고 중복 횟수를 1회 늘립니다.

한 번 등장한 문자열을 HashSet에, 해당 문자열과 중복 횟수를 HashMap에 저장하면서 새로 들어오는 문자열이 중복인지 아닌지 판단합니다. 최대 100,000개 문자열이 들어오기 때문에 List 같은 구조를 사용할 경우 문자열 중복을 판단할 때 시간제한에 걸리기 쉽습니다. 그래서 탐색이 빠른 HashSet.contains()를 사용합니다. 또, 혹시 모를 입출력 지연도 막기 위해 Scanner 대신 BufferedReader를 사용했습니다. 문자열이 중복되지 않는다면 각 HashMap과 HashSet에 새로운 문자열을 기록하고 'OK'를 출력, 중복이라면 해당 문자열의 중복 횟수를 1회 늘린 후 중복 횟수와 함께 출력합니다.

문자열을 키로, 입력 횟수를 값으로 가지는 딕셔너리를 선언하고 새로 들어오는 문자열이 딕셔너리에 없을 경우 'OK'를 출력, 딕셔너리에 있을 경우 해당 문자열의 중복 횟수를 1회 늘린 후 중복 횟수와 함께 출력합니다.

코드

• C
• C++
• Java
• Python

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
 
int printString(int l, int n, char** names, int* number, char* buffer){
    int i;
    
    if (l > 0){
        char* newstrptr = (char*)malloc(sizeof(char) * (l + 1));
        strcpy(newstrptr, buffer);
        for(i = 0; i <= n; i++){
            if(!strcmp(names[i], newstrptr)){
                number[i]++;
                printf("%s%d\n", names[i], number[i]);
                return n;
            }
        }
        strcpy(newstrptr, buffer);
        names[n] =  newstrptr;
        printf("OK\n");
        n++;
    }
    return n;
}
 
 
int main(){
    int maxLength = 10000, i, times;
    char* names[maxLength];
    
    for(i = 0; i < 10000; i++){
        names[i] = (char*)malloc(sizeof(char) * 33);
    }
    
    int number[10000] = {0, };
    char buffer[33];
    int n = 0;
    int l = 0;
    scanf("%d", &times);
    
    for(i = 0; i < times; i++){
        scanf("%s", buffer);
        l = strlen(buffer);
        n = printString(l, n, names, number, buffer);
    }
    return 0;
}

#include <iostream>
#include <map>
#include <string>

int main()
{
    std::string a;
    int n;
    std::map<std::string, int> list;
    
    std::cin>>n;
    
    for(int i=0; i<n; i++){
        std::cin>>a;
        if(list.count(a)==0){
            std::cout<<"OK"<<std::endl;
            list[a] = 1;
        }
        else{
            std::cout<<a<<list[a]<<std::endl;
            list[a] += 1;
        }
    }
    
    return 0;
}

import java.util.HashMap;
import java.util.HashSet;
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
 
public class Main {
    public static void main(String[] args) {
        HashMap<String, Integer> numbers = new HashMap<>();
        HashSet<String> names = new HashSet<>();
        String buffer;
 
        try{
            BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
            BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
            int n = Integer.parseInt(br.readLine());
 
            for(int i = 0; i < n; i++){
                buffer = br.readLine();
                if(!names.contains(buffer)){
                    numbers.put(buffer, 1);
                    names.add(buffer);
                    bw.write("OK\n");
                }
                else{
                    bw.write(buffer+ numbers.get(buffer) +"\n");
                    numbers.put(buffer, numbers.get(buffer) + 1);
                }
            }
        
        	bw.flush();
        	bw.close();
        }
        catch (Exception e) {
        }
    }
}

arr = {}

n = int(input())
for i in range(n):
    temp = input()
    if temp in arr:
        arr[temp] += 1;
        print(temp+str(arr[temp]))
    else:
        arr[temp] = 0;
        print("OK")

문제 출처

https://codeforces.com/contest/4/problem/C