그냥 코딩하는 사람의 블로그

문제 설명

3.Longest Substring Without Repeating Characters

Medium

Given a strings, find the length of the longest substring without repeating characters.

Example 1:
**Input:** s = "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.

Example 2:
Input: s = "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.

Example 3:
Input: s = "pwwkew"
Output: 3
Explanation: The answer is "wke", with the length of 3. Notice that the answer must be a substring, "pwke" is a subsequence and not a substring.

Example 4:
Input: s = ""
Output: 0

Constraints:

• 0 <= s.length <= 5 * 10^4
• consists of English letters, digits, symbols and spaces.

풀이 과정

1. 현재 중복을 검사할 set과 Substring을 담을 queue를 구성한다.
2. 문자열을 왼쪽에서부터 오른쪽으로 문자 하나씩 진행한다
   • 문자 하나씩 반복문을 진행한다.
   • 만약 문자가 set 안에 있는 경우는, 기존 길이가 answer보다 길다면 저장한 다음, 해당 문자까지 queue와 set에서 빼주고 set하고 queue의 맨 마지막에 해당 문자를 다시 넣어준다.
   • 만약 문자가 set 안에 있지 않은 경우는 그대로 queue와 set에 넣어주면 된다.
3. 길이 최댓값을 리턴

소스 코드

from collections import deque

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        answer = 0
        length = 1
        if len(s) == 0:
            return 0
        check = set([s[0]])
        queue = deque([s[0]])
        for i in range(1, len(s)):
            if s[i] not in check:
                length += 1
                check.add(s[i])
                queue.append(s[i])
            else:
                answer = max(length, answer)
                while queue:
                    p = queue.popleft()
                    check.remove(p)
                    if p == s[i]:
                        break
                queue.append(s[i])
                check.add(s[i])
                length = len(check)

        answer = max(length, answer)
        return answer

문제 설명

문제

이진 검색 트리는 다음과 같은 세 가지 조건을 만족하는 이진 트리이다.

• 노드의 왼쪽 서브트리에 있는 모든 노드의 키는 노드의 키보다 작다.
• 노드의 오른쪽 서브트리에 있는 모든 노드의 키는 노드의 키보다 크다.
• 왼쪽, 오른쪽 서브트리도 이진 검색 트리이다.

전위 순회 (루트-왼쪽-오른쪽)은 루트를 방문하고, 왼쪽 서브트리, 오른쪽 서브 트리를 순서대로 방문하면서 노드의 키를 출력한다. 후위 순회 (왼쪽-오른쪽-루트)는 왼쪽 서브트리, 오른쪽 서브트리, 루트 노드 순서대로 키를 출력한다. 예를 들어, 위의 이진 검색 트리의 전위 순회 결과는 50 30 24 5 28 45 98 52 60 이고, 후위 순회 결과는 5 28 24 45 30 60 52 98 50 이다.

이진 검색 트리를 전위 순회한 결과가 주어졌을 때, 이 트리를 후위 순회한 결과를 구하는 프로그램을 작성하시오.

입력

트리를 전위 순회한 결과가 주어진다. 노드에 들어있는 키의 값은 106보다 작은 양의 정수이다. 모든 값은 한 줄에 하나씩 주어지며, 노드의 수는 10,000개 이하이다. 같은 키를 가지는 노드는 없다.

출력

입력으로 주어진 이진 검색 트리를 후위 순회한 결과를 한 줄에 하나씩 출력한다.

풀이 과정

1. 전위 순회는 루트를 먼저 순회하므로, 전위 순회한 순서대로 노드를 넣어서 이진 검색 트리를 만들면 문제와 똑같은 트리가 만들어 진다.
   • 현재 노드보다 작으면 왼쪽 자식 노드
   • 현재 노드보다 크면 오른쪽 자식 노드
   • 자식 노드가 None인 경우 거기다가 넣어준다.
2. 후위 순회의 경우 recursion으로 구현한다. (left -> right -> 루트)
3. 입력 종료 글자가 없으므로 try..except로 입력 종료

소스 코드

import sys

sys.setrecursionlimit(10**5)

class tree_node():
    def __init__(self, element):
        self.left = None
        self.right = None
        self.element = element


