홈 > IT > 질문답변
질문답변

String이 주어지면, 중복된 char가 없는 가장 긴 서브스트링 (substring)의 길이를 찾으시오.

1 confg 4 584
String이 주어지면, 중복된 char가 없는 가장 긴 서브스트링 (substring)의 길이를 찾으시오. 


예제)

Input: “aabcbcbc”
Output: 3 // “abc”

Input: “aaaaaaaa”
Output: 1 // “a”


Input: “abbbcedd”
Output: 4 // “bced”
4 Comments
3 realdragonhead 04.27 22:44  
제 짧은 지식으로 풀어봤습니다. 결과는 맞게 나오는것 같습니다.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define length 100

void main() {
        int strcount=0, len=0, bestcount=0, besttemp = 0;
        unsigned char temp;
        char * usrstr = (char *)malloc(sizeof(char)*length);
        char * comparsion = (char *)malloc(sizeof(char)*length);
        int best[length] = {0, };

        comparsion[0] = '\0';

        puts("스트링을 입력하면 중복된 문자가 없는 가장 긴 서브스트링 길이를 구합니다.");
        fputs("Input : ", stdout);

        while(1) {
                if(strcount == length) {
                        usrstr[length-1] = '\0';
                        break;
                }
                temp = getchar();
                if(temp == '\n') {
                        usrstr[strcount] = '\0';
                        break;
                }

                for(int i = 0; i <= len; i++) {
                        if(comparsion[0]=='\0') {
                                comparsion[0] = temp;
                                len++;
                                break;
                        }
                        if(temp == comparsion[i]) {
                                comparsion[0] = '\0';
                                best[bestcount] = len;
                                len = 0;
                                bestcount++;
                                break;
                        }
                        if(i == len) {
                                comparsion[i] = temp;
                                len++;
                                break;
                        }
                }

                usrstr[strcount] = temp;
                strcount++;
        }
 
        besttemp = best[0];

        for(int j = 1; j <= bestcount; j++) {
                besttemp = besttemp > best[j] ? besttemp : best[j];
        }

        if(besttemp == 0 && len >= 0) {
                besttemp = len;
        }

        printf("사용자 입력 : %s\n", usrstr);        //사용자가 입력한 값을 볼 수 있는 곳인데 주석처리해도 될꺼 같습니다.
        printf("Output : %d\n", besttemp);

        free(usrstr);
        free(comparsion);
}
3 Selovic 04.27 22:51  
int longestSubstringLength(String s) {
int ret = 0;
int start = 0;
Map<char, int> map = new HashMap<>();
for (int j = 0; j < s.length(); j++) {
if (map.containsKey(s[j])) {
start = Math.max(map.get(s[j]), start);
}
ret = Math.max(ret, j - start + 1);
map.put(s[j], j + 1); // 캐릭터 인덱스 저장
}
return ret;
}
3 realdragonhead 04.27 23:04  
코드 정정 하겠습니다. 죄송합니다...

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define length 100

void main() {
        int strcount=0, len=0, bestcount=0, besttemp = 0;
        unsigned char temp;
        char * usrstr = (char *)malloc(sizeof(char)*length);
        char * comparsion = (char *)malloc(sizeof(char)*length);
        int best[length] = {0, };

        comparsion[0] = '\0';

        puts("스트링을 입력하면 중복된 문자가 없는 가장 긴 서브스트링 길이를 구합니다.");
        fputs("Input : ", stdout);

        while(1) {
                if(strcount == length) {
                        usrstr[length-1] = '\0';
                        break;
                }
                temp = getchar();
                if(temp == '\n') {
                        usrstr[strcount] = '\0';
                        break;
                }

                for(int i = 0; i <= len; i++) {
                        if(comparsion[0]=='\0') {
                                comparsion[0] = temp;
                                len++;
                                break;
                        }
                        if(temp == comparsion[i]) {
                                comparsion[0] = temp';
                                best[bestcount] = len;
                                len = 1;
                                bestcount++;
                                break;
                        }
                        if(i == len) {
                                comparsion[i] = temp;
                                len++;
                                break;
                        }
                }

                usrstr[strcount] = temp;
                strcount++;
        }
 
        besttemp = best[0];

        for(int j = 1; j <= bestcount; j++) {
                besttemp = besttemp > best[j] ? besttemp : best[j];
        }

        if(besttemp == 0 && len >= 0) {
                besttemp = len;
        }

        printf("사용자 입력 : %s\n", usrstr);        //사용자가 입력한 값을 볼 수 있는 곳인데 주석처리해도 될꺼 같습니다.
        printf("Output : %d\n", besttemp);

        free(usrstr);
        free(comparsion);
}
3 realdragonhead 04.28 10:05  
다른 방식으로 한번 짜봤습니다. selovic 님이 달아준 코드가 짧으면서 좋은것 같습니다. c++를 공부를 못해봐서 c로 짯습니다.
#include <stdio.h>
#include <stdlib.h>
#define length 100

int longsubstring(char * ,int );
void main() {
        unsigned char temp;
        char * usrinput = (char *)malloc(sizeof(char)*length);
        int strcount=0;

        puts("스트링을 입력하면 중복된 문자가 없는 가장 긴 서브스트링 길이를 구합니다.");
        fputs("Input : ", stdout);

        while(1) {
                if(strcount == (length-1)) {
                        usrinput[length-1] = '\0';
                        break;
                }
                temp = getchar();
                if(temp == '\n') {
                        usrinput[strcount] = '\0';
                        break;
                }
                usrinput[strcount] = temp;
                strcount++;
        }
        printf("Output : %d\n", longsubstring(usrinput, strcount));
}

int longsubstring(char * finput ,int strlength) {
        int index = 0;
        int len =0, maxresult =0;

        for(int j=0; j < strlength; j++) {
                for(int k = index; k < j; k++) {
                        if(finput[j]==finput[k]) {
                                index=j;
                                maxresult = maxresult>=len?maxresult:len;
                                len=0;
                                break;
                        }
                }
                len++;
        }
        return maxresult>=len?maxresult:len;
}
Category
State
  • 현재 접속자 45 명
  • 오늘 방문자 191 명
  • 어제 방문자 851 명
  • 최대 방문자 948 명
  • 전체 방문자 185,261 명
  • 전체 게시물 1,968 개
  • 전체 댓글수 250 개
  • 전체 회원수 114 명
Facebook Twitter GooglePlus KakaoStory KakaoTalk NaverBand
PlusFriend Chat