반응형 전체 글11 [BOJ17298] 오큰수 [BOJ17298] 오큰수 문제 링크 BOJ17298 - 오큰수 문제 설명 N개의 원소로 이루어진 수열이 주어진다. 수열의 각 원소를 기준으로 오른쪽에 있는 원소 중에 기준이 되는 원소보다 큰 수가 있다면 그 수를, 없다면 -1을 출력한다. 수열을 이루는 원소의 갯수를 의미하는 N은 최대 백만(106), 원소의 크기의 범위는 1에서 백만이다. 풀이 설명 수열의 각 요소보다 큰, 오른쪽에 있는, 가장 가까운 수를 차례대로 구하는 문제였다. N이 최대 백만인 경우에 N2만큼의 연산을 하는 완전탐색으로는 시간 초과가 발생한다. 기준 원소에서 오른쪽으로 가장 가까운 원소를 구해야 하므로 삽입되는 순서가 유지되어야하고, 기준 원소보다 큰 원소가 바로 오른쪽에 없을 때, 이후에도 나올 수 있기 때문에 크기 비교 연.. 2021. 11. 19. [BOJ10799] 쇠막대기 [BOJ10799] 쇠막대기 문제 링크 BOJ10799 - 쇠막대기 문제 설명 (는 쇠막대기의 시작, )는 쇠막대기의 끝을 의미한다. ()처럼 붙어있는 괄호는 레이저를 의미하는데, 레이저로 쇠막대기를 잘랐을 때 쇠막대기가 몇 조각이 나오는지를 출력하는 문제이다. 쇠막대기의 길이가 짧을수록 위에 존재하며, 쇠막대기끼리 양 끝점이 겹치지 않는다. 위의 그림에서 화살표는 레이저를 의미한다. 따라서 레이저로 쇠막대기를 잘랐을 때 17개의 조각이 나온다. 풀이 설명 (가 나오면 스택에 담는다. 스택의 크기는 쇠막대기의 갯수를 의미하는데, 레이저가 한번 자를 때 쇠막대기의 갯수만큼 조각이 생기니까 스택의 갯수만큼 Answer에 더해준다. 레이저를 의미하는 ()의 여는 괄호도 스택에 담기는데 이는 별도의 조건으로 처.. 2021. 11. 19. [BOJ17413] 단어 뒤집기 2 [BOJ17413] 단어 뒤집기 2 문제 링크 BOJ17413 - 단어 뒤집기 2 문제 설명 입력은 알파벳 소문자, 숫자, 공백, 로만 이루어져 있고, 단어를 뒤집어서 출력하는 문제였다. 사이에 있는 문자열은 단어가 아니기 때문에 별도의 조건이 필요했다. 풀이 설명 입력에 공백이 존재하기 때문에 기존의 입력 방식인 cin이 아닌, getline을 사용하여 입력을 받았다. for문을 돌면서 태그를 여는 괄호를 만나면 그 이전 인덱스까지의 문자열을 뒤집는다. 태그를 닫는 괄호를 만나면 현재 인덱스 i의 다음 인덱스를 의미하는 i + 1로 뒤집는 연산의 시작 인덱스를 의미하는 Start변수를 갱신한다. 태그가 닫혀있는 상태이면서 공백을 만나면 현재 인덱스까지의 문자열을 뒤집고, Start를 다음 인덱스로.. 2021. 11. 18. 이전 1 2 3 다음 반응형