def push_tree(tree, element):
    if tree.element == None: # 맨 위 루트노드는 초깃값 None
        tree.element = element
    else:
        temp = tree_node(element)
        while True:
            # 현재 트리의 요소보다 입력값이 크면 오른쪽
            if tree.element < element:
                if tree.right == None:
                    tree.right = temp
                    break
                else:
                    tree = tree.right
            # 작으면 왼쪽
            else:
                if tree.left == None:
                    tree.left = temp
                    break
                else:
                    tree = tree.left

def post_order(tree):
    if tree == None:
        return
    post_order(tree.left)
    post_order(tree.right)
    print(tree.element)

Tree = tree_node(None)
while True:
    try:
        p = int(input())
        push_tree(Tree, p)
    except:
        break

post_order(Tree)

풀이 과정

• row와 column의 범위가 작은 편이므로 combinations를 사용하여서 풀이

1. 모든 column의 조합들을 구한다. (1개 ~ column의 길이)
2. 각각의 column 조합에 대해 최소성과 유일성 검사
   • 최소성의 경우는, 각 column의 조합에 대해 다시 조합들을 구한 뒤, 조합들중 하나라도 후보키에 있는지 검사
   • 유일성의 경우는, 릴레이션에서 각 튜플들에 대해 column의 조합으로 데이터를 구성하여 하나씩 넣어본 다음, 중복되는 요소가 있다면 유일성 만족하지 않음.
3. 후보키의 개수를 리턴해주면 된다.

소스 코드

from itertools import combinations

# 유일성 만족 확인
def simulation(relation, columns):
    compare_set = set()
    for tup in relation:
        target = []
        for col in columns:
            target.append(tup[col])
        target = tuple(target)
        if target in compare_set:
            return False
        compare_set.add(target)
    return True

# 최소성 확인(자신보다 짧은 최소키가 있는지)
def check_in_set(candidate, case):
    case_len = len(case)

    for i in range(1, case_len+1):
        total_case = list(combinations(case, i))
        for case_ in total_case:
            if case_ in candidate:
                return False
    return True


def solution(relation):
    answer = 0
    col_len = len(relation[0])
    cols = [i for i in range(col_len)]
    candidate = set()
    for i in range(1, col_len+1):
        all_case = list(combinations(cols, i))
        for case in all_case:
            # 유일성과 최소성을 만족하는지 확인
            if check_in_set(candidate, case) and simulation(relation, case): 
                candidate.add(case)
                answer += 1

    return answer

출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges

풀이 과정

1. "ICN"이 시작점이므로, ICN에서 시작하여 DFS를 진행하면서, DFS의 깊이가 ticket의 길이까지 진행되는지 체크
   • 이 때, 가능한 경로가 2개 이상인 경우 알파벳 순서가 앞서는 경로를 return 해주어야 한다.
   • 따라서, 시작하기 전에 tickets의 2번째 요소([i][2]) 기준으로 오름차순 정렬 해 준다.
2. DFS를 진행하면서 정답과 방문여부에 push/pop 해주고, DFS를 ticket의 길이만큼 깊게 진행하였다면 정답 리스트를 출력해주면 된다.

• DFS의 이론은 알겠는데 Recursion에서 정답을 어떻게 표시해 주어야 할지 공부가 더 필요함..

소스 코드

end_flag = False
answer = []

def dfs(tickets, visited, city):
    global end_flag, answer
    if len(visited) == len(tickets):
        answer.append(city)
        end_flag = True
        return

    for i in range(len(tickets)):
        if tickets[i][0] == city and i not in visited:
            visited.add(i)
            answer.append(tickets[i][0])
            dfs(tickets, visited, tickets[i][1])
            if end_flag:
                return
            answer.pop()
            visited.remove(i)


def solution(tickets):
    global answer
    tickets.sort(key=lambda x:x[1])
    dfs(tickets, set(), "ICN")

    return answer

출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges

문제 설명

문제

정사각형으로 이루어져 있는 섬과 바다 지도가 주어진다. 섬의 개수를 세는 프로그램을 작성하시오.

한 정사각형과 가로, 세로 또는 대각선으로 연결되어 있는 사각형은 걸어갈 수 있는 사각형이다.

