[BOJ/백준] 25501번. 재귀의 귀재 - C++[cpp]

2024. 4. 29. 22:25·PS/BOJ

문제

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

 

시간 초과된 풀이

#include <iostream>
using namespace std;

int count;

int recursion(string s, int l, int r){
    ::count++;
    if(l >= r) return 1;
    else if(s[l] != s[r]) return 0;
    else return recursion(s, l+1, r-1);
}

int isPalindrome(string s){
    return recursion(s, 0, s.length() - 1);
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int n;
    string temp;
    cin >> n;
    while (n--) {
        ::count = 0;
        cin >> temp;
        cout << isPalindrome(temp) << " " << ::count << '\n';
    }
}
  • 함수에서 매개변수 값을 복사하는 시간으로 인해 시간초과 발생

해결 방법 : call-by-reference, 즉 값을 복사하는 것이 아니라, 참조하여 실행 시간을 줄인다

 

#include <iostream>
using namespace std;

int count;

int recursion(string &s, int l, int r){ // 문자열 참조
    ::count++;
    if(l >= r) return 1;
    else if(s[l] != s[r]) return 0;
    else return recursion(s, l+1, r-1);
}

int isPalindrome(string &s){ // 문자열 참조
    return recursion(s, 0, s.length() - 1);
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int n;
    string temp;
    cin >> n;
    while (n--) {
        ::count = 0;
        cin >> temp;
        cout << isPalindrome(temp) << " " << ::count << '\n';
    }
}

 

'PS > BOJ' 카테고리의 다른 글

[PS/BOJ] 20166번. 문자열 지옥에 빠진 호석 - C++[cpp]  (0) 2024.10.10
[BOJ/백준] 1086번. 박성원 - C++[cpp]  (0) 2024.09.07
[BOJ/백준] 11724번. 연결 요소의 개수 - C++[cpp]  (0) 2024.07.13
[BOJ/백준] 11286번. 절댓값 힙 - C++[cpp]  (0) 2024.06.24
[BOJ/백준] 24511번. queuestack - Java[자바]  (0) 2024.03.31
'PS/BOJ' 카테고리의 다른 글
  • [BOJ/백준] 1086번. 박성원 - C++[cpp]
  • [BOJ/백준] 11724번. 연결 요소의 개수 - C++[cpp]
  • [BOJ/백준] 11286번. 절댓값 힙 - C++[cpp]
  • [BOJ/백준] 24511번. queuestack - Java[자바]
lumana
lumana
배움을 나누는 공간 https://github.com/bebeis
  • lumana
    Brute force Study
    lumana
  • 전체
    오늘
    어제
    • 분류 전체보기 N
      • Spring N
        • MVC
        • DB
        • 핵심 원리
        • JPA
      • WEB
        • HTML
        • CSS
        • HTTP
        • Application
      • Computer Science
        • Network
        • Database
        • OS
        • 시스템 프로그래밍
        • 컴퓨터구조
      • Algorithm
        • Divide&Conquer
        • Sort
        • Greedy
        • DP
        • Backtracking
        • NP-Complete
        • Graph
      • Data Structure
        • 자료구조
        • C++ STL
        • Java Collection
      • 소프트웨어 공학
        • 시험 공부 정리
        • Theorem
      • Programming Language
        • Python
        • Java
        • C
        • C++
        • Rust
        • Theory
      • Unix_Linux
        • Common
      • React
      • PS
        • BOJ
        • Tip
        • 프로그래머스
        • CodeForce
      • Book Review
        • Clean Code
      • Math
        • Linear Algebra
      • AI
        • DL
        • ML
        • DA
        • Concepts
      • 우아한테크코스
        • 프리코스
      • Project Review
      • LegacyPosts
      • Android
      • Apple
        • Mac
        • IPhone
        • IPad
      • 모니터
      • Diary
  • 블로그 메뉴

    • 홈
    • 태그
    • 방명록
  • 링크

  • 공지사항

  • 인기 글

  • 태그

  • 최근 댓글

  • 최근 글

  • hELLO· Designed By정상우.v4.10.3
lumana
[BOJ/백준] 25501번. 재귀의 귀재 - C++[cpp]
상단으로

티스토리툴바