두 정사각형이 같은 섬에 있으려면, 한 정사각형에서 다른 정사각형으로 걸어서 갈 수 있는 경로가 있어야 한다. 지도는 바다로 둘러싸여 있으며, 지도 밖으로 나갈 수 없다.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다.

둘째 줄부터 h개 줄에는 지도가 주어진다. 1은 땅, 0은 바다이다.

입력의 마지막 줄에는 0이 두 개 주어진다.

풀이 과정

1. 일반적인 BFS는 상하좌우인데 이번 케이스는 대각선까지 고려해야 하는 경우
   • 전체 2차원배열 루프를 돌면서 [i][j] = 1이 될 때를 찾는다.
   • [i][j]부터 시작하여 연결된 모든 섬들의 값을 0으로 조정해준 다음, 섬의 개수를 1개 늘려준다.
   • 전체 배열을 돌때까지 반복
2. 섬의 개수를 출력해주면 된다.

소스 코드

import sys
from collections import deque
input = sys.stdin.readline

def bfs(graph, x, y):
    queue = deque([[x, y]])
    graph[x][y] = 0
    # 상하좌우
    dx = [-1, 1, 0, 0] 
    dy = [0, 0, 1, -1]

    # 대각선
    dx2 = [1, 1, -1, -1]
    dy2 = [-1, 1, -1, 1]
    while queue:
        x, y = queue.popleft()
        for i in range(4):
            # 상하좌우
            nx, ny = x+dx[i], y+dy[i]
            if 0 <= nx and nx < len(graph) and (
                0 <= ny and ny < len(graph[0])
            ):
               if graph[nx][ny] != 0:
                   graph[nx][ny] = 0
                   queue.append([nx, ny])
            # 대각선
            nx, ny = x+dx2[i], y+dy2[i]
            if 0 <= nx and nx < len(graph) and (
                0 <= ny and ny < len(graph[0])
            ):
                if graph[nx][ny] != 0:
                    graph[nx][ny] = 0
                    queue.append([nx,ny])


while True:
    w, h = map(int, input().rstrip().split())
    if w == 0 and h == 0:
        break

    graph = [list(map(int, input().rstrip().split())) for _ in range(h)]
    answer = 0
    for i in range(h):
        for j in range(w):
            if graph[i][j] == 1:
                answer += 1
                bfs(graph, i, j)
    print(answer)

문제 설명

문제

상근이는 문자열에 폭발 문자열을 심어 놓았다. 폭발 문자열이 폭발하면 그 문자는 문자열에서 사라지며, 남은 문자열은 합쳐지게 된다.

폭발은 다음과 같은 과정으로 진행된다.

• 문자열이 폭발 문자열을 포함하고 있는 경우에, 모든 폭발 문자열이 폭발하게 된다. 남은 문자열을 순서대로 이어 붙여 새로운 문자열을 만든다.
• 새로 생긴 문자열에 폭발 문자열이 포함되어 있을 수도 있다.
• 폭발은 폭발 문자열이 문자열에 없을 때까지 계속된다.

상근이는 모든 폭발이 끝난 후에 어떤 문자열이 남는지 구해보려고 한다. 남아있는 문자가 없는 경우가 있다. 이때는 "FRULA"를 출력한다.

폭발 문자열은 같은 문자를 두 개 이상 포함하지 않는다.

입력

첫째 줄에 문자열이 주어진다. 문자열의 길이는 1보다 크거나 같고, 1,000,000보다 작거나 같다.

둘째 줄에 폭발 문자열이 주어진다. 길이는 1보다 크거나 같고, 36보다 작거나 같다.

두 문자열은 모두 알파벳 소문자와 대문자, 숫자 0, 1, ..., 9로만 이루어져 있다.

출력

첫째 줄에 모든 폭발이 끝난 후 남은 문자열을 출력한다.

풀이과정

1. 문자열들을 순차적으로 스택에 넣으면서 비교
   • 스택의 길이가 n이라고 하고, 폭발 문자열의 길이가 k라고 할때
   • 스택[n-k] ~ 스택[n]이 폭발 문자열인지 확인한다.
   • 폭발 문자열이라면, 스택에서 pop해주고 폭발에 의해 또다시 폭발 문자열 확인
   • 폭발 문자열이 아니라면, 비교과정 종료
2. 스택이 비어있다면 'FRULA', 스택에 요소가 있다면 해당 요소를 출력해주면 된다.

소스 코드

import sys
from collections import deque

input = sys.stdin.readline

string = input().rstrip()
boom = input().rstrip()

stack = deque()
for s in string:
    stack.append(s)
    while True:
        if len(stack) < len(boom):
            break
        length_s = len(stack)
        length_b = len(boom)
        flag = False
        for i in range(len(boom)):
            if boom[i] == stack[length_s-length_b+i]:
                pass
            else:
                flag = True
                break

        if flag:
            break
        else:
            for i in range(len(boom)):
                stack.pop()
if stack:
    print("".join(stack))
else:
    print("FRULA")

문제 설명

문제

백준 문제 풀이에 힘들어하는 수진이를 위해 민우는 문제해결에 도움이 되는 고무오리를 준비했다. 민우가 준비한 고무오리는 신비한 능력이 존재하는데, 최근에 풀던 백준 문제를 해결해주는 능력이다. 신비한 고무오리와 함께 수진이의 백준 풀이를 도와주자!

고무오리의 사용법은 다음과 같다.

• "고무오리 디버깅 시작" 이라고 외친다
• 문제들을 풀기 시작한다
• 고무오리를 받으면 최근 풀던 문제를 해결한다
• "고무오리 디버깅 끝" 이라고 외치면 문제풀이를 종료한다.

하지만 고무오리에는 치명적인 문제가 있는데, 풀 문제가 없는데 사용한다면 고무오리는 체벌로 두 문제를 추가한다는 점이다.

입력

첫 번째 줄에 "고무오리 디버깅 시작"이라고 주어진다. 두 번째 줄부터 "고무오리" 또는 "문제"가 주어진다. 이는 "고무오리 디버깅 끝"이 주어질 때까지 반복한다. 최대 102줄이 입력으로 주어진다.

출력

고무오리 디버깅이 끝날 때, 주어진 문제를 수진이가 해결하였는지 여부에 따라 남은 문제 없이 모든 문제를 해결하였으면 "고무오리야 사랑해"을 출력하고 하나라도 문제가 남았다면 "힝구"를 출력하라.

풀이 과정

1. 스택에 push / pop
   • 고무오리를 받은 경우 stack에서 pop
     • 이 때, 고무오리를 받았는데 stack이 비어있다면 문제 2개 push
   • 문제를 받은 경우 stack에 push
2. 디버깅 종료 이후 stack에 문제가 남아있다면 "힝구" 출력, 남아있지 않다면 "고무오리야 사랑해" 출력

소스 코드

import sys
from collections import deque

stack = deque()
while True:
    p = sys.stdin.readline().rstrip()

    if p == "고무오리 디버깅 시작":
        continue

    if p == "고무오리 디버깅 끝":
        break

    if p == "문제":
        stack.append(p)
    elif p == "고무오리":
        if len(stack) == 0:
            stack.append('문제')
            stack.append('문제')
        else:
            stack.pop()

if stack:
    print("힝구")
else:
    print("고무오리야 사랑해")

문제 설명

문제

상근이는 환갑을 바라보던 나이에 수능 시험을 다시보고 교대에 입학했고, 초등학교 선생님으로 취직했다.

• 상근: 요즘 애들은 친구를 사귀지 않나봐. 내가 앞에서 보고 있으면, 친구가 있는 학생이 별로 없는 것 같아.
• ??: 오빠! 오빠는 말콤의 친구와 성적이라는 책 안 읽어 봤어? 이 책에는 성적과 친구가 무슨 관계가 있는지 나와. 요즘 애들은 친구를 사귀기 전에 먼저 그 친구의 반 등수를 살펴봐. 말콤은 이 연구를 하기 위해서 6년동안 초등학교에서 선생님으로 위장 했었지. 하지만, 6년이라는 시간을 초등학교에서 보냈지만, 그 사람은 결국 결론을 얻지 못했어.
• 상근: 근데?
• ??: 말콤이 어느 날 자신이 초등학생이 되어 학교를 활보하는 꿈을 꾸었어. 근데 잠을 깨고 나니 내가 꿈을 꾸고 초등학생이 된건지, 아니면 초등학생이 꿈을 꾸고 지금의 내가 되어있는지를 모르겠는거야. 그래서 말콤은 상식적인 사고 방식에 큰 의문을 가졌지. 그 때 말콤은 깨달았던거야. 초등학교 친구는 부질없구나. 그제서야 알게된거야. 모든 학생은 자신과 반 등수의 차이가 K를 넘으면 친구가 아니라는거.
• 상근: 아? 근데 K는 어떻게 구해?
• ??: K는 문제에서 주어지지. 근데, 더 중요한 사실이 있어. 친구와 좋은 친구의 차이야. 말콤이 친구와 성적을 쓰고 2년 뒤에 낸 책인 좋은 친구라는 책에는 좋은 친구는 이름의 길이가 같아야 된다는 말이 나와.
• 상근: 아! 그럼 난 오늘 집에 가서 우리 반에 좋은 친구가 몇 쌍이나 있는지 구해봐야 겠어!

상근이네 반의 N명 학생들의 이름이 성적순으로 주어졌을 때, 좋은 친구가 몇 쌍이나 있는지 구하는 프로그램을 작성하시오. 좋은 친구는 등수의 차이가 K보다 작거나 같으면서 이름의 길이가 같은 친구이다.

입력

첫째 줄에 N과 K가 주어진다. (3 ≤ N ≤ 300,000, 1 ≤ K ≤ N) 다음 N개 줄에는 상근이네 반 학생의 이름이 성적순으로 주어진다. 이름은 알파벳 대문자로 이루어져 있고, 2글자 ~ 20글자이다.

풀이 과정

1. 학생들을 성적 순으로 순차적으로 큐에 넣어준다.
   • 큐의 길이가 K를 넘게 된다면, 큐에서 하나 빼주고, 딕셔너리에서 빼준 학생의 이름 길이의 값도 하나 빼줌.
   • 현재 넣어야 하는 학생의 이름과 길이가 같은 큐에 있는 사람들의 수만큼 정답을 늘려줌.(이 때, 딕셔너리 사용)
   • 큐에 학생을 넣어줌, 넣어줌과 동시에 딕셔너리에서 해당 학생의 이름 길이의 값을 하나 늘려 줌.
2. 정답을 출력해주면 된다.

• 이 때, 학생들을 넣을때마다 반복문으로 큐에 있는 사람들의 길이를 일일이 비교하면서 정답을 늘려주면 시간 초과가 나타나므로 딕셔너리 활용

소스 코드

import sys
from collections import deque

input = sys.stdin.readline
N, K = map(int, input().rstrip().split())
len_count = {i:0 for i in range(2, 21)}

queue = deque()
answer = 0
for i in range(N):
    friend = input().rstrip()
    if i > K:
        t = queue.popleft()
        len_count[len(t)] -= 1
    answer += len_count[len(friend)]
    queue.append(friend)
    len_count[len(friend)] += 1

print(answer)

문제 설명

상근이는 슬로베니아의 도시 Donji Andrijevci를 여행하고 있다. 이 도시의 도로는 깊이가 K인 완전 이진 트리를 이루고 있다. 깊이가 K인 완전 이진 트리는 총 2K-1개의 노드로 이루어져 있다. (아래 그림) 각 노드에는 그 곳에 위치한 빌딩의 번호가 붙여져 있다. 또, 가장 마지막 레벨을 제외한 모든 집은 왼쪽 자식과 오른쪽 자식을 갖는다.

깊이가 2와 3인 완전 이진 트리

상근이는 도시에 있는 모든 빌딩에 들어갔고, 들어간 순서대로 번호를 종이에 적어 놓았다. 한국으로 돌아온 상근이는 도시가 어떻게 생겼는지 그림을 그려보려고 하였으나, 정확하게 기억이 나지 않아 실패했다. 하지만, 어떤 순서로 도시를 방문했는지 기억해냈다.

1. 가장 처음에 상근이는 트리의 루트에 있는 빌딩 앞에 서있다.
2. 현재 빌딩의 왼쪽 자식에 있는 빌딩에 아직 들어가지 않았다면, 왼쪽 자식으로 이동한다.
3. 현재 있는 노드가 왼쪽 자식을 가지고 있지 않거나 왼쪽 자식에 있는 빌딩을 이미 들어갔다면, 현재 노드에 있는 빌딩을 들어가고 종이에 번호를 적는다.
4. 현재 빌딩을 이미 들어갔다 온 상태이고, 오른쪽 자식을 가지고 있는 경우에는 오른쪽 자식으로 이동한다.
5. 현재 빌딩과 왼쪽, 오른쪽 자식에 있는 빌딩을 모두 방문했다면, 부모 노드로 이동한다.

왼쪽 그림에 나와있는 마을이라면, 상근이는 2-1-3 순서대로 빌딩을 들어갔을 것이고, 오른쪽 그림의 경우에는 1-6-4-3-5-2-7 순서로 들어갔을 것이다. 상근이가 종이에 적은 순서가 모두 주어졌을 때, 각 레벨에 있는 빌딩의 번호를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 K (1 ≤ K ≤ 10)가 주어진다.

둘째 줄에는 상근이가 방문한 빌딩의 번호가 들어간 순서대로 주어진다. 모든 빌딩의 번호는 중복되지 않으며, 구간 [1,2K)에 포함된다.

출력

총 K개의 줄에 걸쳐서 정답을 출력한다. i번째 줄에는 레벨이 i인 빌딩의 번호를 출력한다. 출력은 왼쪽에서부터 오른쪽 순서대로 출력한다.

풀이 과정

1. 1~5번을 읽어 보면 트리의 중위 순회임을 알 수 있다. (왼쪽 자식 -> 부모 -> 오른쪽 자식)
2. 따라서, 재귀함수로 구현한다.
   • 시작 구간은 0~(2^K-1)
   • 구간의 가운데가 부모 노드이다.
   • 왼쪽 구간과 오른쪽 구간은 자식 노드이므로 레벨이 1 증가한다. 이 때, 출력은 왼쪽에서부터 오른쪽 순서이므로 왼쪽 구간부터 방문하면서 레벨 리스트에 넣어준다.
3. 각 레벨 리스트의 요소들을 출력해주면 된다.

소스 코드

import sys

K = int(sys.stdin.readline().rstrip())
nodes = list(map(int, sys.stdin.readline().rstrip().split()))

levels = [[] for _ in range(K)]

def visit(level, left, right):
    if left == right:
        levels[level].append(nodes[left])
        return

    mid = (left + right) // 2
    visit(level+1, left, mid-1)
    visit(level+1, mid+1, right)
    levels[level].append(nodes[mid])

visit(0, 0, len(nodes)-1)

for level in levels:
    print(*level)

문제 설명

문제

어떠한 자연수 N은, 몇 개의 연속된 자연수의 합으로 나타낼 수 있다. 당신은 어떤 자연수 N(1 ≤ N ≤ 10,000,000)에 대해서, 이 N을 몇 개의 연속된 자연수의 합으로 나타내는 가지수를 알고 싶어한다. 이때, 사용하는 자연수는 N이하여야 한다.

예를 들어, 15를 나타내는 방법은 15, 7+8, 4+5+6, 1+2+3+4+5의 4가지가 있다. 반면에 10을 나타내는 방법은 10, 1+2+3+4의 2가지가 있다.

N을 입력받아 가지수를 출력하는 프로그램을 작성하시오.

입력

첫 줄에 정수 N이 주어진다.

출력

입력된 자연수 N을 몇 개의 연속된 자연수의 합으로 나타내는 가지수를 출력하시오

풀이 과정

1. 투포인터 알고리즘 사용
   • left, right를 두어, 합계를 left~right까지의 합으로 지정
   • 현재 합계가 N보다 작다면 right를 늘려 구간을 넓힘
   • 현재 합계가 N보다 크거나 같다면 left를 늘려 구간을 좁힘
     • 이 때, N보다 클 때는 정답의 개수를 저장해주어야 함.
2. 저장해 둔 정답의 개수 출력

소스 코드

import sys

n = int(sys.stdin.readline())

left = 1
right = 1
sumation = 1
answer = 0
while(left <= right):
    if sumation == n:
        answer += 1
    if sumation < n:
        right += 1
        sumation += right
    elif sumation >= n:
        sumation -= left
        left += 1

print(answer)